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 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.
