Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the elements one by one and sort them based on their values.
If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on. If we have total n elements, then we need to repeat this process for n-1 times.
It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.
Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required.
Following are the steps involved in bubble sort (for sorting a given array in ascending order):
Let's consider an array with values {5, 1, 6, 2, 4, 3}. Below, we have a pictorial representation of how bubble sort will sort the given array.
So as we can see in the representation above, after the first iteration, 6 is placed at the last index, which is the correct position for it.
Similarly after the second iteration, 5 will be at the second last index, and so on.
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp;
for(i = 0; i < n; i++)
{
for(j = 0; j < n-i-1; j++)
{
if( arr[j] > arr[j+1])
{
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
// print the sorted array
printf("Sorted Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[100], i, n;
// ask user for number of elements to be sorted
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
{
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
}
// call the function bubbleSort
bubbleSort(arr, n);
return 0;
}
Enter the number of elements to be sorted: 5
Enter element no. 1: 3
Enter element no. 2: 2
Enter element no. 3: 0
Enter element no. 4: 5
Enter element no. 5: 4
Sorted Array: 0 2 3 4 5
Although the above logic will sort an unsorted array, still the above algorithm is not efficient because as per the above logic, the outer for loop will keep on executing for 6 iterations even if the array gets sorted after the second iteration.
Data Structures
Data Structures Overview Arrays Linked List Stack Queue Priority QueueExpression parsing
Infix Notation Prefix Notation Postfix notation Notation ConversionHashing
Hash Table and Function Collision ResolutionSearching Techniques
Linear Search Binary Search Interpolation Search Fibonacci SearchSorting
Bubble Sort Bubble Sort in Depth Selection Sort Selection Sort in Depth Insertion Sort Insertion Sort in Depth Shell Sort Merge Sort Quick Sort Quick Sort in Depth Counting Sort Radix Sort Bucket SortTree
Trees and Graphs Binary Tree Types of Binary Trees Binary Search Tree N-ary Tree AVL Tree Red Black Tree Splay tree B tree B+ treeTree Search Traversal Techniques
Breadth First Search (BFS) Depth First Search (DFS) Inorder, Preorder and Postorder TraversalHeaps
Heaps Introduction Binary Heap Heap OperationsTrending
C Programming
Remember to follow community guidelines and don't go off topic.