home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / c / snippets / sorts.txt < prev    next >
Encoding:
Text File  |  1995-03-13  |  3.3 KB  |  53 lines
  1. There are four kinds of sorts.  There are sorts that search, sorts that swap,
  2. sorts that separate, and sorts that don't compare one element to another.  In
  3. the first class are the insertion sort, the extraction sort, and the heap
  4. sort. In the second class are the quick sort and the merge sort.  In the
  5. third class are the bubble sort and the Shell sort.  In the last class are
  6. the Radix-Exchange sort and the Pigeon sort.  (These lists aren't all
  7. inclusive. In fact, I know I'm leaving some sorts out, but I just want to
  8. give examples of what's in each class.)
  9.  
  10. I won't talk about the last class because I don't find them particularly
  11. interesting.  Even though they are the fastest kind of sorts known, with O(N)
  12. sorts not only possible but practical in many cases, it is difficult to
  13. generalize them, and I'm fond of finding general solutions to general
  14. problems.
  15.  
  16. In the sorts that swap, the only variable is which elements are swapped.  The
  17. Shell sort starts by swapping elements that are far apart in hopes that any
  18. "large scale" disorder is eliminated quickly.  The bubble sort compares only
  19. those elements that are next to each other.  Each pair is compared and, if
  20. they are found to be out of order, they are swapped.
  21.  
  22. The sorts that separate work by understanding that it is a lot faster to sort
  23. smaller lists than bigger lists.  So, you seek to break up the lists into
  24. halves and then break up the halves and then break up the quarters, and so on
  25. until each piece is small enough to sort.  (Often, a program will just
  26. continue to break the list down until each piece has a length of one.  A list
  27. of one item is already sorted.  On the other hand, many programmers prefer to
  28. stop after the element size gets small enough.)
  29.  
  30. However, there is a choice to be made in this case.  Do you attempt to impose
  31. order on the list before or after you split it into parts.  The quick sort is
  32. a before sort.  The merge sort is an after sort.  When you quick sort a list,
  33. you choose a value, called the pivot, and you build your sublists such that
  34. all of the elements which have a key value less than the pivot go into one
  35. sublist and those elements which do not go into the other.  Then, you
  36. recursively sort each sublist and when that is done you simply append the
  37. "greater than" list to the "less than" list to make the whole sorted list.
  38. With a merge sort, you find the middle and break it there without any concern
  39. for the key values of the elements, recursively sort each sublist and then
  40. merge the two sorted lists back together into one big list.  (The real nice
  41. thing about the merge sort is you don't have to be able to pick a good pivot
  42. value in order for it to work well. Most of the algorithms for finding the
  43. best pivot values start "Sort the list...")
  44.  
  45. The insertion sort is what you do when you "build a sorted list."  Basically,
  46. you go through the unsorted list, and for each element, you find the place in
  47. the sorted list where it should go and put it there.  This process is
  48. repeated until there are no more elements in the unsorted list. The
  49. extraction sort looks through the unsorted list for the element with the
  50. biggest (or smallest) value and once it finds it, appends that element to the
  51. sorted list.  This process is repeated until there are no more elements in
  52. the unsorted list.
  53.