QuickSort in Java - using only one loop? Is it possible?
Hello,
All the implementations of Quicksort I searched on the internet uses nested loops, one parent loop and then inside 2 loops for each of the pointers, left and right. Given the logic of the quick sort, I was intrigued by the question that why is it not possible to write the QuickSort algorithm using only one while loop, where we push the left and right pointers to their next positions if possible using only the parent while loop?
I tried but it fails. If using only one loop for both pointers isn't possible, I would like to understand why behind it. There should be some logical/mathematical reasoning behind why we need to use separate loops for the left and right pointers?
Here is the code for my faulty attempt:
public class QuickSort {
public static void sort(int[] input){
sortArray(input,0,input.length-1);
}
public static void sortArray(int[] array, int p, int q){
int left, right, pivot;
pivot = p;
left = p+1;
right = q;
//end condition, if only 1 element is there in the array
if(p>=q){
return;
}
boolean leftMoved = false, rightMoved=false;
while(left <= right){
leftMoved = false;
rightMoved=false;
if(left< q && array[left] < array[pivot]){
left ++;
leftMoved = true;
}
if((left < right) && array[right] > array[pivot]){
right --;
rightMoved=true;
}
if(left < right && leftMoved==false && rightMoved==false){
//swap left and right
int temp = array[right];
array[right] = array[left];
array[left] = temp;
if(array[left]==array[right]){
left++;
}
}
}
//swap pivot and left, only if left is less than pivot, if not then it means pivot is already at it's right place.
if(array[pivot] > array[left]){
int temp = array[pivot];
array[pivot] = array[left];
array[left] = temp;
}
//now sort left side array
sortArray(array,p,left-1);
//and right side array
sortArray(array,left+1,q);
}
}
