Learning toolsProgress & bookmarks
p. 432 · PDF 442
2-3-3 Insertion Sort
Insertion sort is a sorting algorithm that divides the data into the sorted part and elements before sorting, and then inserts data so that the order of the sorted part is not disturbed. By using array S (N=5) that is used in selection sort, the algorithm of insertion sort is considered. This algorithm sorts array S in ascending order where array S has N elements where data is recorded.
Original source text
1
2
3
4
5
S
28
84
73
16
51
N
5
··· Number of elements
Source visual description
Original Insertion Sort source layout. Source labels: 1; 2; 3; 4; 5.
The procedure of sorting array S in ascending order with insertion sort is as follows:
p. 433 · PDF 443
Original source text
1) Assume that the 1st element has already been sorted.
S
28
84
73
16
51
2) In the sorted part (1-1), insert “84” from the elements before sorting.
S
28
84
73
16
51
3) In the sorted part (1-2), insert “73” from the elements before sorting.
S
28
73
84
16
51
4) In the sorted part (1-3), insert “16” from the elements before sorting.
S
16
28
73
84
51
5) In the sorted part (1-4), insert “51” from the elements before sorting.
→ There is no element before sorting. (Sorting ends.)
S
16
28
51
73
84
Source visual description
Original Insertion Sort source layout. Source labels: 1) Assume that the 1st element has already been sorted.; S; 28; 84; 73.
In insertion sort, for inserting data in the sorted part in ascending order, comparison is made in order from the last element of the sorted part, and exchange is repeated until a value smaller than the inserted data is found or no comparison element is left (or exchange is performed up to the first element). In step 5) of the above example, the process of inserting element “51” is shown as follows:
Original source text
* In the sorted part (1-4), insert “51” from the elements before sorting.
S
16
28
73
84
51
1) Since “84 > 51”, exchange two elements.
S
16
28
73
51
84
2) Since “73 > 51”, exchange two elements.
S
16
28
51
73
84
3) Since “28 < 51”, the insertion position is decided.
Source visual description
Original Insertion Sort source layout. Source labels: * In the sorted part (1-4), insert “51” from the elements before sorting.; S; 16; 28; 73.
p. 434 · PDF 444
Figure 7-30 shows the flowchart that is prepared on the basis of this concept. In Figure 7-30, the first element (i.e., data to be inserted) before sorting is managed with variable J.
Original source text
Figure 7-30 Insertion sort
Source visual description
The original insertion-sort chart retains its selected element, insertion search, shifts and index updates.
p. 435 · PDF 445
Original source text
[Shell sort]
Shell sort is a sorting technique that is an improved insertion sort. Data to be sorted is
extracted at regular intervals (i.e., gaps), and the data is sorted by using insertion sort. The
gap size is gradually reduced, and the process is repeated until it becomes 1. It is a very
efficient sorting technique where no large movement of data is required.
1) Gap = 4
S
28
84
73
47
51
92
35
69
16
2) Gap = 2
S
16
84
35
47
28
92
73
69
51
3) Gap = 1
S
16
47
28
69
35
84
51
92
73
Source visual description
Original Insertion Sort source layout. Source labels: S; 28; 84; 73; 47.
Section progress
Original chapter exercises
Original chapter exercises →New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015