Introducing Quick Sort

Question

#include<stdio.h> #include<iostream.h> #include<conio.h> void quicks(int *arr,int x,int pivot,int lo,int hi); void swap1(int *x,int *y); int main() { int *arr = new int[7]; arr[0] = 23; arr[1] = 3; arr[2] = -23; arr[3] = 45; arr[4] = 12; arr[5] = 76; arr[6] = -65; quicks(arr,7,0,1,6); for(int i = 0;i<7;i++) std::cout << arr[i] <<"\t"; getch(); return 0; } void quicks(int *arr,int x,int pivot,int lo,int hi) { int i = lo,j = hi; if(pivot < x-1) { while(i <= hi) { if(arr[i] <= arr[pivot]) i++; else break; } while(j >= lo) { if(arr[j] >= arr[pivot]) j--; else break; } if( i > j) { swap1(&arr[j],&arr[pivot]); lo = pivot+1; hi = x - 1; quicks(arr,x,pivot,lo,hi); } else if(i == j) { pivot = pivot + 1; lo = pivot+1; hi = x - 1; quicks(arr,x,pivot,lo,hi); } else if(i < j) { swap1(&arr[j],&arr[i]); lo = i + 1; hi = j - 1; quicks(arr,x,pivot,lo,hi); } } else { printf("\nDONE\n"); } } void swap1(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } 

Hi, I wrote a program for implementing Quick sort. But the program goes into an endless loop. In the Quicks function, while loops to increase and decrease i and j are a problem. Can someone tell me what's wrong with this QUick Sort implementation.

Answer 1

Make a quick dry start using your input and algorithm, you will notice that after a while you will come across an infinite loop.

You start the loop with quicks(arr,7,0,1,6); . Try instead to set the minimum element to the "rightmost", that is 0. This will certainly not solve your problem, since the algorithm seems really erroneous, and the situation does not change at all, and I am completely moving forward. You are trying to complicate a very simple task.

i will go from lo to pivot . And j from hi to pivot . After the pivot is in the right place, you move forward pivot and lo by 1 and repeat the process.

Take a look at this image, you will get an idea of ​​the required algorithm: