Section 7.3
7 Standard Algorithms
7.3 Internal Sorting
When a file is small enough to be held in the computer's memory an internal sort
can be used.
7.3.1 Insertion Sort
In order to convert an unsorted list to a sequential list we can take an item
out of the list, shuffle the other items along until a gap appears at the
appropriate place and insert our item. This is repeated for all items.
Example
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
|
5
|
3
|
8
|
6
|
2
|
Start with the item in position 2. Take it out of the list to position 0.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
3
|
5
|
|
8
|
6
|
2
|
Now start just to the left of the gap. Compare each item with the item in
position 0 and move it right if it is greater.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
3
|
|
5
|
8
|
6
|
2
|
Finally insert the item in position 0 in the gap.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
|
3
|
5
|
8
|
6
|
2
|
The third item is greater than the item in position 2 so nothing has to be done
and the number stays in the same position.
Next we move the fourth item into position 0.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
6
|
3
|
5
|
8
|
|
2
|
We now move the appropriate items right...
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
6
|
3
|
5
|
|
8
|
2
|
and move the item in position zero into the gap.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
|
3
|
5
|
6
|
8
|
2
|
Now we move the item in position 5 to position 0.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
2
|
3
|
5
|
6
|
8
|
|
We now move the appropriate items right...
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
2
|
|
3
|
5
|
6
|
8
|
and move the item in position zero into the gap.
|
Position:
|
0
|
1
|
2
|
3
|
4
|
5
|
|
Value:
|
|
2
|
3
|
5
|
6
|
8
|
Pseudocode
DIM card% (0 TO 5)
READ in the data
FOR position% = 2 TO 5
card%(0) = card%(position%)
DO UNTIL card%(movpos%) <= card%(0)
card%(movpos% + 1) = card%(movpos%)
movpos% = movpos% - 1
LOOP
card%(movpos% + 1) = card%(0)
NEXT position%
7.3.2 Bubble Sort
In this internal sort, adjacent values in a list are compared and swapped if
necessary.
Several passes are usually required to sort a list.
|
1st Pass
|
6
|
5
|
3
|
2
|
8
|
|
|
5
|
6
|
3
|
2
|
8
|
|
|
5
|
3
|
6
|
2
|
8
|
|
|
5
|
3
|
2
|
6
|
8
|
|
2nd Pass
|
5
|
3
|
2
|
6
|
8
|
|
|
3
|
5
|
2
|
6
|
8
|
|
|
3
|
2
|
5
|
6
|
8
|
|
3rd Pass
|
3
|
2
|
5
|
6
|
8
|
|
|
2
|
3
|
5
|
6
|
8
|
|
4th Pass
|
2
|
3
|
5
|
6
|
8
|
On the fourth pass no swaps are made so the sort is complete.
This sort is called a bubble sort because small (or light) numbers 'bubble' to
the top.
Pseudocode
DIMension card(1 to n)
READ in data
DO
swapped = 0
FOR position = 1
IF card(position) > card(position + 1) THEN
swap the cards
swapped = 1
END IF
NEXT position
LOOP UNTIL swapped = 0
7.3.3 Quick Sort
This algorithm is a fast sorting algorithm because it swaps items that are a
very large distance apart.
It works by picking a pivot item in the list and then moves every item that is
greater to one side and every item that is less is passed to the other side.
The two sub-divisions are then recursively passed one after another to the
Quick Sort algorithm.
The loop unravels when the sub-divisions are sorted.
When lengthy records or variable length records need to be sorted it is often
faster to sort only the key field.
In order to retrieve the full record details a pointer is added to each key
field value.
