Monthly Archives: June 2008

quicksorting with stacks

Posted on by
Reply 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public void quicksort(int[] d, int lo, int hi){
	if(lo<hi){
		int pivotIndex=partition(d, lo, hi);
		quicksort(d,lo,pivotIndex-1);
		quicksort(d,pivotIndex+1,hi);
		}
	public int partition(int[] d,int lo, int hi){
		intStack smaller = new intStack();
		intStack larger = new intStack();
		int pivot = d[hi];
		for(int i=lo;i<hi;i++){
			if(d[i]<pivot)
				smaller.push(d[i]);
			else
				larger.push(d[i]);
		}
		int i=lo;
		while(!smaller.isEmpty()){
			d[i]=smaller.pop();
			i++;
		}
		d[i] = pivot;
		int pivotIndex = i;
		i++;
		while(!larger.isEmpty()){
			d[i] = larger.pop();
			i++;
		}
	return pivotIndex;
	}
}

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);
}