Searching and Sorting 577
Explanation The above program of selection sort uses nested loops. Using nested loops array
elements are compared with one another. The value of loop variable p is assigned to variable
small. The inner loop executes from (p+1) to num, in which the number present at array position
nums [small] if greater than nums [r], the location indicated by r is assigned to small. The next
i f () block carries swapping of elements. Thus, all array elements are compared and necessary
swapping is done.
16.8 BUBBLE SORT
Bubble sort is a commonly used sorting algorithm and it is easy to understand. In this type, two
successive elements are compared and swapping is done if the first element is greater than the
second one. The elements are sorted in ascending order. Though it is easy to understand, it is time
consuming.
The bubble sort is an example of exchange sort. In this method comparison is performed
repetitively between the two successive elements and if essential swapping of elements is done.
Thus, step-by-step the entire array elements are checked. It is different from the selection sort.
Instead of searching the minimum element and then applying swapping, two records are swapped
instantly upon noticing that they are not in order. Fig. 16.5 illustrates the exchange sort.
Let us consider the elements 9, 5,1, 4, and 3 for sorting under bubble sort.
1) In pass 1, first element 9 is compared with its next element 5. The next element is smaller than
the 9. Hence, it is swapped. Now the list is 5, 9, 1, 4, 3 again the 9 is compared with its next
element 1 the next element is smaller then the 9 hence swapping is done. The same procedure is
done with the 4 and 3 and at last we get the list as 5,1, 4, 3, 9.
2) In pass 2, the elements of pass 1 are compared. The first element 5 is compared with its next
element 1.5 and 1 are swapped because 1 is smaller than 5. Now the list becomes 1, 5, 4, 3, 9.
Next, 5 is compared with element 4. Again, the 5 and 4 are swapped. This process is repeater
until all successive elements are compared and if the succeeding number is smaller than the
present number then the numbers are swapped. The final list at the end of this pass is 1,4, 3, 5,
9.
3) In pass 3, the first element 1 is compared with the next element 4. The element 4 is having the
higher value than the first element 1, hence they remain at their original positions. Next 4 is
compared with the subsequent element 3 and swapped due to smaller value of 3 than 4.
4) At last, the sorted list obtained is as 1, 3, 4, 5, 9.
Fig. 16.5 Exchange sort
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.