Video: The Sorter (A great song: You gotta know when to swap 'em...)
program sorting_methods;
const limit = 10;
var num_list, sorted_list : array [1..limit] of integer;
i, j, k, m, n : integer;
sort : char;
procedure bubble;
var i, j, temp: integer;
begin
for i := 1 to limit - 1 do
for j := i + 1 to limit do
if sorted_list [i] > sorted_list [j] then
begin
temp := sorted_list [i];
sorted_list [i] := sorted_list [j];
sorted_list [j] := temp;
end;
end;
procedure insertion;
var current, pointer, i, temp: integer;
begin
current := 1;
repeat
inc (current);
pointer := 1;
while (pointer < current) do
begin
if sorted_list[pointer] >
sorted_list[current] then
begin
temp :=
sorted_list[current];
for i :=
current downto pointer + 1 do
sorted_list[i] := sorted_list[i-1];
sorted_list[pointer] := temp;
end;
inc (pointer);
end;
until current = limit;
end;
procedure selection;
var i, j, max, temp: integer;
begin
for i := 1 to limit -1 do
begin
max := i;
for j := i + 1 to limit do
if sorted_list [max] > sorted_list
[j]
then
begin
temp :=
sorted_list [max];
sorted_list
[max]
:= sorted_list [j];
sorted_list
[j] :=
temp;
end;
end;
end;
procedure shell;
var i, j, temp, shellgap: integer;
begin
shellgap := 8;
repeat
for i := 1 to limit -shellgap do
if sorted_list [i] > sorted_list [i +shellgap] then
begin
temp := sorted_list [i];
sorted_list [i] :=
sorted_list [i
+ shellgap];
sorted_list [i + shellgap] :=
temp;
end;
shellgap := shellgap div 2;
until shellgap = 0;
end;
begin
writeln ('Enter ', limit, ' numbers for sorting');
for i := 1 to limit do
readln (num_list[i]);
for j := 1 to limit do
sorted_list[j] := num_list[j];
writeln ('Enter type of sort, b for bubble, i for insertion, s for selection, h for shell');
repeat
readln (sort);
if not (sort in ['b', 'h', 'i', 's']) then writeln ('Wrong code entered');
until sort in ['b', 'h', 'i', 's'];
case sort of
'b': bubble;
'i': insertion;
's': selection;
'h': shell;
end;
write ('Original list: ');
for k := 1 to limit do
write (num_list[k], ' ');
writeln;
write ('Reversed list: ');
for m := limit downto 1 do
write (num_list[m], ' ');
writeln;
write ('Sorted list: ');
for n := 1 to limit do
write (sorted_list[n], ' ');
readln;
end.
The four sorting methods shown here are variations on a theme - compare 2 values, if necessary switch them over using a temporary variable. We make a copy of the original list so we can preserve it for later use. We use global array variables and procedures without parameters because array parameters are generally reference parameters, that is they point to the address of the array so an array parameter becomes a pointer to a pointer and therefore rather point-less.
Brief algorithms (for an array of 5 data items):
Compare all pairs of values in the array made up of item 1 and every other item, 1 & 2, 1 & 3, 1 & 4, 1 & 5. This ensures item 1 is in correct place.
Compare item 2 with every other item: 2 & 3, 2 & 4, 2 & 5. This ensures item 2 is in the correct place.
Compare item 3 with every other item: 3 & 4, 3 & 5. This ensures item 3 is in the correct place.
Compare item 4 with every other item: 4 & 5. This ensures items 4 and 5 are in the correct place.
Thus:
for i := 1 to 4 do
for j := i + 1 to 5 do...
Note that the number of comparisons for a given number is n-1 + n-2 + n-3 ... For example, if n=5 then the number of comparisons is 4 + 3 + 2 + 1 = 10. The formula for this is (n^2-n)/2. The presence if n^2 means that the number of comparisons grows in a polynomial fashion so the algorithm is not efficient for large data sets. The number of comparisons are triangle numbers (see exercise 17). Some sort algorithms (merge and quick sort) grow in proportion to logarithm n (base 2): these are more efficient with large data sets than a bubble sort.
Note this alternative method: here.
Repeat
NoMoreSwaps ← true
For element ← 1 to NumberOfItems - 1 do
if list[element] > list[element + 1]
then
NoMoreSwaps← false
temp← list[element]
list[element]← list[element] + 1
list[element + 1]← temp
endif
endfor
until NoMoreSwaps = true
Start at second number in list, compare this with all items below it (3, 4 & 5), inserting in correct place.
Move to third number and compare this with items below it, moving if necessary.
Move to fourth number and compare this with items below it, moving if necessary.
When a move is required the current item is stored in temp, the other items are moved up one and the temp value is stored in the free location.
Dry run. Array = 5 4 7 3 6, limit=5
c = 2, p = 1
Loop: while p < c do:
if list[1] > list[2] then swap them
5 > 4 so swap:
temp = list[c] (value 4)
for i := c(2) downto p+1(2) do
contents
of list[i(2)] become list[i-1(1)]: 5 5 7 3 6 (5 overwrites 4 at cell 2)
copy temp to list[p]: 4 5 7 3 6 (4 overwrites 5 at
cell 1)
inc (p): c = 2, p=2
c = limit is false so repeat loop continues
inc c: c = 3, p = 1 list = 4 5 7 3 6
Loop: while p < c do:
if list[1] > list[3] then swap them
4 < 7 so no swap
inc (p): p=2, c = 3
if list[2] > list[3] then swap them
5 < 7 so no swap
inc (p): p=3, c = 3
c = limit is false so repeat loop continues
inc c: c = 4, p = 1, list = 4 5 7 3 6
Loop: while p < c do:
if list[1] > list[4] then swap them
4 > 3 so swap:
temp = list[c] (value 3)
for i := c(4) downto p+1(2) do
contents of list[i(4)] become list [i-1(3)]: 4 5 7 7 6
(7 overwrites 3 at cell 4)
contents of list[i(3)] become list [i-1(2)]: 4 5 5 7 6
(5 overwrites 7 at cell 3)
contents of list[i(2)] become list [i-1(1)]: 4 4 5 7 6
(4 overwrites 5 at cell 2)
copy temp to list[p]: 3 4 5 7 6 (3 overwrites 4 at
cell 1)
inc (p): p=2, c = 4, list = 3 4 5 7 6
if list[2] > list[4] then swap them
4 < 7 so no swap
inc (p): p=3, c = 4, list = 3 4 5 7 6
if list[3] > list[4] then swap and inc (p).
5 < 7 so no swap
inc (p): p=4, c = 4, list = 3 4 5 7 6
c = limit is false so repeat loop continues
inc c: c = 5, p = 1, list = 3 4 5 7 6
Loop: while p < c do:
if list[1] > list[5] then swap and inc (p)
3 < 6 so no swap
inc (p): p=2, c=5
if list[2] > list[5] then swap and inc (p)
4 < 6 so no swap
inc (p): p=3, c=5
if list[3] > list[5] then swap and inc (p)
5 < 6 so no swap
inc (p): p=4, c=5
if list[4] > list[5] then swap and inc (p)
7 > 6 so swap:
temp = list[c] (value 6)
for i= c(5) downto p+1(5) do
contents of list[i(5)] become list [i-1(4)]: 3 4
5 7 7
copy temp to list[p]: 3 4 5 6 7
inc (p): p=5, c = 5, list = 3 4 5 6 7
c = limit is true so repeat loop stops, routine is finished.
Note that a for loop of the form for i := 1 to 1 do... or for i := 1 downto 1... will execute once. The question asked is whether the value of i is greater than the limit specified, if not the code inside the loop is executed. i is then incremented so 2 > 1 and the loop finishes.
Find the largest item in a list
Move this to the top of the list
Repeat until list is sorted
Same mechanism as Bubble sort but gap between numbers is wider e.g. 16 and falls with each pass through the process e.g. 8, 4, 2. In some data sets this may reduce the number of moves required, thus saving time.