# Quicksort help.

Salim Sentosa

Greenhorn

Posts: 6

Colin Kenworthy

Ranch Hand

Posts: 88

posted 14 years ago

- 0

Quicksort relies on the principle that it is easier to sort 2 lists of half the size than it is to sort 1 big list. It is a generic term and there are many ways of implementing it, here's one...

1. Determine a value (X) roughly in the middle of the range of values you are sorting: Ideally this would have about half the values in the list > X and half <= X.

2. Now re-arrange the list so that all values less than or equal X are in the left half of the list and values greater than X are in the right half: Notice now that each value is in the correct half of the list but each half is unsorted, so to sort the big list we just need to sort each half.

3. Repeat steps 1 and 2 recursively for each half of the list.

By constantly dividing and re-arranging the list we must eventually end up with a whole load of little lists and you can stop dividing when the sub-list size is 1 or 2. A sublist of size 1 is already sorted, sorting a sub-list of size 2 is simple.

Hope I've not confused you...

1. Determine a value (X) roughly in the middle of the range of values you are sorting: Ideally this would have about half the values in the list > X and half <= X.

2. Now re-arrange the list so that all values less than or equal X are in the left half of the list and values greater than X are in the right half: Notice now that each value is in the correct half of the list but each half is unsorted, so to sort the big list we just need to sort each half.

3. Repeat steps 1 and 2 recursively for each half of the list.

By constantly dividing and re-arranging the list we must eventually end up with a whole load of little lists and you can stop dividing when the sub-list size is 1 or 2. A sublist of size 1 is already sorted, sorting a sub-list of size 2 is simple.

Hope I've not confused you...

It is sorta covered in the JavaRanch Style Guide. |