##### 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

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

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