Saurabh
BAN USERI'm good in Core Java, have good experience in Java/JEE stack. Looking to upgrade my knowledge here and prepare for some tough techie interviews.
Cheers!
- 1 Answer QuickSort in Java - using only one loop? Is it possible?
Hello,
- Saurabh September 26, 2015
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);
}
}| Flag | PURGE
Which code?
You should specify which code you want to run. It may happen that it may not give any error if it's pure java language code without referencing any external API, since java 1.6 didn't make any inherent changes in the java language itself (yes there were lot of other upgradations concerning GC and JVM optimizations but here we are talking about running the code on java 1.5).
If you want to compile the code on X env. and run on Y then you can specify the target and source options while using javac - explore javac more for this.
Working code.
- Saurabh June 16, 2016