Sorting Methods!
February 22nd, 2016
In this particular case, I will be talking about three specific methods, Bubble sort, Quicksort, and Merge sort.
Bubble Sort
I'm a strong believer in visuals so to commence...
As the visual is showing, the Bubble sort compares through each pair all the way to the end. If not fully sorted, will start over.
The quickest and most efficient method is desirable so how does this sorting method fare compare to others? Fares okay when the amount of numbers to sort is small. Big amounts of numbers, no.
Quicksort
No, its not a typo. Its spelled 'Quicksort'.
Quicksort acts like a partitioning type of method where it divides numbers into a low and high sections. It will pick the last number and move numbers to the left and right based on the relation to the number picked. In this image, the last number is four. Eight, nine, five, and seven are moved to the right since they are higher. The numbers are then divided for further sorting.
Again, the last number is picked. Two is 'last' and three is moved to the right which sorts that area. On the right-hand side of the four, the numbers are sorted a little further. Once all the partitions are sorted, the job is complete.
Quicksort is faster and saves space (in-place sorting) while Merge sort, which I will discuss next, requires space to run its calculations. However, there are times when Merge sort will be the preferred method, as when there are an inordinate amounts of numbers.
Merge Sort
A Merge Sort is a "divide and conquer" sort of method. It divides the amount of numbers into the smallest amount (one) and then compares itself with its neighbors to know where to go in the next step. Proceed with viewing the gif below.
Merge sort fares very well even with large amounts of numbers. In fact, in the worst case where sorting is not easy, it still performs 39% fewer comparisons than Quicksort!