Sorting Algorithms
Bubble Sorting
The 'key' concept behind Bubble Sorting is that ADJACENT elements are compared. If we are sorting from small to big, the larger of the two in an adjacent pair is moved to the right, the smaller to the left. (If they are already in the correct position, their positions are not 'swapped.'). This continues for each adjacent pair from the left all the way to the right.
Multiple passes through the array are required to make sure all values are correctly placed.
In this fashion, the larger elements 'bubble' up to the right.
'Smart' Bubble Sorting
When implemented, after one full pass through the storage array, the largest element is in place. Therefore, it no longer needs to be compared to its neighbor.
The software keeps going through 'passes' of the array, but with each pass, it avoids comparing elements that have already reached the end.
Moveover, it keeps track of whether or not a 'swap' has occurred. As long as a 'swap' has happened, there's a chance that there is more sorting required.
However, if a pass through the array reveals no swaps, that means the array is sorted already, and the process terminates.
If you watch Smart Bubble Sort in action, you will notice that it appears to 'speed up' as it progresses. That's what is actually happening, as there are fewer elements to compare with each pass through the array.
'Dumb' Bubble Sorting
Unlike it's brighter cousin, Dumb Bubble Sort dutifully compares each element to its neighbor throughout the whole sorting process, even though elements at the right have already been correctly placed.
Additionally, for an n-element array, it goes through about that many passes even if no swaps are made. A keep observer would notice elements already in order, but the software doesn't 'know' that.
For this reason, 'Dumb Bubble' does not appear to accelerate as it progresses through its implementation.
Selection Sorting
'Selection Sort' begins with an 'S' and so does its 'key' concept word: SMALLEST.
Starting with the left-most array value, we assume it's the smallest. We then scan through the entire rest of the array looking for something even smaller.
If we do find a smaller value, we tag it and keep going until we reach the end. At the end, we now know the smallest element and where it was located. If it's smaller than the first, it is 'swapped' with the value in the first position in the array. Nothing happens if the first element was the smallest.
This process repeats for the second element, the third, etc all the way to the end.
After examining each nth element, the left-most nth value is correctly positioned. Therefore, for example, if 5 elements have been examined, we are guaranteed that the left-most 5 elements are correctly placed. So, they are no longer examined in the sorting process.
For this reason, only one pass through the array is required.
Because 'swaps' are potentially dramatic in their span, this algorithm is considerably more efficient than either Bubble Sort algorithm.
Insertion Sorting
'Key' concept? INSERT of course!
Starting with the left-most array value, we assume it's in the correct position.
Moving on to the second value, we position it in the correct position relative to the first. Subsequently, we look at the 3rd, 4th, etc values. Each time, we 'insert' it into the correct position, relative to the others, moving any elements to the right to accomodate the inserted value.
After the nth value is positioned correctly, we are guaranteed that the first n values are correctly placed. Therefore, there is only one pass through the array in this algorithm; each nth element is excluded from future dealings.
Shell Sorting
The 'key' concept in Shell Sort is JUMP. What does that mean?
We can best explain with an example. Suppose we have an array of 16 elements. We calculate a 'jump' value that's half the size of the array. In this case, the jump value is 8.
In the first pass through the 16 array values, we compare entries that are separated by the 'jump' value. If the left value exceeds the right, they are 'swapped.'
A swap indicates more work might need be done, so after the current pass is completed, another is done with a jump of 8. If no 'swaps' are made, the jump value is halved, and another pass through the array is performed with that jump until no swaps occur.
This repeats until the jump distance is 1, and no further swaps are made. Note that at this point, Shell Sort is now just Smart Bubble Sort in nature!
Generally, of the 5 techniques shown, Shell Sort is the most efficient. Changes are made in large jumps and this seems to help the process go faster.
Merge Sorting
Naturally the 'key' concept in Mergesort is MERGE.
It's a recursive 'divide and conquer' algorithm which tends to 'zip' two already-sorted sub lists together.
Wikipedia offers a great explanation and a mini-example.
We will add more explanations here as we develop it.
Note: Our Mergesort Demo was introduced in Stage 4 by K. Dance. It needs a bit of tweaking to get up to speed: it's limited to about 1000 stars because of a stack limitation, and it's not as fast as it should be at this time. However, modifications are forthcoming and we should get it fully up-to-speed soon.
