COMP 1005 Lecture Notes - Lecture 12: Sorting Algorithm, Mathematical Notation, Time Signature
24 Jan 2021
School
Department
Course
Professor
Document Summary
Know how to calculate the complexity of algorithms. There are various sorting algorithms such as bubble sort, quick sort, insertion sort, selection sort, and merge sort. In a comparison-based sorting algorithm, we compare elements in the list and make decisions based on these comparisons. Python automatically knows how to compare numbers with other numbers and strings with other strings. Insertion sort takes elements one by one from an unsorted array and inserts them into a new sorted array. Selection sort divides an array into two arrays: sorted and unsorted. At the start of sorting, the sorted array is empty. The unsorted array is the initial given array. It is useful when the array size is small. The two methods maintain an invariant throughout its execution. An invariant is something that remains true as the algorithm executes. The selection sort builds up its sorted partition by selecting the minimum value remaining in the unsorted partition.
