# Sorts Flashcards

Is quick sort in place? Stable?

Quick sort is in place, and can be made stable (while still fast) with some neat optimizations.

What is quick sort’s time complexity (consider all cases)?

Θ(n log n) in the best and average case. Θ(n^2) in the worst case.

What leads to a worst case performance of quick sort?

When the pivots selected are consistently greater than or less than the rest of the values (leading to partitions of length 0).

How long does each of quicksort’s partitioning steps take?

Each partition step takes Θ(n) operations.

Name the two common quick sort partitioning schemes.

Hoare and Lomuto.

Describe the Hoare partitioning scheme.

Two scanning indices move towards each other until they swap or cross.

A swap occurs when both point to an element on the wrong side (inversion).

Describe the Lomuto partitioning scheme.

Two indices, but only one is scanning - out of place items are swapped to the beginning.

Which pairtitioning scheme is more efficient?

Hoare.

Quicksort performance is primarily driven by what?

Pivot selection.

Besides pivot selection, how else can quicksort be made more efficient?

Diverting to insertion sort for smaller partitions is generally more efficient.

What are the divide and conquer sorting algorithms (that we are studying)?

Quick sort and merge sort.

Write pseudo code for quick sort (assume partitioning is handled by a separate function).

void sort(int[] a, int lo, int hi) {

if (hi <= lo) return;

int j = partition(a, lo, hi);

sort(a, lo, j-1);

sort(a, j+1, hi);

}

Write pseudo code for quick sort’s paritioning.

int partition(int[] a, int lo, int hi) {

int i = lo, j = hi + 1;

int v = a[lo];

while (true) {

while (a[++i] < v) if (i == hi) break;

while (v < a[–j]) if (j == lo) break;

if (i >= j) break;

swap(a, i, j);

}

swap(a, lo, j);

return j;

}

What is merge sort’s time complexity? (consider all cases)

Θ(n log n) in all cases.

Is merge sort in place? Stable?

Stable, but not in place.