Sorts

Question 1

Quicksort Time Complexity

Answer 1

best, avg O(n log n) (orange)

worst O(n^2) (red)

Question 2

Quicksort Space Complexity

Answer 2

log n (green)

Quick sort calls itself log(n) times. For each recursive call, a stack frame of contsant size is created.

Question 3

Quicksort - How does it work?

Answer 3

How Does It Work?

Choose a pivot. Reorder the array so that all the values less than the pivot value are before the pivot and all the values greater than the pivot value are after the pivot. Now the pivot is in its final position. Apply the same pattern recursively.

Choice of pivot matters greatly. If the final position is chosen as the pivot, performance will be O(n^2) worst case for already sorted arrays or arrays of identical elements.

Computer architecture favors quicksort because it is a cache-efficient sort. It linearly scans the input and linearly partitions the input, which means you make the most of each cache load before reloading.

Question 4

Quicksort Features

Answer 4

Features

In practice, 2-3x faster than mergesort and heapsort despite having the same best case and avg case Big O

In place

Not stable

Question 5

Why is quicksort 2-3x faster than mergesort and heap sort despite having the same Big O time complexity?

Answer 5

Computer archutecture favors quicksort because it is a cache efficient sort. Quicksort processes segments of the array in order. When it loads the first element, the location is loaded into the cache. When it needs to access the next element, that element is likely already in the cache. Other algorithms, like heapsort, jump around the array a lot making them less cache efficient.

Question 6

Mergesort Natural Variant

Answer 6

Can get best case of O(n) using the “natural” variant which exploits naturally occuring sorted sequences. Rather than starting with sublists of size 1 or 2, split the data into naturally occuring runs

3,4,2,1,7

becomes

3,4 2 1,7

Question 7

Mergesort Time Complexity

Answer 7

Time Complexity

Best, avg, and worst case: n log n

Question 8

Mergesort - How Does It Work?

Answer 8

Divides entire dataset into groups of at most two.

Compares each number one at a time, moving the smallest number to left of the pair.

Once all pairs sorted it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.

This process is repeated until there is only one set.

Question 9

Mergesort Space Complexity

Answer 9

Space Complexity

O(n) worst case

Question 10

Mergesort Features

Answer 10

Features

Stable (!)

Divide and conquer

Question 11

What’s the best algorithm for sorting? Questions to ask…

Answer 11

What can you tell me about the data?

Is it already sorted, mostly sorted, or unsorted?

How large are the data sets likely to be?

Are there duplicate key values?

How expensive are key comparisons?

What are the requirements?

Are we optimizing for best-case, worst-case, or average-case performance?

Does the sort need to be stable?

What about the system?

Is the largest data set to be sorted smaller than the available memory?

Question 12

What is a stable sort?

Answer 12

Preserves the input ordering of elements with equal keys

Question 13

Selection Sort Time Complexity

Answer 13

Time Complexity

Worst, avg, best case: n^2 (red)

Question 14

Selection Sort Space Complexity

Answer 14

Space complexity

O(1)

Question 15

Selection Sort - How Does It Work?

Answer 15

How does it work?

Loop through array. Find the smallest element then swap it with the element in position 0. Repeat the same process to find the next smallest element and swap it with the item in position 1.

At each iteration, you are selecting the next smallest element and moving it into the sorted porition of the array.

Question 16

Heap Sort - Time Complexity

Answer 16

Time Complexity

Best, avg, worst: n log n (orange)

Question 17

Heap Sort Space Complexity

Answer 17

Space Complexity

Worst: O(1) (green)

Question 18

Heap Sort Features

Answer 18

In place

Not stable

Same time complexity as a merge sort but much better space complexity - O(1) vs 0(n).

Same space complexity as a selection sort but much better time complexity - O(n log n) vs O(n^2)

Question 19

Heap Sort - How Does It Work?

Answer 19

