Sorting Algorithms

Question 1

What are the Non-Recursive/Incremental Comparison Sorting Algorithms?

Answer 1

• Selection Sort
• Bubble Sort
• Insertion Sort

Question 2

What are the Best, Worst, and Average Case of Selection Sort Algorithm?

Answer 2

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

Question 3

What are the Best, Worst, and Average Case of Bubble Sort Algorithm?

Answer 3

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

Question 4

What are the Best, Worst, and Average Case of Modified Bubble Sort Algorithm?

Answer 4

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

Question 5

What are the Best, Worst, and Average Case of Insertion Sort Algorithm?

Answer 5

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

Question 6

What are the Recursive Comparison Sorting Algorithms?

Answer 6

• Merge Sort
• Quick Sort
• Heap Sort

Question 7

What are the Best, Worst, and Average Case of Merge Sort Algorithm?

Answer 7

Best: O(nlogn)
Worst: O(nlogn)
Average: O(nlogn)

Question 8

What are the Best, Worst, and Average Case of Quick Sort Algorithm?

Answer 8

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

Question 9

What are the Best, Worst, and Average Case of Heap Sort Algorithm?

Answer 9

Best: O(nlogn)
Worst: O(nlogn)
Average: O(nlogn)

Question 10

When should you use Strategy 1 (Pick the First Element in S) when picking a pivot?

Answer 10

If input is random and not sorted

Question 11

When should you use Strategy 2 (Pick the Pivot Randomly) when picking a pivot?

Answer 11

Random Number Generation is an expensive operation

Question 12

How do you find the pivot in Strategy w (Median-of-Three Partitioning)?

Answer 12

Median of the left-most, right-most, and center elements of array S

Question 13

What happens to Quick Sort when the array contains multiple duplicate elements?

Answer 13

Unstable

Question 14

What is the theorem for lower-bound comparison sorting?

Answer 14

To sort n elements, comparison sorts must make Ω(nlgn) comparisons in the worst case.