Sorting

Question 1

How does Quick Sort work?

Answer 1

1. Randomly select a pivot
2. Using the left index and right index, increment the left index and decrement the right index until the left index finds a value that is greater than pivot, and the right index finds a value that is less than pivot. Swap those values. Continue until left index == right index.
3. Swap the pivot with the left index when it is over.
4. Recursively execute the quick sort on the left partition and right partition of the array.

Question 2

What is the best and worst case time complexity of Quick Sort?

Answer 2

Best: O(nlogn)
Worst: O(n^2)

Question 3

What is the best and worst case space complexity of Quick Sort?

Answer 3

Best: logn
Worst: n

Question 4

How does Merge Sort work?

Answer 4

Divide and Conquer (Recursive algorithm)
1. Split the array into the left and right halves and keep on splitting until they reach their individual elements
2. Merge the individual elements into a sorted sublist -> 1 & 3 -> 1,3.
3. With each sorted sublist, compare the first element of each sublist and add the smaller element to a combined list. After adding, increment the index until one of the sublist runs out and add the remaining elements of the other list.

Question 5

What is the best and worst case time complexity of Merge Sort?

Answer 5

O(nlogn)

Question 6

What is the best and worst case space complexity of Quick Sort?

Answer 6

log n

Question 7

How does Insertion Sort work?

Answer 7

1. For each element from the second element of the list to the end, traverse each element to the left side of it and if that element is greater than the reference element, shift the element to the right. Once it finds an element smaller than it, stop and insert it there.

Question 8

What is the best and worst case time complexity of Insertion Sort?

Answer 8

Best: O(n)
Worst: O(n^2)

Question 9

What is the best and worst case space complexity of Insertion Sort?

Answer 9

Best and Worst: O(1)

Question 10

How does Bubble Sort work?

Answer 10

1. For each element from the first to the second last, compare it to the element ahead of it. If it is greater, swap. Through the first iteration, the greatest number will be at the end of the list, and through the second iteration, the second greatest number will be the second last element of the list.

Question 11

What is the best and worst case time complexity of Bubble Sort?

Answer 11

Best: O(n)
Worst: O(n^2)

Question 12

What is the best and worst case space complexity of Bubble Sort?

Answer 12

Best and Worst: O(1)

Question 13

How doe Selection Sort work?

Answer 13

1. For each element from the first to the second last, compare it with every element to the right of it and find the minimum. Swap the minimum with the element.

Question 14

What is the best and worst case time complexity of Selection Sort?

Answer 14

best case and worst case: O(n^2)

Question 15

What is the best and worst case space complexity of Bubble Sort?

Answer 15

best & worst cases: O(1)

Question 16

Is Selection Sort in-place and stable?

Answer 16

In-place but not stable

Question 17

Is Insertion Sort in-place and stable?

Answer 17

Both In-place and stable

Question 18

Is Bubble Sort in-place and stable?

Answer 18

Both In-place and stable

Question 19

Is Merge Sort in-place and stable?

Answer 19

Not In Place but Stable

Question 20

Is Radix Sort in-place and stable?

Answer 20

Not In Place but Stable