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.
  
  
  
  
  

Go back to lecture menu

Go back to main page