Slide #1.

Overview of Sorting by Ron Peterson
More slides like this


Slide #2.

Variety of Algorithms • There are a lot of different approaches to sorting, not just different programs that use similar methods. • Donald Knuth’s, The Art of Computer Programming, Vol. 3, documents dozens of algorithmic methods for sorting. • Examples: bubble, insertion, selection, Shell, merge, heap, quick, & radix are all prefixes of names of sorts.
More slides like this


Slide #3.

More Sort Names • Bubble sort · Cocktail sort · Odd-even sort · Comb sort · Gnome sort · Quicksort · Selection sort · Heapsort · Smoothsort · Cartesian tree sort · Tournament sort · Cycle sort · Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting · Monkey-puzzle sort · Merge sort · Polyphase merge sort · Strand sort · American flag sort · Bead sort · Bucket sort · Burstsort · Counting sort · Pigeonhole sort · Proxmap sort · Radix sort · Flashsort · Bitonic sorter · Batcher odd-even mergesort · Timsort · Introsort · Spreadsort · UnShuffle sort · JSort · Spaghetti sort · Pancake sort
More slides like this


Slide #4.

Categories by Efficiency • Simple sorts – O(N^2) – Bubble, selection, insertion sorts • Intermediate sorts – Shell – O(N*log^2 N) • Efficient sorts – O(N*log N) – Quicksort, merge sort, Heap sort • Specialty sorts – Radix – O(C) (* # of digits per value)
More slides like this


Slide #5.

What you should know • For each sort discussed: – The name – Its efficiency • Average, best, and worst – How it works • Study the individual sorts in the book and look at the videos on the syllabus link
More slides like this


Slide #6.

2 more topics • Stable sorts: – Used for multi-key sorts like First/Last name – Does not change order within key group – Merge sort is typically a “stable” sort • STL sort algorithms: – Same interface for each (begin-it, end-it, [opl]) – Main approaches: • sort(..); stable_sort(..); make_heap(..), sort_heap(..); {plus a few tools to build others}
More slides like this