----- NEEDS JAVASCRIPT ON. -----
[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
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
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 . . .
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]
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
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).