Sorting Algorithm
71
Sorting Algorithm
First, let us consider sorting the following sequence in ascending order:
[3, 1, 2].
(4.41)
Of course, the answer is [1,2,3], but if the sequence were much longer, like [38, 90,
25, 74, 87, 26, 53, 86, 14, 89, . . . ], it would be difficult to immediately answer. When
we have to do this kind of work, one of the smartest ways is to write a program that
does the sorting. In other words:
[3, 1, 2] → (Some “mechanical” procedure) → [1, 2, 3].
(4.42)
The key term is “mechanical,” in that there should be no human thinking during
the procedure. 11 One way to implement this procedure is to pick up the input data
two by two in order of precedence in the sequence, and swap if the right number is
smaller, otherwise keep it as is:
[3, 1
1,3
, 2] → [1, 3, 2
2,3
] → [1, 2, 3].
(4.43)
It may not be complete just in a single trial. In another example, we find
[3, 2
2,3
, 1] → [2, 3, 1
1,3
] → [2, 1, 3],
(4.44)
which is incomplete, and in such a case, the same process is performed again from
the left:
(4.44) = [2, 1
1,2
, 3] → [1, 2, 3
2,3
] → [1, 2, 3].
(4.45)
Even if we do not want to judge whether or not “it has completed,” the procedure
should complete the sorting by repeating the same operation at least a number of
times that is same as the number of elements of the sequence.
11 A human is allowed to turn the gear by hand to put some energy to the machine.
71
Sorting Algorithm
First, let us consider sorting the following sequence in ascending order:
[3, 1, 2].
(4.41)
Of course, the answer is [1,2,3], but if the sequence were much longer, like [38, 90,
25, 74, 87, 26, 53, 86, 14, 89, . . . ], it would be difficult to immediately answer. When
we have to do this kind of work, one of the smartest ways is to write a program that
does the sorting. In other words:
[3, 1, 2] → (Some “mechanical” procedure) → [1, 2, 3].
(4.42)
The key term is “mechanical,” in that there should be no human thinking during
the procedure. 11 One way to implement this procedure is to pick up the input data
two by two in order of precedence in the sequence, and swap if the right number is
smaller, otherwise keep it as is:
[3, 1
1,3
, 2] → [1, 3, 2
2,3
] → [1, 2, 3].
(4.43)
It may not be complete just in a single trial. In another example, we find
[3, 2
2,3
, 1] → [2, 3, 1
1,3
] → [2, 1, 3],
(4.44)
which is incomplete, and in such a case, the same process is performed again from
the left:
(4.44) = [2, 1
1,2
, 3] → [1, 2, 3
2,3
] → [1, 2, 3].
(4.45)
Even if we do not want to judge whether or not “it has completed,” the procedure
should complete the sorting by repeating the same operation at least a number of
times that is same as the number of elements of the sequence.
11 A human is allowed to turn the gear by hand to put some energy to the machine.