Lesson 21 - Learning Goals

21.1 Learn why sorting is useful

21.2 Learn several different Sorting Techniques

21.3 Learn how to compare different sorting algorithms

Sorting

Introduction

• General problem: Have an array of n data items (records) to be sorted on some key (field).
• e.g. n integers to be sorted in increasing order from smallest to largest:
• Want algorithms (methods, paradigms, …) to do this efficiently - compact and fast.
• Compact : little extra space needed
• Speed : running time of the algorithm [ Best Case? Worst Case? Average Case? ]

Order notation

• Allows description of the "running time" of the algorithm as a function of the size, n, of the input
• Algorithm is O(f(n)) if running time is bounded by c f(n) (where c is a positive constant) for all inputs of size n.
• Note: For large n, 0.001 n3 >> 1E6 n2 , so c "doesn't matter".
• e.g: A sorting algorithm technique is O(n^2) if its "running time" is proportional to n^2 for input arrays of length n.
• Algorithm is if running time is greater than d g(n) (where d is a positive constant) for some input of size n. O provides an upper bound on running time, while provides a lower bound.

For sorting:

• Running time can measure the number of swaps (exchanges of array elements) or the number of comparisons.
• Theoretical result: sorting problem is (n log n) (i.e. cannot do better)
• Practical result: There exist algorithms that work in O(n log n) time
• For small n, (e.g. n<100), some simple O(n^2) algorithms are faster than the elegant O(n log n) ones.

Bubble sort

• Imagine a vertical array, where smaller elements are "lighter" and bubble up to the top during sorting.
• Make repeated, bottom-to-top passes, exchanging adjacent elements as we go.
• On the first pass, the lightest element bubbles up to the top, etc.

A(1) small

A(2) .

A(3) .

… .

A(n) big

Bubble sort Algorithm

for i = 1 to n do

for j = n downto i + 1 do

if A[j] < A[j-1] then

Swap(A[j] , A[j-1])

• Note that, after i passes, the array elements A[1], A[2], … A[i] are in their final, sorted order.
• Need a total of n-1 passes, because if n-1 smallest elements are sorted, then so is the nth, largest one.
• This process requires O(n^2) swaps, O(n^2) comparisons, and only 1 extra record in the swap procedure.

Insertion Sort

• On pass i, the array element A[i] assumes its rightful position among the A[1], A[2], …, A[i-1], which were already sorted on previous passes.
• Basic Idea : For each I from 2 to n, move A[i] to position j <= i such that A[i] < A[k} for j k < i, and either A[i] A[j-1] or j = 1.
• Convenient to set A[0] = - to avoid checking j=1.

Algorithm for Insertion Sort

A[0] = -MaxInt

for i = 2 to n do begin

j = i

while A[j] < A[j-1] do begin

Swap(A[j], A[j-1])

j = j - 1

end

end

• Note that the partial results are not useful (element A[i may take any place amongst the elements A[1], A[2], …, A[i1] on pass i)
• Again requires O(n^2) swaps, O(n^2) comparisons, little extra space.

Selection sort

• On pass I, select the smallest array element A[j] amongst A[i], A[i + 1], …, A[n]
• Then, swap A[i] and A[j]
• This leaves elements A[1], A[2], …,A[i] in their final, sorted order.
• Running time is still O(n2), but there are only n-1 swaps; may be useful if records are large and swaps are "expensive"

Algorithm for Selection Sort

for i = 1 to n - 1 do begin

j = i

Min = A[i]

for k = i + 1 to n do

if A[k] < Min then begin

Min = A[k]

j = k

end

end

Swap( A[i], A[j])

end

Shell Sort

• On pass 1 sort n/2 pairs of elements (A[i], A[n/2 + i]), for 1 i n/2
• On pass 2 sort n/4 4-tuples of elements (A[I], A[n/4 + i], A[n/2 + i], A[3n/4 + i]), for 1 i n/4
• On pass j, sort n/2j 2j-tuples of elemts (A[i + kn/2j]), 0 k 2j - 1, for 1 i n/2j
• Stop when j > log2n
• Use insertion sort on the tuples in each pass, stopping once 2 elements in the proper order are encountered
• Analysis shows O(n^1.5) running time

Better algorithms

• Shell sort is reasonably fast and easy to implement
• Quicksort is O(n log n) in average case, but O(n2) in worst
• Heapsort is O(n log n) in average and worst case, but the constant is big, so worse algorithms better for "small" problems.