The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Sorting

Problem :-
Implement the Bubble sort algorithm.

Solution :-
This algorithm works by repeatedly iterating over the array elements, comparing each of the adjacent elements and swapping them if necessary. The iteration through the list continues until no swaps are required which indicates that the list is sorted.Complexity of the algorithm is O(n2).
We implement an optimized version of Bubble sort which is based on an observation that 'n'th pass through the array finds the 'n'th largest element in the list and puts it into its final position in the array.
Consider the following array { 7, 2, 5, 3, 4 }. Let's see how Bubble sort technique works :-

First Pass :-
{ 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( Swap 2 & 7 since 7 > 2 )
{ 2, 7, 5, 3, 4 } -> { 2, 5, 7, 3, 4 } ( Swap 5 & 7 since 7 > 5 )
{ 2, 5, 7, 3, 4 } -> { 2, 5, 3, 7, 4 } ( Swap 3 & 7 since 7 > 3 )
{ 2, 5, 3, 7, 4 } -> { 2, 5, 3, 4, 7 } ( Swap 4 & 7 since 7 > 4 )
Element 7 is placed in its final position in the sorted array.

Second Pass :-
{ 2, 5, 3, 4, 7 } -> { 2, 5, 3, 4, 7 } ( No swapping since 2 < 5 )
{ 2, 5, 3, 4, 7 } -> { 2, 3, 5, 4, 7 } ( Swap 3 & 5 since 5 > 3 )
{ 2, 3, 5, 4, 7 } -> { 2, 3, 4, 5, 7 } ( Swap 4 & 5 since 5 > 4 )
Element 5 is placed in its final position in the sorted array.

Third Pass :-
{ 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 2 < 3 )
{ 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 3 < 4 )
Element 4 is placed in its final position in the sorted array.

Fourth Pass :-
{ 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 2 < 3 )
Element 3 is placed in its final position in the sorted array.

Finally, after four passes, the array is sorted. We could optimize the algorithm further by exiting after the Third Pass in which there were no swaps. In general, we can exit early once we see a pass with no swaps.