Sorting (1): Introduction

• Logic can prove that an algorithm / program is (always) correct
  
  
• [Sorting] is
  
  
  • very important in its own right, and
    
    
  • a good case-study for algorithm
    
    
    • development
      
      
    • complexity &
      
      
    • correctness (proof).

• Simple O(n²)-time algorithms
  
  
  • Bubble sort
    
    
  • Selection sort
    
    
  • Insertion sort
    
    
• faster O(n.log(n))-time algorithms   [--later]
  • Merge sort (and O(n)-space)
  • Quick sort (and O(log(n))-space)
  • Heap sort
  • Radix sort
  
  
• Each has a simple idea turned into a precise algorithm

Strategy

• How do you solve a big problem?
  
  
• One way:
  
  
  • Solve a smaller problem and
    
    
  • keep expanding solution until
    
    
  • it solves the big problem

e.g. Selection sort

• i = 1
  
  
• a[ 1 .. i - 1 ] is sorted and <= a[ i .. N ].   Well it's a start!

Now

• make i bigger and maintain invariant, `INV', true:
  
  
• INV: a[ 1 .. i - 1 ] is sorted & a[ 1 .. i - 1 ] <= a[ i .. N ]

Eventually i must reach N

• Invariant and i = N
  
  
• (a[ i .. i - 1 ] sorted and <= a[ i .. N ]) and (i = N)   implies . . .   a[ 1 .. N ] is sorted

Selection sort

• for i from 1 to N - 1 do
  
  
  • INV(i): a[1..i-1] sorted & a[1..i-1] <= a[i..N]
    
    
  • do_something
    
    
  • to make INV(i+1) true
    
    
• end_for

What can the ``do_something'' be?

Selection sort's loop body, do_something to find smallest element in a[ i .. N ]:

• smallest := i;
• aSmallest := a[i];
  
  
• for j from i+1 to N do
  
  
  • if a[j] < aSmallest then
    • smallest := j;
    • aSmallest := a[j]
      
      
  • end_if
• end_for
  
  
• swap a[ i ] and a[ smallest ]
• then, a[ 1 .. i ] sorted and <= a[ i + 1 .. N ],   i.e. INV( i + 1 )

• Selection sort's invariant
  
  
• a[ 1 .. i-1 ] sorted AND a[ 1 .. i-1 ] <= a[ i .. N ]
  
  
• is quite strong. What about the weaker:
  
  
• a[ 1 .. i-1 ] sorted
  
  
• ``weak'' is (sometimes) a good problem solving strategy . . . less conditions to satisfy.
  
  
• This leads to . . .

Insertion sort

• a[ 0 ] = -maxint;   // [ ? why ________ ? ]
  
  
• for i from 2 to N do
  
  
  • INV(i): a[ 1 .. i-1 ] is sorted
    
    
  • do_something (different)
    
    
  • to make INV(i+1) true
    
    
• end_for

Insertion sort's loop body, do_something, insert a[ i ] into a[ 1 .. i-1 ] at the "right" place:

• ai := a[ i ];
  
  
• j := i - 1;
  
  
• while a[ j ] > ai do
  • a[ j + 1 ] := a[ j ];   j--
• end_while
  
  
• ASSERT: a[ j ] <= ai < a[ j + 1 . . i ] and j >= 0
  
  
• a[ j + 1 ] := ai;
  
  

i.e. a[ 1 .. i ] is sorted,     i.e. INV( i + 1 )

Stability

A sorting algorithm is stable iff
the relative order of any two elements having the same key value is always maintained.

Selection sort is not stable; consider the swap, e.g. [2_a,2_b,1] -> [1,2_b,2_a].

Insertion sort is stable if it places the inserted element at the first valid position (stop on  <= ai).

An example of a situation where stability is useful is [_________________________].

Complexity

• Time
  
  
  • best case
    
    
  • average case
    
    
  • worst case
    
    
• Space
  
  
  • best case
    
    
  • average case
    
    
  • worst case
    
    

Sorting (1):   Summary:

• Algorithms develop from an intuition,
  
  
• must be made precise,
  
  
• logic can prove algorithms / programs correct.
  
  
• Sorting
  
  
• Time and space-complexity
  
  
• Best-, average- and worst-case performance