- 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).

- development

- very important in its own right, and

- Simple O(n
^{2})-time algorithms

- faster O(n.log(n))-time algorithms [--later]

- Each has a simple
**idea**turned into a precise algorithm

- How do you solve a big problem?

- One way:

- Solve a smaller problem and

- keep expanding solution until

- it solves the big problem

- Solve a smaller problem and

- 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

© L . A l l i s o n |

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

- INV(i):
a[1..i-1] sorted &
- end_for

What can the ``do_something'' be?

Selection
sort's loop body, *do_something*
to find smallest element in

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

- if a[j] < aSmallest then
- end_for

- swap a[ i ] and a[ smallest ]
- then, a[ 1 .. i ] sorted and <=
a[ i + 1 .. N ] ,i.e. INV( i + 1 )

© L . A l l i s o n |

- 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 . . .

- 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

- INV(i): a[ 1 .. i-1 ] is sorted
- end_for

Insertion sort's
loop body, *do_something*,
insert

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,

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

Insertion
sort is stable *if*
it places the inserted element at the *first* valid position
`<= ai`

)

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

- Time

- best case

- average case

- worst case

- best case
- Space

- best case

- average case

- worst case

- best case

Selection sort | Insertion sort | ||
---|---|---|---|

Time | Best | ||

Average | |||

Worst | |||

Space | Best | ||

Average | |||

Worst |

- 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

© L.Allison, Sunday, 28-Nov-2021 04:57:27 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/04sort1.shtml