CSC148H5 Lecture Notes - Lecture 10: Quicksort, Merge Sort, Insertion Sort
Document Summary
Selection sort def selection_sort(lst): for each index i in the list lst: swap element at index i with the smallest element to the right of i. Insertion sort 5 def insertion_sort(lst): for each index from 2 to the end of the list lst insert element with index i in the proper place in lst[0i] Bubble sort 7 swap adjacent elements if they are out of order go through the list over and over again, keep swapping until all elements are sorted. Quicksort procedure quicksort(lst, left, right) would sort the segment lst[left:right+1] 1. pick lst[right] as the pivot: partition the list around the pivot, recursive quicksort the partitions on the left and right of pivot. Summary of quicksort quicksort isn"t always quick , theoretically. In the worst case, it"s still quite slow (o(n )) however, in practice, quicksort performs very well. The worst case is rare, and on average the performance is good (o(n logn)).
