When a closet is messy or disorganized, even if you know those shoes that go perfectly with your new dress are in it, often it doesn't feel worth it to sift through the piles of clothes that don't fit anymore and winter coats you won't need for months to find them, so you end up wearing those boring black ballet flats out of convenience.
Sorting in computer science is important for this same reason. Much like it does not matter how big your closet is if you can never find anything, it does not matter how much data a computer or program can store if it takes an unreasonable amount of time to access and perform actions on or with that data.
Overtime a number of effective sorting algorithms have been developed, but some, as we will see, are less time consuming and expensive.
Here are a few of the most well-known sorting algorithms:
Bubble Sort: This algorithm makes passes through an array, comparing adjacent items, and swapping those that are not in the right order. If someone was going through there closet and wanted their winter coats on the left, fall jackets in the centre and spring cardigans on the right, and they saw a fall jacket on the far left, if they used bubblesort they would look at the item directly next to it. If they saw a winter coat they would swap that with fall jacket, on the other hand if they saw a spring cardigan they would not swap the two and would move on to comparing the spring cardigan to every item in the closet until it was in its proper place. They would then repeat the process until the closet is sorted.
Obviously this is not an efficient way to sort a list or a closet. Bubblesort exchanges items with other items before we even know where that item is supposed to go. This leads to moving items from incorrect positions to incorrect positions, which is expensive and time consuming. In its worst case bubble sort takes O(n**2), but it's worth noting that on a sorted list bubble sort can stop early because if there are no exchanges during a pass the list is sorted.
Selection Sort: This algorithm is similar to bubble sort, but it does not make unnecessary swaps it avoids doing so by first looking for the largest value, in a list and then swapping it into its proper place.
For example, if you were organizing shoes by their heal height, you would begin by looking for the really tall five inch heals and moving those into there place, then doing the same with the three inch platforms, then the nikes, then finally the ballet flats.
Selection sort is still O(n**2) because it makes as many comparisons and bubblesort, but because it avoids unnecessary exchanges and it does tend to execute more quickly.
Insertion Sort: Insertion sort is a bit like if you decided to just start fresh and move everything to a new closet entirely. It treats the first portion of the list as a sorted sublist, and goes through each item, adding it to its proper place in this sublist, until the sublist becomes the list.
Insertion sort is still O(n**2), given that the number of comparisons in its worst case would be similar to that of bubble-sort and insertion sort. However, on a sorted list, only one comparison would be made per pass.
Merge Sort: This algorithm really speeds things up. Using recursion merge-sort divides and conquers' the a list. Essentially merge-sort splits a list in half sorts each half using merge sort (i.e. merging them together) then 'merges' them together again. It is basically like if you had as many friends willing to help you organize your closet as you do items in your closet.
Merge sort is O(nlogn) or 'linearithmic', making it much quicker then the previous algorithms, but it also requires much more space as it needs to store the 'half lists' separately.
Quick Sort: This algorithm is similar to merge sort, but it avoids using the excess storage by using a 'pivot value' and moving items to the side of the pivot value which they belong, instead of splitting the list in half.
If the pivot value is always in the middle of the list, then it will be O(nlogn) like merge sort, but without the excess storage. In it's worst case though, the algorithm will be O(n**2), making it as inefficient as something like bubble sort.
No comments:
Post a Comment