Sharang Gupta Sharang Gupta - 28 days ago 9
Java Question

I dont know why but only my middle element remains unsorted

For some reason the middle element of my array remains unsorted...

public class QuickSort {

public int a[];

public QuickSort(int[] a) {
this.a = a;
}

private void swap(int pos1, int pos2) {
int t = a[pos1];
a[pos1] = a[pos2];
a[pos2] = t;
}

private int partition(int low, int high) {
int i = low, j = low + 1, pivot = low;
while (j < high) {
if (a[j] <= a[pivot]) {
swap(++i, j);
}
j++;
}
swap(i, pivot);
return i;
}

private void sort(int low, int high) {
int i;
if (low >= high)
return;
else {
i = partition(low, high);
sort(i + 1, high);
sort(low, i - 1);
}
}

public String toString() {
StringBuilder sb = new StringBuilder("");
for (int i : a) {
sb.append(i);
sb.append("\n");
}

return sb.toString();
}

private static int[] generateRandomNumbers(int s) {

int a[] = new int[s];

for (int i = 0; i < s; i++) {
a[i] = new Random().nextInt(50);
}

return a;
}

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of elements");
int s = sc.nextInt();

QuickSort obj = new QuickSort(generateRandomNumbers(s));

System.out.println(obj.toString());

obj.sort(0, s - 1);

System.out.println("\n");
System.out.println(obj.toString());
}

}


The array is filled with randomly generated numbers, this is a standard quicksort algorithm
any help would be appreciated , i'm a novice programmer and have tried to debug this code for far too long...

Answer

Modify

swap(i+1, pivot);
return i+1;

and

int i = low-1, j = low, pivot = high;

also

if (low < high)
        {
            i = partition(low, high);
            sort(i + 1, high);
            sort(low, i - 1);
        }

works flawlessly after these changes.

Comments