Array Sorting Algorithms

Question 1

What is the best time complexity of quicksort?

Answer 1

O(n log(n)) - bad

Question 2

What is quicksort?

Answer 2

A divide and conquer algorithm where it divides the array into two smaller sub arrays. An index in each array is chosen as pivot, and the pivot compares itself to all the other entries so all smaller values are before it and all larger values are behind it. Recursively goes through each sub array (the one before and the one after the pivot position) and repeats.

Question 3

What is the average time complexity of quicksort?

Answer 3

O(n log(n)) - bad

Question 4

What is the worst time complexity of quicksort?

Answer 4

O(n^2) - terrible

Question 5

What is the worst space complexity of quicksort?

Answer 5

O(log(n)) - good

Question 6

What is merge sort?

Answer 6

A comparison based divide and conquer algorithm, where the list is divided into sublists of one element, then compared with an adjacent list to merge the two lists until it is sorted.

A new array needs to be allocated to store the sorted list.

Question 7

What is the best time complexity of merge sort?

Answer 7

O(n log(n)) - bad

Question 8

What is the average time complexity of merge sort?

Answer 8

O(n log(n)) - bad

Question 9

What is the worst time complexity of merge sort?

Answer 9

O(n log(n)) - bad

Question 10

What is the worst space complexity of merge sort?

Answer 10

O(n) - okay

Question 11

What is timsort?

Answer 11

An adaptive sorting algorithm designer by Tim Peters, where it identifies the longest “run” (sorted subarray) and chooses either insertion or merge sort.

Question 12

What is the best time complexity of timsort?

Answer 12

O(n) - great!

Question 13

What is the average time complexity of timsort?

Answer 13

O(n log(n)) - bad

Question 14

What is the worst time complexity of timsort?

Answer 14

O(n log(n)) - bad

Question 15

What is the worst space complexity of timsort?

Answer 15

O(n) - okay

Question 16

What is heapsort?

Answer 16

An in-place algorithm that builds a heap out is the data that is placed in an array in the layout of a binary tree. The sorting is done by repeatedly moving the largest element from the heap and inserting into array.

Question 17

What is the best time complexity of heapsort?

Answer 17

O(n log(n)) - bad

Question 18

What is the average time complexity of heapsort?

Answer 18

O(n log(n)) - bad

Question 19

What is the worst time complexity of heapsort?

Answer 19

O(n log(n)) - bad

Question 20

What is the worst space complexity of heapsort?

Answer 20

O(1) - great since it is done in place

Question 21

What is bubble sort?

Answer 21

A simple algorithm that begins from the beginning of the list and compares adjacent pairs and swaps their position if not sorted. It repeatedly goes through the list, which grows shorter each time as the larger values get sorted to the end.

Question 22

What is the best time complexity of bubble sort?

Answer 22

O(n) - good, only needs to go through once

Question 23

What is the worst space complexity of bubble sort?

Answer 23

O(1) - great, done in place

Question 24

What is the average time complexity of bubble sort?

Answer 24

O(n^2) - horrible

Question 25

What is the worst time complexity of bubble sort?

Answer 25

O(n^2) - horrible

Question 26

What is the best time complexity of insertion sort?

Answer 26

O(n) - great

Question 27

What is the average time complexity of insertion sort?

Answer 27

O(n^2) - horrible

Question 28

What is the worst time complexity of insertion sort?

Answer 28

O(n^2) - horrible

Question 29

What is the worst space complexity of insertion sort?

Answer 29

O(1) - great, done in place

Question 30

What is selection sort?

Answer 30

A simple but inefficient algorithm where it splits the array into two sublists, sorted and unsorted. It finds the smallest element in the unsorted list and exchanges it with element in leftmost position of unsorted list.

Question 31

What is the best time complexity of selection sort?

Answer 31

O(n^2) - horrible

Question 32

What is the average time complexity of selection sort?

Answer 32

O(n^2) - horrible

Question 33

What is the worst time complexity of selection sort?

Answer 33

O(n^2) - horrible

Question 34

What is the worst space complexity of selection sort?

Answer 34

O(1) - great

Question 35

What is insertion sort?

Answer 35

A super simple sorting algorithm where it removes one element from the list, finds where it belongs in the sorted list, and inserts it there. It can be performed online (as the list is being received).

Good for short lists, bad for long ones.

Question 35

What is bucket sort?

Answer 35

A comparison sorting algorithm that sets up an array of empty buckets. It distributes the contents of the original array in the buckets. Each non empty bucket is sorted, then each bucket is visited in order and put back in the original array.

Question 35

What is the best time complexity of bucket sort?

Answer 35

O(n + k), where K is number of buckets

Question 36

What is the average time complexity of bucket sort?

Answer 36

O(n + k), where K is number of buckets

Question 37

What is the worst time complexity of bucket sort?

Answer 37

O(n^2) - horrible

Question 38

What is the worst space complexity of bucket sort?

Answer 38

O(n) - okay

Question 39

What is radix sort?

Answer 39

A non-comparative sorting algorithm that sorts data with integer keys by grouping keys by individual digits that share the same significant digit position and value. Starts with 1s place, then 10s, then 100s, etc.

Question 40

What is the best time complexity of radix sort?

Answer 40

O(nk) - good, but k is variable

Question 41

What is the average time complexity of radix sort?

Answer 41

O(nk) - good, but k is variable

Question 42

What is the worst time complexity of radix sort?

Answer 42

O(nk) - good, but k is variable

Question 43

What is the worst space complexity of radix sort?

Answer 43

O(n+k)