Segmentation Error When Running Recursive Bubble Sort in C

Question

I'm attempting to implement the bubble sort algorithm using recursion to sort an array of integers. However, I keep encountering a segmentation error when I compile and run the code. I've tried debugging it but I can't find the problem.

#include <stdio.h>

#define ARR_SIZE 10


//primitive function
void bubble_sort(int array[]);


//sort the number array using bubble sort
int main(void)
{
    int array[] = {4,2,9,3,2,4,9,10,20,4};

    bubble_sort(array);

    for (int i = 0; i < ARR_SIZE ; i++)
    {
        printf("%i\n", array[i]);
    }
}


void bubble_sort(int array[])
{
    int swap_counter = 0;
    for (int i = 0; i < ARR_SIZE - 2; i++)
    {
        if (array[i] >= array[i + 1])
        {
            swap_counter++;
            int temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }

    }


    if (swap_counter != 0)
    {
        bubble_sort(array);
    }
    else
    {
        return;
    }



}

You have a stack overflow (godbolt.org/z/7ncdh1586). That means you probably have unbounded recursion. This should be the first thing you discover with even the most minimal debugging effort. — paddy
– paddy, Commented Aug 24, 2023 at 21:47
You swap identical keys, of which you do have one, so this will keep going (until it runs out of stack space). — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Aug 24, 2023 at 21:49
Obligatory side note: bubblesort is a poor use of recursion. It doesn't scale. Try doing it on a huge array with 100,000,000 elements. Note that recursion is great for mergesort as the recursion depth would be log2 of the length. — Craig Estey
– Craig Estey, Commented Aug 24, 2023 at 22:13
The else { return } seems pretty pointless since that's going to happen anyway at the end of the function. — tadman
– tadman, Commented Aug 24, 2023 at 22:40
Not only is bubblesort a poor subject for recursive computation, but the particular recursion presented is pretty frivolous. — John Bollinger
– John Bollinger, Commented Aug 25, 2023 at 0:46

NoDakker · Accepted Answer · 2023-08-25 02:38:35Z

As noted in the comments above the function appears to perform a swap and subsequent recursive call to the sorting function when the first integer element is either greater than or equal to the second integer element. Performing a swap and call seemed to be unnecessary when the elements are equal. That and when doing some refactoring, the "for" loop was not testing out the very last element in the integer array.

Rather than reposting a wholly refactored program, following are the two code snippets I refactored that appeared to perform the bubble sort function using recursive calls.

In lieu of the following statement:

for (int i = 0; i < ARR_SIZE - 2; i++)

utilize the following size testing:

for (int i = 0; i < ARR_SIZE - 1; i++)

And, in lieu of performing a swap when the two array elements are equal:

if (array[i] >= array[i + 1])

only perform the swap and recursive call when the first element is actually greater than the second element:

if (array[i] > array[i + 1])

When I tested out your code with those refactored bits, following was the terminal output without an overflow issue.

craig@Vera:~/C_Programs/Console/BubbleSort/bin/Release$ ./BubbleSort 
2
2
3
4
4
4
9
9
10
20

Give that a test.

Collectives™ on Stack Overflow

Segmentation Error When Running Recursive Bubble Sort in C

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related