[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:57:27 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

## 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(n2)-time algorithms

• faster O(n.log(n))-time algorithms   [--later]
• 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 ]:

 NB. Can get code from Algorithms web site.
• 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:

 NB. Can get code from Algorithms web site.
• 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 )

Eventually i = N + 1, terminates, and then a[ 1 .. N ] is sorted.

## 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. [2a,2b,1] -> [1,2b,2a].

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

[lecturer: explain; fill in some entries; take notes]
L. Allison

## Sorting (1):   Summary:

• Algorithms develop from an intuition,