Highlighted text? Practice this concept. Highlighted passages and figures open related questions.
Practice related questions (1)Progress & bookmarks
Current section
2-3-2 Bubble Sort
p. 429
Practice this section 1 linked exam question with default filters
Progress
Not marked complete
Related questions in this lesson 1
Adjacent exchanges in bubble sort1p. 429 · PDF 439
2-3-2 Bubble Sort
Original source text
1
2
3
4
5
S
28
84
73
16
51
N
5
··· Number of elements
Source visual description
Original Bubble Sort source layout. Source labels: 1; 2; 3; 4; 5.
The procedure of sorting array S in ascending order with bubble sort is as shown below. The process of repeating comparison/exchange from the first element up to the last element is called one round of path.
p. 430 · PDF 440
Original source text
1) Make the 1st comparison/exchange in order from the first element.
→ Decide the 5th element S(5).
S
28
73
16
51
84
2) Make the 2nd comparison/exchange in order from the first element.
→ Decide the 4th element S(4).
S
28
16
51
73
84
3) Make the 3rd comparison/exchange in order from the first element.
→ Decide the 3rd element S(3).
S
16
28
51
73
84
4) Make the 4th comparison/exchange in order from the first element.
→ Decide the 2nd element S(2).
→ The 1st element S(1) is automatically decided. (Sorting ends.)
S
16
28
51
73
84
Source visual description
Original Bubble Sort source layout. Source labels: 1) Make the 1st comparison/exchange in order from the first element.; → Decide the 5th element S(5).; S; 28; 73.
In this explanation, last elements are decided one by one and are removed from the scope of sorting. The path is repeated until positions of all elements are decided. In Figure 7-28, this algorithm is implemented by reducing N elements one by one for each round of a path. On the other hand, if exchange does not occur even once in one round of a path, it means that all elements are arranged in the correct order and sorting ends. Figure 7-29 shows the method that uses the value of variable FLG (0: initial state, 1: exchange occurred) and terminates the process if exchange does not occur. When efficiency is important, these two methods can also be used in combination. Please think about what kind of flowchart it turns into.
p. 431 · PDF 441
Original source text
Figure 7-28 Bubble sort (1)
Figure 7-29 Bubble sort (2)
Source visual description
The original bubble-sort charts compare adjacent elements and retain the exchange steps. The second chart also uses FLG.
p. 432 · PDF 442
Original source text
[Shaker sort]
Shaker sort is a sorting method that is obtained by improving bubble sort. Bubble sort
compares/exchanges adjacent elements in order from the smaller element number, while
shaker sort compares/exchanges adjacent elements in order from the smaller element
number and then compares/exchanges in order from the larger element number. Since
elements move alternately from a smaller number to a larger number and a larger number
to a smaller number, it is called shaker sort. However, efficiency does not improve that
much.
S
28
73
16
51
84
S
16
28
73
51
84
S
16
28
51
73
84
Source visual description
Original Bubble Sort source layout. Source labels: S; 28; 73; 16; 51.
Section progress
Original chapter exercises
Original chapter exercises →New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015