Sorting using quicksort doesn't give sorted array

Question

I started learning algorithm in C++ and stuck with Quicksort. But I'm unable to get the bug in my code that is not sorting the array properly.

Here is the link to code or here is the code:

#include <iostream>
using namespace std;

void printArray(int array[], int len) {
  for (int i = 0; i < len; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

void swap(int* a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int arr[], int lo, int hi) {
  int pivot = arr[hi];
  int i = lo - 1;
  for (int j = lo; j < hi-1; j++) {
    if (arr[j] <= pivot) {
        i +=1;
        swap(&arr[i], &arr[j]);
    }
  }

  swap(&arr[i+1], &arr[hi]);
  return i+1;
  }

  void quicksort(int arr[], int lo, int hi) {
    if (lo < hi) {
      int p = partition(arr, lo, hi);
      quicksort(arr, lo, p-1 );
      printArray(arr, 8);
      quicksort(arr, p + 1, hi);
    }
  }

 int main() {
   int len;
   int array[] = {2,8,7,1,3,5,6,4};
   len = (sizeof(array)/sizeof(array[0]));
   quicksort(array, 0, len-1);
   printArray(array, len);
   return 0;
 }

I'm printing the array elements so that I can see the behavior of array elements.

You have a debugger, learn how to use it. That's usually working better than head scratching. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Aug 1, 2015 at 7:23

Andre Holzner · Accepted Answer · 2015-08-01 07:49:28Z

2

Your implementation looks very close to the pseudocode on Wikipedia (with j in partition(..) in your code being called i in the Wikipedia article and i in your code having the name storeIndex)

But there are two differences, one of which at least causes the algorithm to fail on your example:

for (int j = lo; j < hi-1; j++)

should be

for (int j = lo; j <= hi-1; j++)

the Wikipedia article says for i from lo to hi−1, inclusive hence the <= instead of <.

Another difference is that in your code you have

if (arr[j] <= pivot)

while the Wikipedia article has

if A[i] < pivotValue

so < instead of <= .

answered Aug 1, 2015 at 7:49

Andre Holzner

18.8k6 gold badges59 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Suraj Palwe Over a year ago

thanks for the help!! I didn't look to the iterator in foor loop! thanks again

TryinHard · Accepted Answer · 2015-08-01 08:11:08Z

1

Please change your for loop from:

for (int j = lo; j < hi-1; j++)

to

for (int j = lo; j < hi; j++)

or

for (int j = lo; j <= hi-1; j++)

The reason being the array must be handled right from lo to hi(inclusive).

But, in your attempt it was taking only

{lo, low+1, ..., hi-1}

into account instead of

{lo, low+1, ..., hi-1, hi}

edited Aug 1, 2015 at 8:11

answered Aug 1, 2015 at 7:52

TryinHard

4,1263 gold badges31 silver badges55 bronze badges

1 Comment

Suraj Palwe Over a year ago

Thanks for the help!!

Collectives™ on Stack Overflow

Sorting using quicksort doesn't give sorted array

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related