Bubble Sort
Bubble Sort

i. Bubble sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

ii. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2) where n is the number of items.

Example: We take an unsorted array for our example.
15 12 27 18 22 30

Step 1: Bubble sort starts with very first two elements, comparing them to check which one is greater. In this case, value 15 is greater than 12, so swap operation will be performed.
12 15 27 18 22 30

Step 2: Next, we compare 15 with 27. Value 27 is greater than 15, so it is already in sorted locations.
12 15 27 18 22 30

Step 3: compression between 27 and 18. 18 < 27 so swap operation will be performed.
12 15 18 27 22 30

Step 4: compression between 27 and 22. 22 < 27 so swap operation will be performed.
12 15 18 22 27 30

Step 5: compression between 27 and 30. 27 < 30 so it is already in sorted locations.
12 15 18 22 27 30

Algorithm:

Array (A)
Begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort

Complexity:

The complexity of bubble sort is O(n2) in both worst and average cases, because the entire array needs to be iterated for every element.
Following are the Time and Space complexity for the Bubble Sort algorithm.
• Worst Case Time Complexity [ Big-O ]: O(n2)
• Best Case Time Complexity [Big-omega]: O(n)
• Average Time Complexity [Big-theta]: O(n2)
• Space Complexity: O(1)

Drawback:

Though bubble sort algorithm is quite popular, there are many other better algorithm than bubble sort. Specially, bubble sort should not be used to sort large data if performance matters in that program.

Program in C:

/*C Program To Sort data in ascending order using bubble sort.*/
#include
int main()
{
int data[100],i,n,step,temp;
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
for(i=0;i {
printf("%d. Enter element: ",i+1);
scanf("%d",&data[i]);
}

for(step=0;step for(i=0;i {
if(data[i]>data[i+1]) /* To sort in descending order, change > to < in this line. */
{
temp=data[i];
data[i]=data[i+1];
data[i+1]=temp;
}
}
printf("In ascending order: ");
for(i=0;i printf("%d ",data[i]);
return 0;
}

Output:

Enter the number of elements to be sorted: 6
1. Enter element: 12
2. Enter element: 3
3. Enter element: 0
4. Enter element: -3
5. Enter element: 1
6. Enter element: -9
In ascending order: -9 -3 0 1 3 13

Contributor's Info

Created: Edited:
0Comment
Bubble Sort

Buuble sort is a simple sorting algorithm in which the adjacent elements are swapped when they are not in order based on the user's preference(acsending/desceding) .If we have to sort n elements  there are two full loops(from initial position to final position) so thats why It's complexity for both the average and worst case is O(n^2) which is why most of the programmers don't use.

A pseudo code for ascending order sorting is:-

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   return list
end BubbleSort

Contributor's Info

Created:
0Comment