“The Big Sort”
One common algorithm that developers come across is the sorting algorithm. Sorting algorithms can be defined as an algorithm that puts elements in a certain order. For example, take the array below.
arr = [ 9, 10, 5, 2, 4 ,1 ,3, 6, 8, 7 ]As we can see, this is an unsorted array. Although many languages have built-in sorting methods, it is important to understand sorting as an algorithm. In this blog, I will be going over two specific types of sorting: Selection Sort and Insertion Sort. These two types of sort are simple methods that can be used to order elements in an array. I will first lay out the code for the two types of sort in JavaScript, and then discuss the two in tandem.
“Selecting and Sorting”
Selection Sort, as described by Wikipedia, is an in-place comparison sorting algorithm. To parse this, it simply take the current element, and compares it to every other element in the array. If we were ordering the array above, it would take 9, and compare it to every other number in the array. As it iterates over each element, it stores the value if it is less than 9. This new value is then used as the comparison, and will continue through the array. Once the iteration completely ends, the value that is stored to compare, is returned to the index of the array it started at. In this case, 9 would compare 10, keep 9 as the comparison value until it reaches 5. Since 5 is lower than 9, 5 becomes the new comparison value. The iteration continues and 5(the comparison value) is compared against 2. Since 2 is less than 5, 2 becomes the new comparison value. The next comparison would be 2 and 4. Since 2 is the smaller value, it is kept, and then compared with the next. This will continue on until the end of the array. At the end, the current value being used to compare is switched with the number this iteration started at. After the first iteration, the value being used to compare would be 1, at index 5. Since this iteration started at 9, index 0, these two values would be switched.
arr = [ 1, 10, 5, 2, 4 ,9 ,3, 6, 8, 7 ]
#new result after first iterationIf this wordy explanation is hard to understand, the GIF below shows a visual version of selection sort.
Now we can take a look at the code for a selection sort.
The method selection_sort takes in an argument of an array. The first step is to initialize an empty array, that will store the sorted values in our array. Then, we move into the iterative part of our method. The until statement indicates how many iterations we will go through. We then use a built-in Ruby method min = arr.min.
This will set the variable min to the smallest value in the array. The next line, idx = arr.index(min) finds the index of min . We then push the min into the sorted array. The last line, arr.delete_at(idx) , deletes the element from the array. This is done in order to reduce the length of the array, as the until loop will run until the array is empty. The final part is to call sorted to return the now sorted array.
Insertion Sort
Wikipedia describes Insertion Sort as building the sorted list one element at a time. Similar to Selection Sort, this is an in-place comparison algorithm. However, rather than taking the current element and iterating forward, it iterates backwards. This means that whatever the current index is, the method will look at all the indexes before it, and, and find where the value should be inserted. This may be difficult to understand verbally, but the GIF below can be used as a visual interpretation.
As you can see, the current value being compared, highlighted in red, is moved down the array based off a comparison. As it is being moved, you can see how the sorted array is being built. But how is this reflected in code?
Here, we have a much longer solution when compared to the Selection Sort example. We initialize another empty array, listed as sorted. However, we use the arr.shift method in order to push the first element into this array. Then, we build out our for loop based off i . Inside the loop, we initialize a sorted_index of 0. Then comes a while loop. This while loop runs as long as the condition, sorted_index < sorted.length , is true. Within this loop, we have an if...elsif conditional.
The upper condition is a comparison that returns true if the value is less than the compared value. If it is true, than we insert the number to the left of the compared element. The second conditional handles equal values. It is inserted to the right of the number, and breaks. The entire loop will run again, once the current element reaches a number it is greater than. As this process continues, the insert sort will continually insert values in locations based on this formula.
Understanding the process
If we were to look at these two sorting mechanisms, it is clear that as the size of the array increases, the run time of the two formulas also increases indicating that the Big O notation would be O(n²) in the worst cases. However, there is variance in the run time of the two formulas. The Insertion Sort method in bet case scenarios can run at O(n), something the Selection Sort would be unable to do in the best case scenario. Generally, the insertion sort will have a faster run time, due to the way it approaches sorting. Rather than iterating over the entire array the same amount of times(this means that it produces a quadratic number of comparisons every time), the insertion sort will adapt to the data and can reduce the number of operations it performs. However, the speed of sorting would have to be scaled on a large array and tested multiple to times to see this general pattern.
Resources
https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif