[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Friday, 29-Mar-2024 16:59:52 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

Strategy

e.g. Selection sort

Now

Eventually i must reach N

©
L
.
A
l
l
i
s
o
n

Selection sort

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.
©
L
.
A
l
l
i
s
o
n

Insertion sort

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.

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

[lecturer: explain; fill in some entries; take notes]
  Selection sort Insertion sort
Time Best  
Average  
Worst  
Space Best  
Average  
Worst  
L. Allison

Sorting (1):   Summary:

Prepare: The faster O(n.log(n))-time [sorting algorithms].
© L.Allison, Friday, 29-Mar-2024 16:59:52 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/04sort1.shtml
Computer Science, Software Engineering, Science (Computer Science).