Sorting

Examples

• 2

  Stable vs unstable sorting

  edit move example delete share 1

  Improvements requested by Sayakiss:

  • This was posted as an example, but it does not attempt to illustrate the topic. It should possibly be an edit to the topic, a separate topic, or deleted altogether. - jul 22 at 13:29

  Edit Example Delete Example

  2

  Consider a list of pairs:

  (1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
  

  A stable sorting of this list by the first element in each pair would be:

  (1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
  

  Because (9, 3) appears after (9, 7) in the original list as well.

  An unstable sorting would be:

  (1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
  

  Well-known stable sorts:

  • Merge sort
  • Insertion sort
  • Radix sort
  • Tim sort

  Well-known unstable sorts:

  • Heap sort
  • Quick sort

  edited Jul 21 at 19:57

  

  
• 0

  In place sorting vs Out of place sorting

  edit move example delete share 1

  Improvements requested by Sayakiss:

  • This was posted as an example, but it does not attempt to illustrate the topic. It should possibly be an edit to the topic, a separate topic, or deleted altogether. - jul 22 at 13:29

  Edit Example Delete Example

  0

  Let's sort the following array of integers using an in-place sort(Insertion sort in this case):

  5,3,4,7,8,1,9
  

  Step 1: (swapping 5 and 3 - only 1 place in memory required, at most)

  3,5,4,7,8,1,9
  

  Step 2: (swapping 5 and 4)

  3,4,5,7,8,1,9
  

  Steps 3-7: (swapping 1 with the bigger numbers consecutively)

  1,3,4,5,7,8,9
  

  Good examples of in-place sort algorithms are:

  • Insertion sort
  • Selection sort
  • Shell sort
  • Shaker sort

  And for the out-of-place sort algorithms we can mention:

  • Merge sort
  • Quick sort
  • Radix sort
  • Heap sort
  • Tree sort

  Note 1: Most of the sorting algorithms fall into the out-of-place category.

  Note 2: Some of the out-of-place algorithms can be implemented as an in-place sort, like Merge sort.

  created Jul 22 at 11:16