Week 11: Sorting and Efficiency

This week in lecture and in the lab, we looked at sorting algorithms and their efficiency. The algorithms we looked at were insertion sort, selection sort, bubble sort, quick sort, and merge sort. We compared their efficiency to timsort, Python's built-in sorting method), but only by run time since no code was provided. Here are some observations I've made about each of the algorithms:
  
Insertion Sort
There were two versions of insertion sort, the second of which included a call to "del." This version of insertion sort ended up being faster than the first one. To compare, on a 2000 item list, insertion_sort_1 took 0.44 seconds while insertion_sort_2 took only 0.26 seconds.  In insertion_sort_2, the algorithm will look for the insertion point, and once it is found, the item that needs to be sorted gets stored in a variable and deleted from the list. This makes the algorithm run time faster because once the insert method is called, the list is now one item shorter. Thus, it can put the item in the right spot by looping over fewer elements.

  
Selection Sort
Selection sort is interesting because it is always in O(n^2). It goes through the entire list to make comparisons to ensure that each element is properly swapped if need be. Compared to other algorithms,  it is faster than bubble sort, but slower than insertion_sort_2. In the lab, my partner and I discussed ways of making this algorithm faster, and we discovered that since the while loop called "len" during each iteration, it made the run time a little slower. To fix this problem, we assigned len(L) a variable before the while loop so that "len" would only be called once.

Bubble Sort
Bubble sort is by far the slowest sorting algorithm. Although there were two versions of it included in the lab, both took approximately 0.7 seconds on a 2000 item list. Bubble_sort_1 simply makes swaps until the largest item is at the end of the list, which is the sorted section. Bubble_sort_2 checks if there were any swaps on the previous scan of the list, and if not, the algorithm will stop early. It was interesting to see that the second version was not actually faster as expected. Looking over the code, I think it was slower than bubble_sort_1 because of the extra while loop. It's one extra step to check, so if this version was used on the worst case, the run time would be much slower than bubble_sort_1.

Quick Sort
Quick sort is a fairly fast sorting algorithms, but unlike most sorting algorithms, it's slower on nearly sorted or sorted lists. Since it partitions smaller elements to the left and larger elements on the right of the pivot, there will be an unequal number of elements in the right half. The algorithm works much faster when used simultaneously on halves with a similar number of elements. Of the two versions of quick sort below, the second method has a faster run time because it doesn't make copies of the sub lists. Instead, it works with the original list all throughout. The difference is noticeable, with quicksort_2 being 0.3 seconds faster than quicksort_1.

Merge Sort
Merge sort works recursively by splitting the list into two halves, sorting those halves, then merging them together. We worked with two versions of merge sort: mergesort_1 works by creating new lists while mergesort_2 continually updates the original list. The second method is faster (0.010302 seconds vs. 0.009599 seconds). Similar to quick sort, this is because it takes more time and memory to create new lists each time, whereas only using the original list is more efficient.

Although there are six sorting algorithms mentioned above, there exist even more to do the same simple task: sort a list of numbers in non-decreasing order. This is one of the key aspects of computer science. Even though there may be a best way to do a task (in this case, Python's built in method was the most efficient), it's important to notice that there are multiple ways to look at a problem and solve it.