Bubble Sort

Introduction to sorting

Bubble Sort

Bubble sort is one of the most basic and simplest sorting algorithm, it revolves around two principles of sorting comparing and swapping.

Note: We swap if the preceding term is greater than the later term and in the following example we are comparing the highlighted term.

Example :

( 1 ,  2 , 5 , 3 , 0 )

Pass 1:

( 1 , 2 ,  5 , 3 , 0 )  // No swap.
( 1 ,  2 , 5 , 3 , 0 ) // No swap.
( 1 ,  2 , 5 , 3 , 0 ) -> ( 1 ,  2 , 3 , 5 , 0 ) // Swap
( 1 ,  2 , 3 , 5 , 0 ) -> ( 1 ,  2 , 3 , 0 , 5 ) // Swap

After pass 1, we don't need to look at the last term at all since due to pass 1, the last term will always be the greatest number in the list.

Pass 2:

( 1 ,  2 , 3 , 0 ) 5 //No swap.
( 1 ,  2 , 3 , 0 ) 5 //No swap.
( 1 ,  2 , 3 , 0 ) 5 -> ( 1 ,  2 , 0 , 3 ) 5 //Swap.

Similarly in pass 3, we don't need to take a look at last term of the current list under consideration.

Pass 3:

( 1 ,  2 , 0 ) 3  5 //No swap.
( 1 ,  2 , 0 ) 3  5 -> ( 1 ,  0 , 2 ) 3  5 // Swap

Similarly in pass 4

Pass 4:

( 1 ,  0 ) 2  3  5 -> ( 0 ,  1 ) 2  3  5

Since next list will contain only one element , we know that the obtained list is sorted.

with the help of the example we can see an intuition of bubble sort that we basically move the largest number at the end of the list so we don't need to worry about it later, in the process sorting the current list.

Bubble Sort C++ Program:

	//
	// main.cpp
	// bubbleSort
	// Created by Sarvesh Bhatnagar on 05/07/18.
	// Copyright © 2018 introtoalgo.com. All rights reserved.
	//
	#include <iostream>
	using namespace std;
	//Two essential functions for bubble sort compare and swap
	bool compare(int a,int b){
	return a>b;
	}
	bool swapArr(int arr[],int i, int j, bool cmp){
	if (cmp) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	}else{
	}
	return cmp;
	}
	int main() {
	int arr[4] = {3,2,1,5};
	int sizeOfArr = 4;
	bool k = true;
	//Implementing bubble sort.
	while (k == true) {
	k = false;
	for (int i = 0; i<(sizeOfArr-1); i++) {
	if (swapArr(arr, i, (i+1), compare(arr[i], arr[i+1]))) {
	k = true;
	}else{
	}
	}
	if (k == true) {
	sizeOfArr = sizeOfArr-1;
	}
	}
	//Displaying the array
	for (int i= 0; i<4; i++) {
	cout<<arr[i]<<endl;
	}
	return 0;
	}

view raw bubbleSort.cpp hosted with ❤ by GitHub

-By Sarvesh Bhatnagar