# Sorting Algorithms–Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. The strategy followed by bubble sort is to compare adjacent elements in the input list (e.g. array) and interchange them if they are out of order.

Each time the algorithm passes through the input list, the highest valued element gets positioned at the right place i.e. at the end of the list. This behaviour of bubbling elements to right position after every pass is responsible for naming this sorting technique as ‘Bubble Sort’.

Let us apply the Bubble sort algorithm on a integer array. The concept can be extended to other type of data as well.

Algorithm: Bubble Sort

Input: An array of integer elements (input) and the size of the array (n)

Output: In-place sorted array.

Description: At the core, Bubble Sort compares two consecutive elements of the list and interchanges them if they are out of order.

Pseudo-code:

`set swapped = true set i = 0 while i < n-1 && swapped == true do     swapped = false     for j=0 to n-1-i do         if input[j] > input [j+1] then             swap input[j] and input[j+1]             set swapped = true         endif     done done`

Performance:

The worst case performance of Bubble sort is categorized as O(n2) because the outer loop executes ‘n’ times, once for each element of the array. Each of these iterations cause the inner loop to execute ‘n-outer_loop_ counter’ times.

C++ source code for the above algorithm:

`void bubbleSort(int input[], int n) {     bool swapped = true;     for (int i = 0; i < n - 1 && swapped == true; i++) {         swapped = false;         for (int j = 0; j < n - 1 - i; j++) {             if (input[j] > input[j + 1]) {                 // Swap the values                 int temp = input[j];                 input[j] = input[j + 1];                 input[j + 1] = temp;                 // set swapped to indicate that elements were                 // swapped                 swapped = true;             } // endif         } // end of inner for     } // end of outer for } //end of method`

References: