If the new number is smaller, then the algorithm shifts all the numbers up one position in the list. This
repeats, until eventually the algorithm will find that the new number is greater than the next sorted number, and
the algorithm will put the new number in the proper position next to the smaller number.
It??™s also possible that the new number is smaller than all of the numbers in the sorted set. The algorithm
will know that has happened when sorted_index becomes 0. In that case, the algorithm inserts the new
number as the first element in the sorted set.
CHAP. 2] ALGORITHMS 17
Insertion_Sort(num_list)
length <-- length of num_list
// At the start, the second element of the original list
// is the first number in the set of "unsorted" numbers.
number_index <-- 2
// We??™re done when we have looked at all positions in the list.
while(number_index <= length) {
// newNum is the no. being considered for sorting
newNum <-- num_list[number_index]
// sorted_index marks the end of previously sorted numbers.
sorted_index <-- number_index - 1
// From high to low, look for the place for the new number.
// If newNum is smaller than the previously sorted numbers,
// move the previously sorted numbers up in the num_list.
Pages:
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57