What is a Selection Sort Algorithm?
A Selection Sort Algorithm is one of the simplest types of sorting algorithm currently in use. However, if the coder doesn’t understand the concepts behind the algorithm, even this simple tool can cause issues. As with any program, both positive and negative issues must be understood before the algorithm is used successfully.
Why Use a Sorting Algorithm?
First, let’s examine the situation in which the coder will need a sorting algorithm. When the coder is confronted by a list or an array, and needs to put it in a particular order (for example, when a list needs to be placed in alphabetical order, or when an array needs to be placed in numeric order), then a sorting algorithm must be used in order to generate the sorted list that the coder needs.
The coder may choose from a number of algorithms which would help in this situation, and each algorithm has both benefits and drawbacks. Selection sort is an algorithm of this type. However, selection sort is not used very often, for a number of reasons.
Selection Sort—How Does it Work?
First, let’s examine exactly what type of algorithm the selection sort is. A selection sort algorithm is an in-place sort, which means that it does not partition a large list or array into smaller pieces and then work with them simultaneously. In other words, the selection sort algorithm does not use divide-and-conquer, unlike a number of other sorting algorithms, including quicksort.
Instead, selection sort runs two loops at the same time. The first loop consists of numbers that the selection sort has yet to sort, while the second loop consists of numbers that have been sorted. The first loop goes through all of the numbers in an array or list and then takes the lowest number (or
number with least value) and then places it in the second loop. These actions are repeated until the list is sorted.
Selection Sort– Examples In Action
Here is an example list which currently is unsorted:
| 45 |
| 23 |
| 2 |
| 56 |
| 90 |
The selection sort process will place the above list in a group and then look to see which entry has the smallest value. In this case, that entry would be “2”, so the algorithm would place the 2 in the second loop.
| First Loop | Second Loop |
| 45 | 2 |
| 23 | |
| 56 | |
| 90 |
Then the algorithm would check the first loop again, looking for the entry with the least value. In this case, it would be “23”. So, then the algorithm places the entry as the next number in the second loop.
| First Loop | Second Loop |
| 45 | 2 |
| 56 | 23 |
| 90 |
This process is repeated until the first loop simply runs out of entries. Then the second loop is returned as sorted.
Problems with Using Selection Sort
As is fairly obvious, there are a number of drawbacks using this method..First, the selection sort algorithm must plod through each entry one at a time. This shortcoming ensures that selection sort is much slower than algorithms such as quicksort or mergesort on long lists. If a speedy result on a long list is the coder’s aim, selection sort should be avoided.
Also, the classic use of selection sort is inherently unstable, meaning that the list that it creates does not preserve the order the list items or array elements were originally listed. This trait may be modified by a knowledgeable coder, and so selection sort may be stable, depending on the coding implementation.
In terms of complexity, selection sort is O(n²) in both average and worst-case scenarios. Although O(n²) isn’t very fast, there is very little variation between the fastest scenario and the slowest scenario, which is a positive feature.
Reasons to Consider Using Selection Sort
However, selection sort runs quite speedily on smaller lists, often returning results faster than divide-and-conquer sorts such as quicksort and mergesort, simply because on shorter lists. Often when a divide and conquer sort has partitioned a large list or array into smaller sizes, the divide-and-conquer algorithm will then run simultaneous selection sorts to put the list or array in order faster.
Another substantial reason to use selection sort is that it uses very little memory and is known for being CPU-light. If the coder is working in a space where memory is limited or costly, this feature can be a tremendous advantage. For example, when using Flash memory, every write function shortens the life of the memory. The option of selection sort should be considered in situations such as these, because selection sort does not require an additional file to be built to house data. All action takes place within the algorithm and memory.
In comparison with other algorithms, selection sort almost always performs more quickly than bubble sort or gnome sort. Join an interesting conversation here.
Comparison: Selection Sort Versus Insert Sort
However, insert sort almost always is faster and more efficient. To understand why, a coder must understand the concept behind insert sort.
Like select sort, insert sort uses two loops to place a list or array in order. However, the way in which the list is sorted differs.
With select sort, the algorithm must loop through each item in the original list in order to find the lowest value. However, with insert sort, the algorithm takes a value from the original list and inserts it into the proper place on the sorted list. This makes for a much faster algorithm. An example of an unsorted list is below, to help explain the differences between select sort and insert sort.
| Unsorted List |
| 5 |
| 65 |
| 12 |
| 15 |
| 98 |
| 3 |
An insert sort algorithm would take the first entry on the list (“5” in this case) and place it as the first entry in the sorted list. Meanwhile, a select sort algorithm would go through the entire list and then select the lowest number (“3” in this case). That number would then be placed as the first entry on the sorted list.
The insert sort would then take the next number (“65”) and place it after the number 5 on the sorted list. The select sort algorithm, though, would need to go through the entire list again, take the number “5” and then place it as the second entry on the list. As can be seen by the example, insert sort generally takes less time than select sort, because it is more efficient.
Also, classic insert sort is considered a stable sort, meaning that the original order of the list is respected when it does not interfere with the sort. For example, if insert sort were tasked with organizing the following sample list by the first integer (12, 34, 5, 9.6, 9.5), the list element “9.6” would appear before the list element “9.5” in a stable sort result.
This result differs from select sort, which is considered an unstable sort. If the same list were processed by the select sort algorithm, the results would either be (5, 9.5, 9.6, 12, 34) or (5, 9.6, 9.5, 12, 34). There are two possible results, as the original order of the list is not respected.
Selection Sort: Easy to Learn for the Neophyte Programmer
Selection sort is one of the simplest algorithms, which means it’s easy for the beginning coder to implement. The basic nature of the algorithm ensures its continued use as well, meaning that most coders are familiar with selection sort and will understand the coder’s usage of the algorithm in a program. This near universal familiarity means that selection sort can be used on projects with multiple coders, as it is so basic that nearly every member of the programming team can assume to be familiar with it.
Even if a team member has not encountered selection sort before, the functioning behind the algorithm is easy to comprehend and shouldn’t confuse an individual who is unfamiliar with it. Again, this is an advantage for selection sort, which is easier to understand for most people than other sorting algorithms.
Why it’s Valuable to Know Selection Sort
Although selection sort may not be appropriate for every array or list that needs sorting, it should be considered for small lists, especially if the coder is working under tight memory restrictions. In some instances, selection sort is even faster than divide-and-conquer algorithms such as quicksort. No matter what type of sorting the coder generally encounters, selection sort should be an algorithm that the coder is familiar with.
.
What do you think?