UNIT IV
SORTING AND SEARCHING ALGORITHMS
Bubble sort, insertion sort, radix sort, quick sort, merge sort, shell sort etc Linear Search,
binary search
BUBBLE SORT
Bubble sort is a basic algorithm for arranging a string of numbers or
other elements in the correct order.
The metihod works by examining each set of adjacent elements in
the string, from left to right, switching their positions if they are out
of order.
As the algorithm progresses, smaller value items “bubble” to the top
of the list, this is the reason for naming the algorithm as bubble sort.
10 9 11 6 15 2
In the above example, let us take the first element for sorting the
entire list.
The very first element is the bubble element.
Take the first element in the series and is compared with the next
element. If the first element is smaller than the next element, swap
the values.
In case, the next element is not smaller then there is no change in
the list, the algorithm proceeds to the next value to compare.
9 10 11 6 15 2
Now, the bubble element is still 10.
Now, the position of 10 is changed from 1 to 2 and the bubble is
compared with the next element 11.
As 11, is greater than 10, the position of 10 is not changed as it is
lower, the bubble is shifted to 11.
,11 becomes the bubble.
9 10 11 6 15 2
Now the bubble is compared with 6, as 6 is lower, the values are
swapped.
9 10 6 11 15 2
Now the bubble is compared with the next value 15, as 11 is lower
there is no change in the list, but bubble is shifted to the next
number that is 15.
9 10 6 11 15 2
Now the bubble is compared with the next element, as the value 2
is lower than the bubble, the values are swapped.
9 10 6 11 2 15
All the above processes are taken as Pass 1.
After Pass1, however bigger the list is the maximum value will
reach its right position.
In the next pass, the last value (15) that has reached its right
position is not compared.
If the list is of ‘n’ size, n-1 value will be considered for the next pass.
9 10 6 11 2 15
Now, in the second pass, start from the beginning of the list.
9 becomes the bubble and is compared to the next value 10.
As the value is smaller than 10, no change happens and the bubble
is shifted to 10.
, 9 10 6 11 2 15
The bubble is compared with the next element 6, as the value is
lower, the values are swapped.
9 6 10 11 2 15
Still, the bubble is 10 and is compared with the next value.
The value 11 is greater than 10, therefore, no change happens in
the list and the bubble is shifter to 11.
9 6 10 11 2 15
Now, the bubble is compared to the next value 2.
As 2 is lower than 11, the values are swapped.
9 6 10 2 11 15
This is the end of Pass 2. By its ends, the second largest value in
the list, 11 has come to its actual position.
In Pass 3, n-2 elements will be considered. That is out of 6, only 4
elements will be considered.
9 6 10 2 11 15
The algorithm starts with the first element, 9 which is the bubble.
The bubble is compared with the next element 6, as the value is
lower than the bubble, they are swapped and nine continues to be
the bubble.
6 9 10 2 11 15
SORTING AND SEARCHING ALGORITHMS
Bubble sort, insertion sort, radix sort, quick sort, merge sort, shell sort etc Linear Search,
binary search
BUBBLE SORT
Bubble sort is a basic algorithm for arranging a string of numbers or
other elements in the correct order.
The metihod works by examining each set of adjacent elements in
the string, from left to right, switching their positions if they are out
of order.
As the algorithm progresses, smaller value items “bubble” to the top
of the list, this is the reason for naming the algorithm as bubble sort.
10 9 11 6 15 2
In the above example, let us take the first element for sorting the
entire list.
The very first element is the bubble element.
Take the first element in the series and is compared with the next
element. If the first element is smaller than the next element, swap
the values.
In case, the next element is not smaller then there is no change in
the list, the algorithm proceeds to the next value to compare.
9 10 11 6 15 2
Now, the bubble element is still 10.
Now, the position of 10 is changed from 1 to 2 and the bubble is
compared with the next element 11.
As 11, is greater than 10, the position of 10 is not changed as it is
lower, the bubble is shifted to 11.
,11 becomes the bubble.
9 10 11 6 15 2
Now the bubble is compared with 6, as 6 is lower, the values are
swapped.
9 10 6 11 15 2
Now the bubble is compared with the next value 15, as 11 is lower
there is no change in the list, but bubble is shifted to the next
number that is 15.
9 10 6 11 15 2
Now the bubble is compared with the next element, as the value 2
is lower than the bubble, the values are swapped.
9 10 6 11 2 15
All the above processes are taken as Pass 1.
After Pass1, however bigger the list is the maximum value will
reach its right position.
In the next pass, the last value (15) that has reached its right
position is not compared.
If the list is of ‘n’ size, n-1 value will be considered for the next pass.
9 10 6 11 2 15
Now, in the second pass, start from the beginning of the list.
9 becomes the bubble and is compared to the next value 10.
As the value is smaller than 10, no change happens and the bubble
is shifted to 10.
, 9 10 6 11 2 15
The bubble is compared with the next element 6, as the value is
lower, the values are swapped.
9 6 10 11 2 15
Still, the bubble is 10 and is compared with the next value.
The value 11 is greater than 10, therefore, no change happens in
the list and the bubble is shifter to 11.
9 6 10 11 2 15
Now, the bubble is compared to the next value 2.
As 2 is lower than 11, the values are swapped.
9 6 10 2 11 15
This is the end of Pass 2. By its ends, the second largest value in
the list, 11 has come to its actual position.
In Pass 3, n-2 elements will be considered. That is out of 6, only 4
elements will be considered.
9 6 10 2 11 15
The algorithm starts with the first element, 9 which is the bubble.
The bubble is compared with the next element 6, as the value is
lower than the bubble, they are swapped and nine continues to be
the bubble.
6 9 10 2 11 15
