CS112 Sorting Algorithms

Name all of the sorting algos we need to know

Selection sort, Bubble sort, Insertion sort, Quick sort, Merge sort

What are the best/average/worst case time averages for Insertion Sort?

Best case O(n) when the list is already sorted. Average/Worst case are O(n^2) when you have to go back half or all of the time

Explain how Insertion Sort works

Has a sorted and unsorted region. Goes through each element and compares backward. Places the element in the correct spot in sorted region then moves on.

What are the best/average/worst case time averages for Selection Sort?

Always has O(n^2) because you have to check the list for each element.

Explain how Selection sort works

You go through element by element and find the minimum by going through the whole list. The algorithm tracks the position of the minimum value and swaps at the end.

What are the best/average/worst case time averages for Bubble Sort?

Best case is O(n) when the list is sorted. Average/worst case is O(n^2) if you have to bubble an element to the back every time. However, the best case is dependent on the algorithm having a check for if there are no swaps during a pass.

Explain how Bubble sort works

You always start at position 0, but you go to a decreasing position. Each repetition results in the largest element being brought to the end

What are the best/average/worst case time averages for Quick Sort?

Best case: O(logn) when the pivot is always the middle element.

Worst case: O(n^2) when the pivot is always the smallest/largest element

Explain how Quick Sort works

Recursive, divide and conquer algorithm. Establishes a pivot at the centermost element (or the center left if even elements). From there, two trackers I + J which start from the front and back of the array. When I reaches an element bigger than the partition and J reaches one smaller, they swap. This continues until the two swap places.

What are the best/average/worst case time averages for Merge Sort?

Always O(nlogn) time

Explain how merge sort works

Requires two sorted lists and merges them. Compares arr1[i] with arr2[j], if one is smaller than adds it to the temp array and increments the i or j—whichever was added.

In order to sort: Splits one list in half, then half, etc. until one element. Then merge sorts them all together.