CSE 331 Lecture Notes - Lecture 1: Heapsort, Sorting Algorithm, Insertion Sort
Types of Sorts
• Comparison sorts: compares two elements at a time
o Elements must form a consistent, total ordering
o compareTo() must work for the elements
o Best runtime is O(nlog(n))
• Niche Sort: also called linear sorts. Leverages specific properties about the items in the
list to achieve faster runtimes
o Runs on O(n)
• In place sort: a sorting algorithm is in-place if it requires only O(1) extra space to sort the
array
o Typically modifies the input collection
o Useful to minimize memory storage
• Stable sort: a sorting algorithm is stable if any equal items remain in the same relative
order before and after the sort
Algorithms
• Insertion sort: take each item and insert it where it should belong.
o Start at the beginning and then take in one item at a time and insert it
o Consistently loop over the sorted part of the loop.
o Worst case runtime is O(n2)since you have to loop through to find the first out of
order. Then loop through to find where to insert
o Best case runtime is O(n)(when list is already sorted), which almost never occurs
o It is an unstable sort algorithm, depending on how the algorithm is implemented
o It is an inplace algorithm
• Selection sort: similar to insertion sort, where you insert items where it belongs. But
instead of choosing the next unsorted item, you find the next smallest item that is
unsorted.
o Worst case runtime is O(n2)
o Best case runtime is O(n2)
o Algorithm is in-place
• Heap sort: run Floyd’s buildHeap on the data, then call removeMin() til there are no data
left.
o Worst runtime is O(nlog(n))since it takes O(n) to build the heap, and log(n) to
remove (have to percolate the nodes)
Document Summary
Types of sorts: comparison sorts: compares two elements at a time, elements must form a consistent, total ordering, compareto() must work for the elements, best runtime is o(nlog(n), niche sort: also called linear sorts. Leverages specific properties about the items in the list to achieve faster runtimes: runs on o(n) Then loop through to find where to insert: best case runtime is o(n)(when list is already sorted), which almost never occurs. It is an unstable sort algorithm, depending on how the algorithm is implemented. It is an inplace algorithm: selection sort: similar to insertion sort, where you insert items where it belongs. So you can use a max heap instead: divide and conquer: idea of dividing the work into smaller pieces recursively and then conquer those pieces, merge sort: divides the list into half, then continue breaking it down. Recursively divide each parts into less than and greater than.
