Lesson 21 - Learning
Goals
21.1 Learn why
sorting is useful
21.2 Learn several
different Sorting Techniques
21.3 Learn how
to compare different sorting algorithms
Sorting
Introduction
- General problem: Have an
array of n data items (records) to be sorted on some key (field).
- e.g. n integers to be sorted
in increasing order from smallest to largest:
- Want algorithms (methods,
paradigms,
) to do this efficiently - compact and fast.
- Compact : little extra space
needed
- Speed : running time of the
algorithm [ Best Case? Worst Case? Average Case? ]
Order notation
- Allows description of the
"running time" of the algorithm as a function of the
size, n, of the input
- Algorithm is O(f(n)) if running
time is bounded by c f(n) (where c is a positive constant) for
all inputs of size n.
- Note: For large n, 0.001
n3 >> 1E6 n2 , so c "doesn't matter".
- e.g: A sorting algorithm
technique is O(n^2) if its "running time" is proportional
to n^2 for input arrays of length n.
- Algorithm is if running time
is greater than d g(n) (where d is a positive constant) for some
input of size n. O provides an upper bound on running time, while
provides a lower bound.
For sorting:
- Running time can measure
the number of swaps (exchanges of array elements) or the number
of comparisons.
- Theoretical result: sorting
problem is (n log n) (i.e. cannot do better)
- Practical result: There exist
algorithms that work in O(n log n) time
- For small n, (e.g. n<100),
some simple O(n^2) algorithms are faster than the elegant O(n
log n) ones.
Bubble sort
- Imagine a vertical array,
where smaller elements are "lighter" and bubble up to
the top during sorting.
- Make repeated, bottom-to-top
passes, exchanging adjacent elements as we go.
- On the first pass, the lightest
element bubbles up to the top, etc.
A(1) small
A(2) .
A(3) .
.
A(n) big
Bubble sort Algorithm
for i = 1 to n do
for j = n downto i + 1 do
if A[j] < A[j-1] then
Swap(A[j] , A[j-1])
- Note that, after i passes,
the array elements A[1], A[2],
A[i] are in their final,
sorted order.
- Need a total of n-1 passes,
because if n-1 smallest elements are sorted, then so is the nth,
largest one.
- This process requires O(n^2)
swaps, O(n^2) comparisons, and only 1 extra record in the swap
procedure.
Insertion Sort
- On pass i, the array element
A[i] assumes its rightful position among the A[1], A[2],
,
A[i-1], which were already sorted on previous passes.
- Basic Idea : For each I from
2 to n, move A[i] to position j <= i such that A[i] < A[k}
for j k < i, and either A[i] A[j-1] or j = 1.
- Convenient to set A[0] =
- to avoid checking j=1.
Algorithm for Insertion Sort
A[0] = -MaxInt
for i = 2 to n do begin
j = i
while A[j] < A[j-1] do begin
Swap(A[j], A[j-1])
j = j - 1
end
end
- Note that the partial results
are not useful (element A[i may take any place amongst the elements
A[1], A[2],
, A[i1] on pass i)
- Again requires O(n^2) swaps,
O(n^2) comparisons, little extra space.
Selection sort
- On pass I, select the smallest
array element A[j] amongst A[i], A[i + 1],
, A[n]
- Then, swap A[i] and A[j]
- This leaves elements A[1],
A[2],
,A[i] in their final, sorted order.
- Running time is still O(n2),
but there are only n-1 swaps; may be useful if records are large
and swaps are "expensive"
Algorithm for Selection Sort
for i = 1 to n - 1 do begin
j = i
Min = A[i]
for k = i + 1 to n do
if A[k] < Min then begin
Min = A[k]
j = k
end
end
Swap( A[i], A[j])
end
Shell Sort
- On pass 1 sort n/2 pairs
of elements (A[i], A[n/2 + i]), for 1 i n/2
- On pass 2 sort n/4 4-tuples
of elements (A[I], A[n/4 + i], A[n/2 + i], A[3n/4 + i]), for 1
i n/4
- On pass j, sort n/2j 2j-tuples
of elemts (A[i + kn/2j]), 0 k 2j - 1, for 1 i n/2j
- Use insertion sort on the
tuples in each pass, stopping once 2 elements in the proper order
are encountered
- Analysis shows O(n^1.5) running
time
Better algorithms
- Shell sort is reasonably
fast and easy to implement
- Quicksort is O(n log n) in
average case, but O(n2) in worst
- Heapsort is O(n log n) in
average and worst case, but the constant is big, so worse algorithms
better for "small" problems.
Go back to lecture menu
Go back to main page
Copyright © 1996 McGill University. All rights
reserved.