File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Quicksort help. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Quicksort help." Watch "Quicksort help." New topic

Quicksort help.

Salim Sentosa

Joined: Oct 29, 2001
Posts: 6
I need help with the Quicksort. Just the analogy or example.
I've found codes but couldn't get the general idea.
Thanks a lot!
Colin Kenworthy
Ranch Hand

Joined: Aug 06, 2001
Posts: 88
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...
Salim Sentosa

Joined: Oct 29, 2001
Posts: 6
(now try to digest what you said
I agree. Here's the link:
subject: Quicksort help.
It's not a secret anymore!