CODEWITHSUNDEEP
csortingqsort
John Carter
John Carter

Reputation: 9

What I am doing wrong with this function, it does not end

this is a function I saw few months ago, I tried to replicate it but I think I am missing something because program does not end.

void quick_sort(int *array, int len) {
     for (int i = 0; i < len - 1; i++) {
         if (array[i] > array[i + 1]) {
             int temp = array[i];
             array[i] = array[i + 1];
             array[i + 1] = temp;
          }
      }
      quick_sort(array, len);
 }

what i am doing wrong here? Can anybody help?

Upvotes: 0

Views: 82

Answers (2)

WhozCraig
WhozCraig

Reputation: 66244

For one, this function is not properly named: this is absolutely nothing like quick-sort. It looks like the inner loop of a bubble-sort algorithm, and the dead-giveaway is the ascending comparison and potential swaps of adjacent elements

That said, to make this sort routine recursive, just push what would otherwise be the outer loop of traditional bubblesort into the recursive activation stack. To understand that, consider a basic non-swap-detection-optimized bubblesort:

void bubblesort(int arr[], size_t len)
{
    while (len-- > 0) // THIS LOOP
    {
        for (size_t i=0; i<len; ++i)
        {
            if (arr[i] > arr[i+1])
            {
                int tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
            }
        }
    }
}

You can see above the outer loop is the thing we want to store in the stack. So how can we do that ? Well, first we need the condition that stops the recursion, and the inner loop. Then, we can just recurse with a length one element smaller than the current length:

void bubblesort(int arr[], size_t len)
{
    if (len-- < 2) // base case to exit on trivial sequence
        return;

    for (size_t i=0; i<len; ++i)
    {
        if (arr[i] > arr[i+1])
        {
            int tmp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = tmp;
        }
    }

    // recurse with one fewer element.
    bubblesort(arr, len);
}

That's it. This is also a textbook example of a tail-recursive application, and as such one we can implement with an iterative loop (obviously, that's what we started with in the first place).

So, in summary, you were missing the exit case and the reduction in length that eventually arrived at that exit case. Addressing both of those, the function should "work" (term used loosely, as no one would ever sort non-trivial data with a function like this).

Upvotes: 1

Ashish Kumar
Ashish Kumar

Reputation: 581

You have to give an exit condition otherwise it will run forever.
Your code doesn't have any exit condition and hence it is running infinitely.
You are keep on calling quick_sort(array, len); but think of a scenario where you need to stop calling quick_sort(array, len);, and put condition for it(that will be your exit condition) this way you can stop running it infinite loop.

Upvotes: 0

Related Questions