Bubble Sort
- Bubble sort is a very simple sorting technique. However, this sorting algorithm is not efficient in comparison to other sorting algorithms.
- The basic idea underlying the bubble sort is to pass through the file sequentially several times. Each pass consists of comparing each element in the file with its successor (x[i] with x[i+1]) and interchanging the two elements if they are not in proper order.
- Example: Consider the following file,
25 57 48 37 12 92 86 33
In first pass, following comparisons are made:
x[o] with x[1] (25 with 57) No interchange
x[1] with x[2] (57 with 48) Interchange
x[2] with x[3] (57 with 37) Interchange
x[3] with x[4] (57 with 12) Interchange
x[4] with x[5] (57 with 92) No interchange
x[5] with x[6] (92 with 86) Interchange
x[6] with x[7] (92 with 33) Interchange
Thus, after the first pass, the file is on the order:
25 48 37 12 57 86 33 92
After first pass, the largest element (in this case 92) gets into its proper position within the array.
In general, x[n-i] is in its proper position after iteration i. The method is thus called bubble sort because each number slowly "bubbles” up to its proper position after each iteration.
Now after the second pass the file is:
25 37 12 48 57 33 86 92
Thus, after second pass, 86 has now found its way to the second highest position.
Since each iteration or pass places a new element into its proper position, a file of n elements requires no more than n-1 iterations.
The complete set of iterations is the following:
Original file: 25 57 48 37 12 92 86 33
Iteration 1: 25 48 37 12 57 86 33 92
Iteration 2: 25 37 12 48 57 33 86 92
Iteration 3: 25 12 37 48 33 57 86 92
Iteration 4: 12 25 37 33 48 57 86 92
Iteration 5: 12 25 33 37 48 57 86 92
Iteration 6: 12 25 33 37 48 57 86 92
Iteration 7: 12 25 33 37 48 57 86 92
Algorithm for Bubble Sort
This algorithm sorts the array list with n elements
Step1: Initialization,
Set i=0
Step2: Repeat steps 3 to 6 until i<n
Step3: Set j=0
Step4: Repeat step 5 until j<n-i-1
Step5: If list[j]>list[j+1]
Set temp = list[j]
Set list[j] = list[j+1]
Set list[j+1] = temp
j=j+1
End if
Step6: i=i+1
Step7: Exit
Efficiency of Bubble Sort
Sorting algorithms are analyzed in terms of the number of comparisons required fie. the major operation).
In bubble sort, the first pass requires (n-1) comparisons to fix the highest element to its location, the second pass requires (n-2)
comparisons, ..., kth pass requires (n-k) comparisons and the last pass requires only one comparison to be fixed at its proper position.
Therefore total number of comparisons:
f(n) = (n-1) + (n-2) +…+ (n-k) + … +3 + 2 + 1 = (n-1)*n/2
<1 *n^2
Thus ,f(n) = O(n^2) with g(n)=n^2 and C=1 whenever n>1.
In case of bubble sort,
Worst case complexity = Best case complexity = Average case
complexity = O(n^2) because the comparisons will always take place.
C Program For Bubble Sort
#include <stdio.h>
void bubble_sort(int[], int);
int main()
{
int list[100], n, i;
printf("\nHow many elements in the array:");
scanf("%d", &n);
printf("\nEnter %d values to sort:", n);
for (i = 0; i < n; i++)
scanf("%d", &list[i]);
bubble_sort(list, n);
printf("\nThe sorted list is:");
for (i = 0; i < n; i++)
printf(" %d\t", list[i]);
return 0;
}
void bubble_sort(int list[], int n)
{
int temp, i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (list[j] > list[j + 1])
if (list[j] > list[j + 1])
{
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
}
Comments
Post a Comment
Subscribe Us and Thanks for visiting blog.