Daily Archives: June 2, 2008

One-way QuickSort implemented in Java

Posted on by
Reply

The codes might be not optimized, and the first elements of all arrays are chosen as the pivots, which will cause a tremendous slow-down when the array is sorted already.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void swap(int[] ar, int a, int b){
	int tmp = ar[a];
	ar[a] = ar[b];
	ar[b] = tmp;
}
public static int partition(int[] a, int left, int right) {
	int pivot=a[left];
	int m=left;
	for(int i=left+1;i<=right;i++){
		if (a[i]<pivot){
			m++;
			swap(a, i, m);
		}	
	}
	swap(a, left, m);
	return m;
}
public static void quicksort(int[] a, int left, int right){
	if (left>=right)
	return;
	int pivotIndex = partition(a, left, right);
	quicksort(a, left, pivotIndex-1);
	quicksort(a, pivotIndex+1, right);
}