Page 237 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes 11. A ................................ helps in connecting a key to the index of the hash table.
12. In ................................ hashing the process is carried out without the usage of an index
structure.

13.6 Some other Sorting Techniques

Let us now discuss some other sorting techniques.

13.6.1 Bubble Sort

Bubble sort is a simple sorting algorithm, which compares repeatedly each pair of adjacent
items and swaps them if they are in the incorrect order. At the first run, the highest element of
the list ends on the last place of the sorted list, and then, at the following run, the next highest
element ends on one position lower than the previous element and so on. The initial list is
finally sorted, when at a run, no swaps occur.
Even though it’s one of the simplest sorting algorithms, it’s almost never used in real life
because of the bad performance on large sorting lists. It’s easy to learn, so it’s one of the first
algorithms that people learn.

Example: Having the following list, let’s try to use bubble sort to arrange the numbers
from lowest to greatest:

Unsorted list: 9 2 0 1 4 6
First run:
(9 2 0 1 4 6) -> (2 9 0 1 4 6) : 9>2, swap occurs
(2 9 0 1 4 6) -> (2 0 9 1 4 6) : 9>0, swap occurs

(2 0 9 1 4 6) -> (2 0 1 9 4 6) : 9>1, swap occurs
(2 0 1 9 4 6)-> (2 0 1 4 9 6) : 9>4, swap occurs
(2 0 1 4 9 6) -> (2 0 1 4 6 9) : 9>6, swap occurs. The last two elements are in the right order, no swaps
occur, it’s the end of the first run.
Second run:
(2 0 1 4 6 9) -> (0 2 1 4 6 9) : 2>0, swap occurs
(0 2 1 4 6 9) -> (0 1 2 4 6 9): 2>1, swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 2<4, no swap occurs
(0 1 2 4 6 9) -> (0 1 2 4 6 9): 4<6, no swap occurs
(0 1 2 4 6 9) -> (0 1 2 4 6 9): 6<9, no swap occurs, it is the end of the list -> end of the second run.
The array is already sorted, but the algorithm doesn’t know that, so it requires another pass with
no swaps in order to know the elements are in the right place.
Third run:
(0 1 2 4 6 9) -> (0 1 2 4 6 9): 0<1, no swap occurs

(0 1 2 4 6 9) -> (0 1 2 4 6 9): 1<2, no swap occurs
(0 1 2 4 6 9) -> (0 1 2 4 6 9): 2<4, no swap occurs

230 LOVELY PROFESSIONAL UNIVERSITY