# Sorts Flashcards

Quicksort Time Complexity

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

worst O(n^2) (red)

Quicksort Space Complexity

log n (green)

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

Quicksort - How does it work?

**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.

Quicksort Features

**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

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

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.

Mergesort Natural Variant

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

Mergesort Time Complexity

**Time Complexity**

Best, avg, and worst case: n log n

Mergesort - How Does It Work?

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.

Mergesort Space Complexity

**Space Complexity**

O(n) worst case

Mergesort Features

**Features**

Stable (!)

Divide and conquer

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

**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?

What is a stable sort?

Preserves the input ordering of elements with equal keys

Selection Sort Time Complexity

**Time Complexity**

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

Selection Sort Space Complexity

**Space complexity**

O(1)

Selection Sort - How Does It Work?

**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.

Heap Sort - Time Complexity

**Time Complexity**

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