while newNum < num_list[sorted_index] AND sorted_index > 0 {
num_list[sorted_index + 1] <-- num_list[sorted_index]
sorted_index <-- sorted_index - 1
}
// newNum is not smaller than the number at sorted_index.
// We found the place for the new number, so insert it.
num_list[sorted_index + 1] = newNum
}
end
To repeat, the variable number_index keeps track of where the algorithm is in the unsorted set of numbers.
The algorithm starts with the second number (number_index = 2). Then the algorithm compares the number
to the largest number that has been sorted so far, num_list[sorted_index]. If the number is smaller than the
previously sorted number, the algorithm moves the previously sorted number up one position in num_list, and
checks the new number against the next largest number in the previously sorted elements of num_list. Finally,
the algorithm will encounter a previously sorted number which is smaller than the number being inserted, or it will
find itself past the starting position of num_list. At that point, the number can be inserted into the num_list.
The algorithm completes when all of the positions in the num_list have been sorted.
To analyze the running time of the insertion sort, we note first that the performance will be proportional to
n, the number of elements to be sorted.
Pages:
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58