hey this is my quicksort code and its working for normal cases but not for those where the array have same elements and in that case i considered putting elements which are equal to pivot to the left side of pivot.Could anyone please rectify the logical mistake in my code:
public class Solution {
public static int partition(int input[],int si, int ei) {
int pivot = input[si],pivotPos = si,count = 0;
// counting no of elements less than pivot so that space can be left empty to left of pivot
for(int i = pivotPos+1; i<input.length;i++) {
if(input[i]<=pivot)
count++;
}
//swapping pivot with the element
input[si] = input[si+count];
input[si+count] = pivot;
pivotPos = si+count;
// ensuring all elements to the left of pivot are less and to the right are more
int i = si, j = ei,temp;
while(i<pivotPos && j>pivotPos) {
if(input[i]<=pivot)
i++;
else {
if(input[j]>pivot)
j--;
else {
temp = input[i];
input[i] = input[j];
input[j] = temp;
i++;
j--;
}
}
}
return pivotPos;
}
public static void quickSort(int input[], int si, int ei) {
if(si>=ei)
return;
int pivotPos = partition(input,si,ei);
quickSort(input,si,pivotPos-1);
quickSort(input,pivotPos+1,ei);
}
public static void quickSort(int[] input) {
/* Your class should be named Solution
* Don't write main().
* Don't read input, it is passed as function argument.
* No need to print or return the output.
* Taking input and printing output is handled automatically.
*/
quickSort(input,0,input.length - 1);
}
}
input test case: 4 3 8 4 6 5 expected output: 3 4 4 5 6 8
my code gives stack overflow error from the point where partition function is being called
I think I have fixed your code while making minimal changes to your code style. You'll notice that I left some of your code in even though it isn't what we actually need to do. I left that in for your comparison.
public class QuickSort {
public static int partition(int input[],int si, int ei) {
int pivot = input[si],pivotPos = si,count = 0;
// counting no of elements less than pivot so that space can be left empty to left of pivot
for(int i = pivotPos+1; i<input.length;i++) {
if(input[i]<=pivot) {
count++;
}
}
// the above var count is not the info we need
// we need to know how many elements between si and ei (inclusive)
// are less than the value of pivot
// corrected logic here:
int smallerThanPivotCount = 0;
for (int i = si; i <= ei; i++) { // note that our logic includes ei
if (input[i] < pivot)
smallerThanPivotCount++;
}
//swapping pivot with the element
input[si] = input[si + smallerThanPivotCount];
input[si + smallerThanPivotCount] = pivot;
pivotPos = si + smallerThanPivotCount;
// next we are
// ensuring all elements to the left of pivot are less and to the right are more
int i = si, j = ei,temp;
while(i<pivotPos && j>pivotPos) {
if(input[i]<=pivot)
i++;
else {
if(input[j]>=pivot)
j--;
else {
temp = input[i];
input[i] = input[j];
input[j] = temp;
i++;
j--;
}
}
}
return pivotPos;
}
public static void quickSort(int input[], int si, int ei) {
if(si>=ei)
return;
int pivotPos = partition(input,si,ei);
quickSort(input,si,pivotPos - 1);
quickSort(input,pivotPos+1,ei);
}
public static void quickSort(int[] input) {
/* Your class should be named Solution
* Don't write main().
* Don't read input, it is passed as function argument.
* No need to print or return the output.
* Taking input and printing output is handled automatically.
*/
quickSort(input,0,input.length - 1);
}
}
I think your problem was just that you didn't correctly count the number of spaces forward you needed to shift the pivot. I have written code. I don't guarantee you 100% that it is correct, but it does pass my short list of unit tests, including your own example array. I suggest examining it yourself to understand the logic. Then clean up the extra stuff and make it your own. Cheers.