Very similiar to the seletcion sort. It divides the data into a sorted and unsorted region. Instead of looping through an array to find the next smallest element O(n), it uses a heap data structure O(log n).

Question 20

Counting Sort Time Complexity

Answer 20

Time Complexity

Best, avg, and worst case O(n+k) (green) where k is the maxiumum value of the key

Question 21

Counting Sort Space Complexity

Answer 21

Space Complexity

O(k) (yellow) where k is the maximum value of the key

Question 22

Counting Sort - How Does It Work?

Answer 22

How It Works

Not comparison based

Allocate an array, numCounts, of size k, where the indicies represent the range of the input and the values represent the number of times the number appears.

Make one pass through the array to fill in numCounts.

Create sorted array and fill in the sorted numbers.

Question 23

Sorts with O(n^2) (red) Time Complexity

Answer 23

Quicksort: worst case

Selection sort: best, avg, and worst case

Insertion sort: avg and worst case

Bubble sort: avg and worst case

Question 24

Sorts with O(log n) (light green) Space Complexity

Answer 24

Quicksort

Question 25

Sorts with O(n) (yellow) Space Complexity

Answer 25

Mergesort

Question 26

Stable Sorts

Answer 26

Mergesort Counting sort Radix sort Insertion sort

Question 27

Sorts with O(1) (Dark Green) Space Complexity In place sorts

Answer 27

Heapsort Selection sort Insertion sort Bubble sort

Question 28

Sorts with O(n log n) (orange) time complexity

Answer 28

Quicksort: best, avg Mergesort: best, avg, worst Heapsort: best, avg, worst

Question 29

Radix Sort Time Complexity

Answer 29

**Time Complexity** O(nk), where k is the range of values

Question 30

Radix Sort Space Complexity

Answer 30

**Space Complexity** O(n+k), where k is the range of keys

Question 31

Radix Sort - How Does It Work?

Answer 31

**How Does It Work** Not comparison based Groups keys by significant position and value Least significant digit (LSD) radix sort: short keys before long keys then sort keys of the same length lexicographically Most significant digit radix sort: Use lexicographic order. b, ba, c...

Question 32

Insertion Sort Time Complexity

Answer 32

**Time Complexity** Best case: O(n) (yellow) Average case: O(n^2) Worst case: O(n^2)

Question 33

Insertion Sort Space Complexity

Answer 33

**Space Complexity** O(1)

Question 34

Insertion Sort Features

Answer 34

**Features** Stable In place Efficient for small data sets Much less efficient than quicksort, heapsort, and merge sort for large datasets

Question 35

Insertion Sort - How Does It Work?

Answer 35

Loop through the array beginning at item 1. (item 0 becomes the sorted portion of the array.) At each iteration, *insert* the current element into sorted position at the front of the array. (If asked to sort a deck of cards, most people would do it this way.)

Question 36

Bubble Sort Time Complexity

Answer 36

best case O(n) (yellow) avg case, worst case O(n^2) (red)

Question 37

Bubble Sort - How Does It Work?

Answer 37

A comparison based sorting algorithm It iterates left to right comparing every couplet, moving the smaller element to the left. It repeats this process until it no longer moves an element to the left.

Question 38

Bubble Sort Space Complexity

Answer 38

O(1) (dark green)

Question 39

Java Collections.sort()

Answer 39

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

Question 40

Adaptive Sort

Answer 40

Takes advantage of presortedness in the input sequence

Question 41

Java Arrays.sort()

Answer 41

Quicksort Implementation Time complexity Best, Avg: n log n Worst: n^2 Space complexity: log n

Question 42

When to use mergesort over quicksort

Answer 42

* MergeSort is stable by design, equal elements keep their original order. * MergeSort is well suited to be implemented parallel (multithreading). * MergeSort uses (about 30%) less comparisons than QuickSort. This is an often overlooked advantage, because a comparison can be quite expensive (e.g. when comparing several fields of database rows).