Sorts

Question 1

Is quick sort in place? Stable?

Answer 1

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

Question 2

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

Answer 2

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

Question 3

What leads to a worst case performance of quick sort?

Answer 3

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

Question 4

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

Answer 4

Each partition step takes Θ(n) operations.

Question 5

Name the two common quick sort partitioning schemes.

Answer 5

Hoare and Lomuto.

Question 6

Describe the Hoare partitioning scheme.

Answer 6

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

Question 7

Describe the Lomuto partitioning scheme.

Answer 7

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

Question 8

Which pairtitioning scheme is more efficient?

Answer 8

Hoare.

Question 9

Quicksort performance is primarily driven by what?

Answer 9

Pivot selection.

Question 10

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

Answer 10

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

Question 11

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

Answer 11

Quick sort and merge sort.

Question 12

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

Answer 12

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);
}

Question 13

Write pseudo code for quick sort’s paritioning.

Answer 13

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;
}

Question 14

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

Answer 14

Θ(n log n) in all cases.

Question 15

Is merge sort in place? Stable?

Answer 15

Stable, but not in place.

Question 16

What is merge sort’s space complexity?

Answer 16

Θ(n)

Question 17

Can merge sort readily be an in-place algorithm using arrays?

Answer 17

No.

Question 18

Can merge sort be implemented with lists?

Answer 18

Yes.

Question 19

How does merge sort find the halfway point of list in 1n time, rather than 2n time?

Answer 19

Using the “alternate and skip” method.

Question 20

Can merge sort be made to work on a list of lists? (nested lists)

Answer 20

Yes, by merging depth first.

Question 21

What’s the cost of finding the halfway point of an array in merge sort?

Answer 21

Θ(1)

Question 22

What are the benefits of identifying already sorted runs in merge sort?

Answer 22

Less overall comparisons & swaps, reduced merge operations.

Question 23

Why is it possible to develop logarithmic time insert and remove the maximum operations within a heap?

Answer 23

Because the height of a complete binary tree of size n is floor(lg n).

Question 24

What are the two approaches to heapifying?

Answer 24

Top-down (swim-based) or bottom-up (sink-based).

Question 25

Bottom-up heapifying uses how many compares and how many exchanges to construct a heap from N items?

Answer 25

fewer than 2N compares, and fewer than N exchanges.

Question 26

Write the pseudo code for merge sort. (assume merging is handling by a separate function).

Answer 26

list mergesort(list a) {
if (a’s size <= 1) return a;
l1 = a[0 to half];
l2 = a[half to end];
return merge(mergesort(l1), mergesort(l2));
}

Question 27

Write a function that merges two arrays together.

Answer 27

int[] merge(l1, l2) {
L = new List();
while (neither l1/l2 are empty) {
if (l1.get(0) <= l2.get(0)) {L.add(l1.remove(0));}
else L.add(l2.remove(0))
}
if (l1.isEmpty()) L.addAll(l2);
if (l2.isEmpty()) L.addAll(l1);
}

Question 28

Write the pseudo code for heapsort.

Answer 28

void heapsort(int[] a) {
for (int i = a.length/2; i >= 1; i–) {sink(a, i, a.length);
int N = a.length;
while (N > 1) {
exch(a, 1, N–);
sink(a, 1, N);
}
}