Learning toolsProgress & bookmarks
p. 435 · PDF 445
2-3-4 Quick Sort
Quick sort is a high-speed sorting algorithm. The reference value is selected from the data group to be sorted. Next, data is divided into the group that has values smaller than the reference value and the group that has values larger than the reference value. After that, the reference value is selected for each group, and they are divided in a similar manner. It is a recursive algorithm that repeatedly calls itself until the number of elements in each group becomes 1. By using array S (N=9) below, the algorithm of quick sort is considered.
Original source text
1
2
3
4
5
6
7
8
9
S
28
84
73
47
51
92
35
69
16
N
9
Source visual description
Original Quick Sort source layout. Source labels: 1; 2; 3; 4; 5.
The following is the image of a procedure of sorting array S in ascending order with quick sort. The element in the middle of the target data is used as the reference value.
p. 436 · PDF 446
Original source text
1) Divide S(1) through S(9) into the group that has values smaller than reference value
S(5) and the group that has values larger than reference value S(5).
51
Group of smaller values
Group of larger values
28
16
35
47
92
73
69
84
2) In the group of smaller values {S(1) through S(4)} and the group of larger values
{S(6) through S(9)}, decide the reference value for each group and split the groups.
51
16
73
28
35
47
69
92
84
3) In groups {S(2) through S(4), S(8) through S(9)} where there are more than one
elements, decide the reference value for each group and split the groups.
51
16
73
35
69
92
28
47
84
4) Sorting is complete when all groups have only one element.
16
28
35
47
51
69
73
84
92
Source visual description
Original Quick Sort source layout. Source labels: 1) Divide S(1) through S(9) into the group that has values smaller than reference value; S(5) and the group that has values larger than reference value S(5).; 51; Group of smaller values; Group of larger values.
Figure 7-31 shows the flowchart that is prepared on the basis of this concept. In Figure 7-31, quick sort process is recursively called with “QSORT (index of leftmost element, index of rightmost element)”.
p. 437 · PDF 447
Original source text
Figure 7-31 Quick sort
Source visual description
The original QSORT drawing contains the recursive range flowchart on the left and the split process on the right.
Original source text
[Merge sort]
Merge sort is a sorting algorithm that uses merge, which merges two sorted data items
into one without disrupting the order. This algorithm recursively performs a series of
processes of splitting and merging data.
93
32
18
67
: 1st merge
32
93
18
67
: 2nd merge
18
32
67
93
Source visual description
Original Quick Sort source layout. Source labels: : 1st merge; 32; 93; 18; 67.
Section progress
Original chapter exercises
Original chapter exercises →New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015