I am trying to practice how to run a quick sort on an array. However, when I run my program the array isn't fully sorted(see output) and I am not totally sure where the problem might be. I think the error might be in the partition method.
package qs;
import java.util.Random;
public class Qs {
public static final Random ran = new Random();
public int[] array;
public int elements;
public Qs(int[] a){
this.array=a;
this.elements=a.length;
}
public void swap( int i, int j){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
private int partition(int[] a, int start, int end){
int index = start+ran.nextInt(end - start + 1); //set random index pivot value
int pivot = a[index];//sets the random pivot value
swap(index, end); // puts random pivot value at the end of array
for (int i= index = start; i < end; i++) {
if (a[index]<pivot) {
swap(index, i);
index++;
}
}
swap(index, end);
return index;
}
private void qsort(int[] a, int start, int end){
if(end > start){
int index = partition(a,start,end);
qsort(a, start, index - 1);
qsort(a, index + 1, end);
}
}
public void sort(){
qsort(array, 0, elements-1);
}
public void print(){
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] a ={5,23,69,55,448,3,78};
Qs q = new Qs(a);
System.out.println("Original Array");
q.print();
q.sort();
System.out.println("Sorted Array");
q.print();
}
}
Output from this program:
Original Array
5 23 69 55 448 3 78
Sorted Array
3 5 23 55 78 69 448
BUILD SUCCESSFUL (total time: 0 seconds)
int i= index = start;. It is horrible to read. Separate these assigments and the next guy who reads your code will thank you.