• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Quicksort help.

 
Salim Sentosa
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
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
Posts: 88
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks!
(now try to digest what you said
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic