sorting

Question 1

selection sort runtime

Answer 1

O(N^2)

Question 2

number of comparisons in selection sort

Answer 2

(N-1)*N/2

Question 3

How many times longer will sorting a list of 20 elements take compared to sorting a list of 10 elements?

Answer 3

20^2 / 10^2 = 4

Question 4

selection sort’s runtime grows _______with the input size

Answer 4

quadratically

Question 5

insertion sort runtine

Answer 5

O(N^2)

Question 6

in insertion sort the outer loops executes ______ times

Answer 6

N-1

Question 7

in insertion sort the inner loop executes on average _______ times

Answer 7

N/2

Question 8

First iteration (i = 1) requires at most 1 comparison, second iteration requires at most 2 comparison, the third 3 comparison, and so on.

Answer 8

x

Question 9

For sorted or nearly sorted inputs, insertion sort’s runtime is …

Answer 9

O(N)

Question 10

The worst-case performance for insertion sort is when the list elements are in…

Answer 10

descending order

Question 10

midpoint in quicksort

Answer 10

i + (k -i) / 2

Question 11

quicksort time complexity

Answer 11

O(N*logN)

Question 11

If the number of elements in the numbers array is even, the midpoint value is rounded …

Answer 11

down

Question 12

in quicksort there are ______ partitioning levels

Answer 12

log2 N

Question 13

in quicksort there are ______ comparisons

Answer 13

N * log2 N

Question 14

the worst case runtime for the quicksort algorithm is

Answer 14

O(N^2)

Question 15

In quickosrt the worst case, for N elements, there will be ______levels

Answer 15

N - 1

Question 16

worst case quickosrt, how many total comparisons are required to sort a list of N elements

Answer 16

N * (N-1)

Question 17

in selection sort the outer loop executes…

Answer 17

N - 1 times

Question 18

in selection sort the inner loop executes on average …

Answer 18

N/2 times

Question 19

the merge sort algorithm’s runtime is …

Answer 19

O(N log N)

Question 20

at each level, merge sort does about ___ comparisons

Answer 20

N

Question 21

merge sort has a total of ______ comparisons

Answer 21

N * log N

Question 22

Merge sort requires _____ additional memory

Answer 22

O(N)

Question 23

stable sorting algorithm

Answer 23

preserves the order of two data items with the same key