Okay, so we are convinced that if we have a sorted array, it takes a lot less time to find an element in it. But how do we get a sorted array? An arbitrary array is unlikely to be sorted. The algorithm of getting a sorted array out of an arbitrary array while keeping all the elements same, that is, by only rearranging the elements of an input array, is called sorting. There are a lot of algorithms for sorting. But in this chapter, we will start with a few simple ones that are not efficient. In the next chapter, we will explore efficient sorting algorithms.
This is the most natural algorithm for sorting. We choose each position of the array and find the element in the array that belongs in that position. The functional definition of selection sort is as follows:
Find the minimum element in an array
Swap this element with the first element of the array
Sort the rest of the array after the first element recursively
Finding the minimum element has the functional structure as...