quickSort Algorithm

[john]

Can someone tell me where I can find how to impliment QuickSort Algorithm
in Java. I just want to learn the technique and practice. I appreciate
your help.

john

[zave]

"john" <john@cs.uwindsor.ca> wrote:
>
>Can someone tell me where I can find how to impliment QuickSort Algorithm
>in Java. I just want to learn the technique and practice. I appreciate
>your help.
>
>john


1. If the number of elements in Sort is 0 or 1, them return.
2. Pick any element in Sort. This element is called the pivot.
3. Partition Sort-{element} (the remaining element is Sort) into two disjoint
groups. L and R.
4. Return the result of Quicksort(L), followed by Quicksort(R).

part of the implementation would be....

int middle = low+high)/2;
if(a[middle].lessThen(a[low]))
swapReferences( a, low, middle);
if(a[high].lessThen(a[low]))
swapReferences(a, low, highh);
if(a[high].lessThen( a[middle]))
swapRefrences( a, middle, high);

for(int i = low, j=high-1; {
whild(a[++i].lessThen(pivot));
while(pivot.lessThen(a[--j]));
if(i<j)
swapReferences(a, j, i);
else
break;



Well this is an algorithm and part of the implementation for quick sort.
Hope this helps a little.

[Willy Van den Driessche]

Have a look at the code at :
http://users.skynet.be/wvdd2/Sorting/sorting.html
The code is in VB, but you should have no problem converting it to Java.
--
Van den Driessche Willy
For a work in progress :
http://users.skynet.be/wvdd2/index.html

[Stellan Soderstrom]

Hi,

This is an implementation of Quicksort that sorts iteger arrays.
The resulting, sorted list is stored in the same array as you pass
as a parameter to the quickSort method.

Good Luck,
Stellan


public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
}

public static void quickSort(int[] list, int lo, int hi) {
int pivot = lo;
int h = lo;
int tmp = 0;
if(hi - lo <= 0) {
return;
}
else if(hi - lo == 1) {
if(list[lo] > list[hi]) {
tmp = list[lo];
list[lo] = list[hi];
list[hi] = tmp;
}
return;
}
else {
for(int i = lo + 1; i <= hi; i++) {
if(list[i] > list[pivot] && pivot == h) {
h++;
}
else if(list[i] <= list[pivot]) {
// swich (p,h)
tmp = list[pivot];
list[pivot] = list[h];
list[h] = tmp;
// swich (p,i)
tmp = list[pivot];
list[pivot] = list[i];
list[i] = tmp;

pivot++;
h++;
}
else {
// nothing to do
}
}
quickSort(list, lo, pivot - 1);
quickSort(list, pivot + 1, hi);
}
}

"john" <john@cs.uwindsor.ca> wrote:
>
>Can someone tell me where I can find how to impliment QuickSort Algorithm
>in Java. I just want to learn the technique and practice. I appreciate
>your help.
>
>john