For the past two weeks, the course has taken a look at different sorting methods in python, and how they can compare to each other in efficiency. Sorting means to place elements of a list in a certain order.
For an explanation of how sorting efficiency is determined,
feel free to check out this blog -- http://jason-csc148.blogspot.ca/ -- under "Sorting and Efficiency".
Some examples of sorting algorithms are bubble sort, insertion sort and merge sort.
Bubble sort in python is a very simple algorithm that compares adjacent elements in a list, swapping them if they are in incorrect order. Bubble sort is one of the slowest sorting algorithms, and in worst cases has a time performance of O(n^2).
Insertion sort is similar to bubble sort, in that it compares adjacent elements in the list. However, once it finds a pair of unsorted elements, it takes the correct element from the two, and inserts it into the correct position of the sorted part in the list. When comparing the efficiency of bubble and insertion sort for an unsorted list, insertion sort requires fewer comparisons and is therefore more efficient. It, too, has a time performance of O(n^2) in a worst case scenario.
Merge sort, however, is on a completely different level than insertion and bubble sort. It maintains a time performance of O(nlogn) for both its best and worst case scenarios. Merging sort works through a merging step, which takes two sorted lists and merges them into one sorted list. This happens by comparing the smallest elements of each list, and placing them into the merged list accordingly. This step is used in merge sort by firstly splitting up the list into single element lists. Then, we merge each pair of lists into a larger list using the merging step. Next, we take the sorted two-element lists and repeat the process by pairing themselves up with of other two-element lists and merging the two lists together. We complete this process until we unify all of the smaller lists into one finalized sorted list. Merge sort is a lot better than insertion and bubble sort because it takes almost constant time to sort any list of the same length, and the run time in general is a low faster.
