Sorting

Front 1

What are 4 sorting algorithms with an average performance of n*log n?

Back 1

Quick sort

Merge sort

Heap sort

(also Tim sort)

Front 2

How does quick sort work?

Back 2

First, it selects a pivot point and partitions the array such that all items less than the pivot are to the left of the pivot and all items greater than the pivot are to the right of the pivot. Then it recursively calls itself on 0 through pivot -1, and pivot through end.

Front 3

What is quick sort's worst case performance?

Back 3

O(n^2)

Front 4

What is merge sort's worst case performance?

Back 4

O( n log n)

Front 5

What are some circumstances where quick sort performs poorly?

Back 5

Arrays with many repeated elements. Also, depending on the pivot point, arrays sorted in reverse order. (This can be mitigated by selecting as pivot a number towards the middle of an array- for example, p = lo + (hi-lo)/2). It's also not ideal when the array is already mostly sorted, since it must compare to pivot anyway to detect this. This can also be mitigated with a central pivot?

Front 6

Does quick sort preserve original ordering of elements with equal values? (Is it stable?)

Back 6

Nope!

Front 7

What is merge sort?

Back 7

It splits an array into two, checks if each sub array has more than two elements, then recursively calls itself until you have only two elements on each side. It then calls merge, which creates a merged version of the array passed to it by set merging (if first element f of set a is less than first element of set b, f is first overall, go forward. If second element f is < first element of b, f is next; otherwise fb is next, and so on.)

Front 8

Does merge sort preserve the relative ordering of elements with equal values (is it stable?)

Back 8

Yes! Though to make this work, the merge function must favor the first set whenever two equal values appear.

Front 9

Name some ways to optimize merge sort

Back 9

-If the last element of a sorted array is less than the first element of the right hand sorted array, then the call to merge isn't necessary.

-switch to another sorting algorithm when the circumstances are right for that algorithm to perform it's best-case, if better than n*log n

Front 10

What sorting method is O(n) for very small arrays and already mostly sorted data?

Back 10

Insertion Sort; starts at 1, compares 1 and 0, if less than, swap. Moves to 2. compare to 0, if less, insert. Else compare to 1, if less, swap.

Front 11

When is merge sort better than quick sort?

Back 11

When a dataset is too large to fit into memory you can easily split it into smaller files which can be read into memory, sorted by (some appropriate algorithm) and then a merge operation is called using the sorted files as input.

Front 12

When is quick sort better than merge sort?

Back 12

Most of the time, unless the data is mostly sorted already. Also, quicksort is in place in terms of space, where mergesort usually needs 2n.

Front 13

What is heap sort?

Back 13

Treats the input array as a heap, and calls max (or min) heapify to make sure each parent is bigger (smaller) than it's children; otherwise, swap parent and biggest(smallest) child. Then puts the root of array (at 1) in the final position, copies root into end or beginning of output array, and calls heapify on the new, smaller input array.

Front 14

What does the max heapify step of heapsort do?

Back 14

It goes through the heap making sure that the parent is always greater than its children.

Front 15

How do you make merge sort in place?

Back 15

Either with a lot of complicated work with arrays, or very easily using pointers (in a linked list, for example)

Front 16

When is insertion sort handy?

Back 16

When there is only a small amount of data to be sorted- even if into a large total amount of already sorted info

Front 17

What is Selection Sort?

Back 17

Selection sort works by comparing the 0 of the array with the rest of the array until the minimum is found, then swapping that minimum into 0. Repeat for 1, again searching for minimum. Best average and worst cases are all O(n^2)

Front 18

How would you handle sorting by multiple keys- for example, multiple fields in an object, like a car's make and model?

Back 18

Custom comparator functions, ie a custom rule for ordering the set.