Sorting

Question 1

Insertion Best Case

Answer 1

O(n)

Question 2

Insertion Avg Case

Answer 2

O(n^2)

Question 3

Insertion Worst Case

Answer 3

O(n^2)

Question 4

Selection Best Case

Answer 4

O(n^2)

Question 5

Selection Avg Case

Answer 5

O(n^2)

Question 6

Selection Worst Case

Answer 6

O(n^2)

Question 7

Heap Best Case

Answer 7

O(n log n)

Question 8

Heap Avg Case

Answer 8

O(n log n)

Question 9

Heap Worst Case

Answer 9

O(n log n)

Question 10

Merge Best Case

Answer 10

O(n log n)

Question 11

Merge Avg Case

Answer 11

O(n log n)

Question 12

Merge Worst Case

Answer 12

O(n log n)

Question 13

Quick Best Case

Answer 13

O(n log n)

Question 14

Quick Avg Case

Answer 14

O(n log n)

Question 15

Quick Worst Case

Answer 15

O(n^2)

Question 16

Sorts that are easy on Linked List

Answer 16

Insertion, Selection, Merge, Quick

Question 17

Sorts difficult for Linked List

Answer 17

Heap Sort

Question 18

Sorts great for arrays

Answer 18

Insertion, Selection, Quick

Question 19

Sorts bad for arrays

Answer 19

Merge Sort, you need additional array

Question 20

Stability

Answer 20

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Question 21

Stable Sorts

Answer 21

Insertion, Bubble, Merge [IBM] ** Selection can be made stable easily, Linked List version of Quick Sort as well

Question 22

What is the BEST that a comparison based sorting algorithm can run?

Answer 22

O(n log n). Because making 2 way decisions take too long.

Question 23

Stable

Answer 23

Items with equal keys come out in same order they went in

Question 24

Non Stable sorts

Answer 24

Heap Sort ** can still be made stable with secondary key

Question 25

Bucket Best Case

Answer 25

O(n + k) k: number of buckets

Question 26

Bucket Avg Case

Answer 26

O(n + k) k: number of buckets

Question 27

Bucket Worst Case

Answer 27

O(n^2)

Question 28

Radix Best

Answer 28

O(nk)

Question 29

Radix Average

Answer 29

O(nk)

Question 30

Radix Worst

Answer 30

O(nk)