Loading [MathJax]/jax/output/HTML-CSS/jax.js
Close
Close Window

Show Source |    | About   «  17.20. Quick Hashing   ::   Contents   ::   17.22. Sorting Part 2  »

17.21. Sorting Part 1

17.21.1. Sorting Part 1

17.21.1.1. Sorting

  • Each record contains a field called the key.
    • Linear order: comparison.

  • Measures of cost:
    • Comparisons

    • Swaps

17.21.1.2. Insertion Sort

What would you do if you have a stack of phone bills from the past two years and you want to order by date? A fairly natural way to handle this is to look at the first two bills and put them in order. Then take the third bill and put it into the right position with respect to the first two, and so on.

17.21.1.3. Initial Step

Consider this start to the process.

1 / 11 Settings
<<<>>>

Insertion Sort starts with the record in position 1.

  1. 200
  2. 101
  3. 152
  4. 543
  5. 554
  6. 115
  7. 786
  8. 147
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.4. Analysis: Worst Case

1 / 24 Settings
<<<>>>

We first examine the worst case cost.

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.5. Analysis: Best Case

1 / 5 Settings
<<<>>>

Now we will consider the best case cost.

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.6. Analysis: Average Case

1 / 8 Settings
<<<>>>

Finally, consider the average case cost.

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.7. Bubble Sort

1 / 13 Settings
<<<>>>

Moving from left to right, compare adjacent elements and swap if the left one is bigger than the right one.

  1. 200
  2. 101
  3. 152
  4. 543
  5. 554
  6. 115
  7. 786
  8. 147
Proficient Saving... Error Saving
Server Error
Resubmit

1 / 10 Settings
<<<>>>

Moving from left to right, compare adjacent elements and swap if the left one is bigger than the right one.

  1. 100
  2. 151
  3. 202
  4. 543
  5. 114
  6. 555
  7. 146
  8. 787
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.8. Analysis

1 / 24 Settings
<<<>>>

What is the cost of Bubblesort?

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.9. Selection Sort

1 / 15 Settings
<<<>>>

Moving from left to right, find the element with the greatest value.

  1. 200
  2. 101
  3. 152
  4. 543
  5. 554
  6. 115
  7. 786
  8. 147
Proficient Saving... Error Saving
Server Error
Resubmit

1 / 13 Settings
<<<>>>

Second pass: moving from left to right, find the element with the second greatest value.

  1. 200
  2. 101
  3. 152
  4. 543
  5. 554
  6. 115
  7. 146
  8. 787
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.10. Analysis

1 / 40 Settings
<<<>>>

What is the cost for Selection Sort?

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

17.21.1.11. Summary

InsertionBubbleSelectionComparisons:Best CaseΘ(n)Θ(n2)Θ(n2)Average CaseΘ(n2)Θ(n2)Θ(n2)Worst CaseΘ(n2)Θ(n2)Θ(n2)Swaps:Best Case00Θ(n)Average CaseΘ(n2)Θ(n2)Θ(n)Worst CaseΘ(n2)Θ(n2)Θ(n)

17.21.1.12. Code Tuning (1)

  • General strategy: Test to avoid work
    • Balance test cost, success probability, work saved

  • “Optimizations” for quadratic sorts:
    • Insertion Sort shift vs swaps: Works

    • Selection Sort viewed as an optimization of Bubble Sort: Works

    • Selection Sort avoid self-swaps: Does not work

    • Bubble Sort “i” vs “1”: Works

    • Bubble Sort count comparisons/avoid unnecessary iterations: Does not work

    • Bubble Sort O(n) best case claim (Wikipedia): Bogus

17.21.1.13. Exchange Sorting

  • All of the sorts so far rely on exchanges of adjacent records: Inversions

1 / 16 Settings
<<<>>>

What is the average number of inversions?

Proficient Saving... Error Saving
Server Error
Resubmit

   «  17.20. Quick Hashing   ::   Contents   ::   17.22. Sorting Part 2  »

nsf
Close Window