Whether in real life or in the world of programming, being able to sort through data is tremendously useful. Think of how many times you have wished a mess would clean itself up on its own! Sorting algorithms are commonly written as a solution to these types of problems in programming.
So, what is a sorting algorithm? A sorting algorithm is an algorithm that is used to rearrange and sort a given array or list of elements. There are dozens of well-known sorting algorithms, each with their own unique manner of sorting and rearranging elements. Some are chosen over others for their ease of implementation, while others are chosen for their superior time complexity when run against larger collections of data. Today, we will focus on a few of the more basic sorting algorithms and visualize how they differ from one another.
Selection Sort
Selection sort is often viewed as the most basic of sorting algorithms, and chances are that if you have sorted an array at a beginner level, it was likely using selection sort (or something similar). Think of holding playing cards in your hand--to sort them in ascending order, most people would look for the lowest numbers first (in this case let's say 2's) and place them towards the left of their hand. Next, they would look for all of the next highest numbers and place them towards the left, and so on.
In coding terms, imagine an unsorted array [34, 25, 14, 22, 11]. Starting at the index of the first unsorted value, selection sort will traverse the entire array from left to right, replacing the first unsorted value with the local minimum of the traversed elements. Everything to the left of the next unsorted value will be considered sorted.
34 25 14 22 11
11 25 14 22 34
11 25 14 22 34
11 14 25 22 34
11 14 25 22 34
11 14 22 25 34
11 14 22 25 34
11 14 22 25 34
Insertion Sort
Insertion sort is also a relatively basic sorting algorithm that is widely used for smaller datasets. It also involves splitting a collection of elements into a sorted and unsorted portion and comparing elements between the two. Let us use our previous unsorted array for this example: [34, 25, 14, 22, 11]
Insertion sort will initially compare the first two elements of the array and swap them if unsorted. in this case, 25 has been swapped with 34 and is considered part of a sorted sub-portion of our array.
34 25 14 22 11
25 34 14 22 11
Next, 34 is compared with 14, the next unsorted element in our array, and they are swapped. Now, 14 will be compared with our "sorted" sub-portion and will be swapped with 25.
25 34 14 22 11
25 14 34 22 11
14 25 34 22 11
This process repeats until the collection has been sorted:
14 25 34 22 11
14 25 22 34 11
14 22 25 34 11
14 22 25 34 11
14 22 25 11 34
14 22 11 25 34
14 11 22 25 34
11 14 22 25 34
11 14 22 25 34
Merge Sort
Merge sort is a slightly more complex algorithm that utilizes recursion to sort data. If you haven't worked with recursion, learning about the merge sort algorithm is also a great introduction to recursion. Let's use an array with a couple of more elements to demonstrate merge sort: [38, 27, 43, 3, 9 , 82, 10]
Merge sort will initially split the array into equal halves (or in the case of odd-numbered elements, almost-equal halves). Then, it will recursively split each half into smaller halves again and again until each split "half" cannot be split anymore, such that each recursively-split "half" represents a single element of the original array. The halves are then compared with their prior-split counterparts and sorted in small groups. These small groups are then compared with the next prior-split small group and sorted again--this process is repeated until all of the groups have been merged back together in sorted order. It is important to note that merge sort will prioritize completely sorting each "half" or "split-group" before merging halves back together. The diagram below shows the steps in which the merge sort algorithm acts.
Why so many algorithms?
The main reason sorting algorithms are implemented are to save time in the long-run, but what happens when you have to choose between these different sorting algorithms to save time? Using our playing card example, it is easy to imagine looking through 5 or so cards and sorting them using an algorithm like selection sort--but how about when the hand gets to 20, 100, even 1000 cards? It's much easier to imagine dividing that hand up between 2, 4, even 8 or more people and utilizing something like merge sort!
Some sorting algorithms perform more efficiently than others on average, and that's just the way it is. However, some algorithms are easier to implement when saving time is not an issue, such as implementing selection sort and insertion sort when working with very small sets of data. While saving time is important, saving the hassle of writing difficult code is also crucial to many programmers!
Top comments (3)
What you are calling "insertion sort" isn't insertion sort. Insertion sort doesn't do adjacent swaps like that. You've described some sort of cross between insertion sort and bubble sort. Insertion sort stores the next element to be inserted in a temporary variable, then shifts elements over until insertion point is found, finally inserting. Only needs about a third of the assignments to sort compared to what you've described.
After doing some further research and reading, I understand--thank you for the insight and clarification Vincent!
You're welcome