sorting algorithm

Question 1

quicksort: best, avg, worst

Answer 1

best: nlogn
avg: nlogn
worst: n^2

Question 2

mergesort: best, avg, worst

Answer 2

best: nlogn
avg: nlogn
worst: nlogn

Question 3

heapsort: best, avg, worst

Answer 3

best: nlogn
avg: nlogn
worst: nlogn

Question 4

insertion sort: best, avg, worst

Answer 4

best: n
avg: n^2
worst: n^2

Question 5

selection: best, avg, worst

Answer 5

best: n^2
avg: n^2
worst: n^2

Question 6

shell sort: best, avg, worst

Answer 6

best: nlogn
avg: n^(4/3)
worst: n^(3/2)

Question 7

radix sort: best, avg, worst

Answer 7

best: n
avg: n
worst: n

Question 8

quicksort: stable, fast, comparison

Answer 8

stable: no
fast: yes
comparison: yes

Question 9

mergesort: stable, fast, comparison

Answer 9

stable: yes
fast: yes
comparison: yes

Question 10

heapsort: stable, fast, comparison

Answer 10

stable: no
fast: yes
comparison: yes

Question 11

insertion sort: stable, fast, comparison

Answer 11

stable: yes
fast: no
comparison: yes

Question 12

selection sort: stable, fast, comparison

Answer 12

stable: no
fast: no
comparison: yes

Question 13

shell sort: stable, fast, comparison

Answer 13

stable: no
fast: no
comparison: yes

Question 14

radix sort: stable, fast, comparison

Answer 14

stable:

fast: yes
comparison: no

Question 15

what makes a sorting algorithm stable?

Answer 15

can handle duplicates

Question 16

what makes a sorting algorithm fast?

Answer 16

a runtime complexity of O(NlogN) or better

Question 17

what makes a sorting algorithm a comparison sorting algorithm?

Answer 17

operates on an array of elements that can be compared to each other