Bubble Sort

A sorting algorithm which splits the input array in 2 parts, the sorted part and the unsorted part. In every iteration, it finds the extremum element in the unsorted array using pairwise swapping and adds it to the sorted array.

Bubble Sort is a basic and simple sorting algorithm. It is named after the principle of bubbles in an container, as the larger bubbles move towards the top of the container and the smaller ones stay below.

Bubble sort starts sorting the array from right to left, unlike other sorting algorithms. This sorted array is actually in the opposite order than what the expected sorted order is supposed to be (while considering it from right to left).
Characteristic Value Notes
Average Time Complexity O(n2) Same for worst case
Best Time Complexity O(n) For a sorted array
Space Complexity O(1) No extra storage required

Advantages:
  1. Efficient sorting in best case, better than merge sort.

Disadvantages:
  1. Slower operation time as many swaps are performed in every iteration.
  2. Inefficient for arrays with large input due to poor time complexity.

Implementation


Bubble sort starts sorting the array in the opposite order of what is expected from the left to right : Ascending order: Sorted array from left to right is descending in nature
Descending order: Sorted array from left to right is ascending in nature

The logic of the bubble_sort() function is pretty simple, it works with 2 iterators:
  1. itr_1: Holds the index of the end of sorted array after which the extremum from the sorted array will be added after every iteration.
  2. itr_2: Traverses the unsorted array to find the extremum value in every iteration using pairwise swapping.

> Initially, end of sorted array = nth index. And the traversal will begin from the first index of array to the last for finding extremum using pairwise swapping.
> After an extremum is placed in the sorted array, move the itr_1 to the left by 1 and iterate over the unsorted array again.
> The first/0th element left in the unsorted array will automatically be in the sorted position.

Code for the following in C++: 
            
// function for bubble sort
void bubble_sort(int arr[], int n) {
	// i = itr_1 , j = itr_2
  for(int i = n; i >= 1; --i) {
		bool swapped = false;

		for(int j = 0; j < i - 1; ++j) {
			if(arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				swapped = true;
			}
		}
		
		if(!swapped) {
			break;
		}
	}
	return;
}