sorting Flashcards
selection sort runtime
O(N^2)
number of comparisons in selection sort
(N-1)*N/2
How many times longer will sorting a list of 20 elements take compared to sorting a list of 10 elements?
20^2 / 10^2 = 4
selection sort’s runtime grows _______with the input size
quadratically
insertion sort runtine
O(N^2)
in insertion sort the outer loops executes ______ times
N-1
in insertion sort the inner loop executes on average _______ times
N/2
First iteration (i = 1) requires at most 1 comparison, second iteration requires at most 2 comparison, the third 3 comparison, and so on.
x
For sorted or nearly sorted inputs, insertion sort’s runtime is …
O(N)
The worst-case performance for insertion sort is when the list elements are in…
descending order
midpoint in quicksort
i + (k -i) / 2
quicksort time complexity
O(N*logN)
If the number of elements in the numbers array is even, the midpoint value is rounded …
down
in quicksort there are ______ partitioning levels
log2 N
in quicksort there are ______ comparisons
N * log2 N
the worst case runtime for the quicksort algorithm is
O(N^2)
In quickosrt the worst case, for N elements, there will be ______levels
N - 1
worst case quickosrt, how many total comparisons are required to sort a list of N elements
N * (N-1)
in selection sort the outer loop executes…
N - 1 times
in selection sort the inner loop executes on average …
N/2 times
the merge sort algorithm’s runtime is …
O(N log N)
at each level, merge sort does about ___ comparisons
N
merge sort has a total of ______ comparisons
N * log N
Merge sort requires _____ additional memory
O(N)
