|
Sorting
Input: n numbers <a1, a2, a3, ...,an>
Output: n numbers <a1¢, a2¢, a3¢, ...,an¢>
so that ai¢ £ ai+1¢
< 3, 7, 2, 5, > Input
< 2, 3, 5, 7 > Output
This particular example is an instance of the sorting problem.
An algorithm is correct if it solves the problem for EVERY INSTANCE of the problem. Incorrectness may be due to wrong or no answers.
Description of Algorithms is in Pseudocode.
Insertion Sort (one algorithm for sorting): "Add one card at a time to a sorted list" .
Insertion sort is an in place algorithm, i.e. memory is reused for the sorting (no temporary array). At most only a constant number of temporary elements are used.
Input: A = <a1, a2, a3, ...,an>
A[j] = aj
length[A] = n
Insertion-Sort(A)
1 for j ¬ 2 to length[A]
2 do key ¬ A[j]
3 Insert A[j] into the sorted sequence A[1..j-1].
4 i ¬ j - 1
5 while i > 0 and A[i] > key
6 do A[i + 1] ¬ A[i]
7 i ¬ i - 1
8 A[i + 1] ¬ key
Output: <a1¢, a2¢, a3¢, ...,an¢>
where a1¢ £ a2¢ £ a3 ¢£
... a£n¢
| 5 |
2 |
4 |
6 |
1 |
3 |
|
| 2 |
5 |
4 |
6 |
1 |
3 |
|
| 2 |
4 |
5 |
6 |
1 |
3 |
|
| 2 |
4 |
5 |
6 |
1 |
3 |
|
| 1 |
2 |
4 |
5 |
6 |
3 |
|
| 1 |
2 |
3 |
4 |
5 |
6 |
done |
The operation of Insertion-Sort() on the array A = < 5,2,4,6,1,3>. The position if index j is indicated in red.
Pseudocode Conventions:
Compound data (complicated data structures) are made up of attributes or fields.
e.g. If x and y are objects then y ¬x implies f [y] = f [x] for all fields f
f [x] ¬ 3 implies f [y] = 3 (like pointers work)
Parameters are passed by value:
Copies are sent to subpages. Originals in calling routine are NOT changed.
|
