# Sorting Flashcards

What is Quicksorts best, worst and average runtimes? Is it stable and in-place?

Best: n log n

Worst: n²

Average: n log n

Stable: Not stable but can be

In-place: Yes

note:

- stable means to not have the order of 2 equal keys changed i.e. if 5D and 5H were in the initial input array in this order the output array should always hold 5D and 5H one after the other (not 5H, 5D)
- in-place means to output, for example, an array of the same size as the input and thus not wasting memory.

*If the list is implemented as an array, this can be done in-place and with at most n comparisons*

What is Merge Sorts best, worst and average runtimes? Is it stable and in-place?

Best, worst and avg are all

n log n

Stable: Mostly

In-place: No

*In any case the number of comparisons is in Θ(n)*

What is Heap Sorts best, worst and average runtimes? Is it stable and in-place?

Best, worst and avg are all

n log n

Stable: No

In-place: Sure?

What is BubbleSorts best, worst and average runtimes? Is it stable and in-place?

Best: n

Worst: n²

Avg: n²

Stable: Yes

In-place: Yes

What is Insertion Sorts best, worst and average runtimes? Is it stable and in-place?

Best: n

Worst: n²

Avg: n²

Stable: Yes

In-place: Yes

- It works well on small lists, or lists that are nearly sorted*
- number of inversions is n(n − 1)/2 in the worst case *(where input is in reverse sorted order)
- 0 in the best case (input is already sorted)*
- about n(n − 1)/4 on average case*

What is Selection Sorts best, worst and average runtimes? Is it stable and in-place?

Best, worst and avg are all

n²

Stable: No

In-place: Yes

*In practice, it is not as fast as insertion sort*

Shell Sort

Almost nothing is known about average-case running time of Shellsort.

**O(n 7/6 ) avg case**

*Values of h chosen from all relevant numbers of the form 2 i3 j have been proved to give O(n(log n) 2 ) running time*

Mergesort recurrence I

**C(n) = 2C(n/2) + n**

= 2(2C(n/4) + n/2) + n

= 4C(n/4) + 2n = . . .

= 2^{k}C(1) + kn

= **n lg n.**

Quicksort recurrence

Θ(nlogn)

if 1/n instead of 2/n we get

Θ(nl)

What are some mergesort properties?

Based on a recursive divide-and-conquer approach:

- If the list has 0 or 1 elements, done.
- Divide list into two lists of nearly equal size and recursively sort each half.
- Finally, merge the two sorted halves into one sorted list.

Worst-case running time of Θ(n log n)

One of the best external (disk) sorting algorithms.

Works well for linked lists in addition to arrays/vectors

What are some quicksort properties?

Quicksort is based on a recursive partitioning about a ‘pivot’:

- Pick any element as the pivot (many options here).
- Partition elements into three groups: less than (possibly equal to) pivot, equal to pivot, and more than (possibly equal to) pivot.
- Run quicksort on first and third partitions until one element.

In practice, a very fast sorting algorithm (almost twice as fast as mergesort)

On average good O(n lg n), but worst case input data leads to Ω( n^{2} ) performance

What are 3 different ways to choose a quicksort pivot?

- Use passive pivot strategy (e.g. fixed position in range)
- Use active pivot strategy (e.g. median-of-three)
- Use random pivot strategy (more likely O(n lg n) performance)

What is beadsort and what is its runtime complexity range?

Sorting algorithm which sorts positive integers by representing them in unary as a sequence of beads on a horizontal lines then uses gravity to sort them with the assistance of vertical rods

The algorithm’s run-time complexity ranges from O(1) to O(S), where S is the sum of the input integers

Quicksort recurrence relations and runtime

**Best case:** O(n lg n) is when partitioning gives partitions of the same size. Cost is:

T(n) = 2T((n − 1)/2) + n for unique elements

OR

T(n) = 2T(n/3) + n when duplicates allowed

**Worst case:** O( n^{2 }) is when partitioning gives unbalanced partitions.

T(n) = T(n − 1) + n