Welcome to the first post of sorting algorithms. In this post we will see the first sorting algorithm for solving Problem # 1. The algorithm that we will analyze and implement is the Selection Sort. As we will see in future post, we follow the already mentioned structure in the introduction to this problem.
The Selection Sort is a sorting algorithm that requires Θ (𝑛^2) operations to sort a list of n elements. We will analyze the cost with more detail after seeing how it works. This sorting algorithm is based on simplicity aside efficiency. So if we need a sorting algorithm and we have to implement it quickly and with a small data Set (n<100.000), this is a good idea.
The operation is quite intuitive and easy to understand:
- Search the minimun element of the list.
- Swap that element with the first one.
- Search again the minimun element of the list without takinng into account the alredy sorted element (for now just the first).
- Swap that element with the second one.
- Repeat those steps changing each itereation the position of swaping in +1.
Taking the general case:
- Search the minimun element of the list from i (i included) to the end of the list. (i is initialized with the first position of the list).
- Swap the minimun with the i element.
- Increased i in 1.
- Repeat steps 1-3.
As we can see, i represents the first unsorted element of the list.
As always we will implement it in java. We’ll use ArrayList for the implementation, because access, placement (get() / set()) and add (add()) are require constant time. In addition to the comfort it provided us use this structure .
Once we know how the algorithm works and we have made it’s implementation, let’s move on to the analysis:
As we saw in the code, for each element of the array, we perform a search for the smallest element, but the length of the search, on each iteration, is reduced by 1 unit. This results on an arithmetic progression: (n – 1) + (n – 2) + … + 2 + 1. So is:
𝑓 (𝑛) = n (n – 1) / 2 ∈ Θ (n^2)
As we can see the cost of the algorithm is quadratic, expensive compared to other solutions we will see in future post.
In few words, is a simple algorithm, but has a high cost if we order many elements.
NOTE: Sorry for the late poosting on this post, have many projects yo do in between. From now on I will try to keep that 1 post per week on the series of Algorithm posts.
If you have any questions or suggestions do not hesitate to comment. See you on the next!