2-3-1 Selection Sort

1 
2 
3 
4 
5 
S 
28 
84 
73 
16 
51 
N
5 
··· Number of elements 

1) Select the minimum value from all elements, and let it be the first element S(1). 
S 
16 
84 
73 
28
51
2) Select the minimum value from the remaining elements, and let it be the 2nd 
element S(2). 
S 
16 
28 
73 
84
51
3) Select the minimum value from the remaining elements, and let it be the 3rd 
element S(3). 
S 
16 
28 
51 
84
73
4) Select the minimum value from the remaining elements, and let it be the 4th 
element S(4). 
→ The 5th element S(5) is automatically decided. (Sorting ends.) 
S 
16 
28 
51 
73
84

Figure 7-26  Selection sort (1) 
Figure 7-27  Selection sort (2) 

[Heap sort]  
Heap sort is a sorting algorithm that is an improved selection sort. It represents the data 
to be sorted with a heap, and then sequentially extracts the data of root. (Refer to p.414 
for the details of heap and heap sort.) 
In the array representation of a heap, the array of the root is placed at the 1st position. The 
left child node of the I-th element is placed in (2×I)-th position, while the right child 
node is placed at (2×I+1)-th position. By using this relation, a heap is reorganized while 
a parent node and a child node are compared and exchanged. 
1 
2 
3 
4 
5 
6 
H
83 
65 
48 
23 
59 
↓ Extract root (83) and reorganize. 
H
65 
59 
48 
23 
↓ Extract root (65) and reorganize. 
H
59 
23 
48