QuickSort in Java - using only one loop? Is it possible?


Forum Post 1 Answer 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);

}

}

- Saurabh September 26, 2015 | Flag |


Comment hidden because of low score. Click to expand.
0
of 0 vote

Will this help??
http: //techieme.in/easy-way-to-understand-quick-sort/
Do you consider recursion as another loop??

- techiemedotin September 27, 2015 | Flag Reply




Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More