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 Selection sort algorithm.

Solution :-
This algorithm is also known as in-place comparison sort algorithm and requires atmost n comparisons for an array with n elements. This algorithm works by finding the smallest element in the unsorted array arr [0 ... n-1] and swapping it with the element in the first position ( index 0 ). Next, we find smallest element in the subarray
arr [1 ... n-1] and swapping it with the element in second position ( index 1 ). We repeat this for rest of the array. This way after n-1 iteration, we get the final sorted array. Complexity of the algorithm is O(n2).
Consider the following array { 7, 2, 5, 3, 4 }. Let's see how Selection sort technique works :-

First Iteration :-
{ 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( Smallest element found in the array [ 0 ... 4 ] is 2 which is swapped with                                                           element at index 0 i.e 7 )
Second Iteration :-
{ 2, 7, 5, 3, 4 } -> { 2, 3, 5, 7, 4 } ( Smallest element found in the array [ 1 ... 4 ] is 3 which is swapped with                                                           element at index 1 i.e 7 )
Third Iteration :-
{ 2, 3, 5, 7, 4 } -> { 2, 3, 4, 7, 5 } ( Smallest element found in the array [ 2 ... 4 ] is 4 which is swapped with                                                           element at index 2 i.e 5 )
Fourth Iteration :-
{ 2, 3, 4, 7, 5 } -> { 2, 3, 4, 5, 7 } ( Smallest element found in the array [ 3 ... 4 ] is 5 which is swapped with                                                           element at index 3 i.e 7 )

Finally, after four iterations, the array is sorted.