Sorting Algorithms

Question 1

What are the three basic sorting algorithms?

Answer 1

1. Bubble Sort
2. Selection Sort
3. Insertion Sort

Question 2

What are the six advanced sorting algorithms?

Answer 2

1. Merge Sort
2. Heap Sort
3. Quick Sort
4. Counting Sort
5. Bucket Sort
6. Radix sort

Question 3

What is the runtime and stability of bubble sort?

Answer 3

Tbest: Theta(n)
Tworst: Theta (n^2)
Taverege: Theta (n^2)
Toverall: O(n^2)

Stability: Yes

Question 4

What is the runtime and stability of selection sort?

Answer 4

Tbest: Theta(n^2)
Tworst: Theta(n^2)
Taverege: Theta(n^2)
Toverall: Theta(n^2)

Stable: No

Question 5

What is the runtime and stability of insertion sort?

Answer 5

Tbest: Theta(n)
Tworst: Theta(n^2)
Taverege: Theta(n^2)
Toverall: O(n^2)

Stable: Yes

Question 6

Why is selection sort faster than bubble sort if their runtimes are the same?

Answer 6

Selection sort makes far fewer comparisons. This is selection sort makes exactly N(N-1)/2 comparisons

Question 7

What is the runtime, space, and stability of Merge Sort?

Answer 7

Runtime: Theta (N lgN)
Space: Theta (N)
Stable: Yes

Question 8

What is the runtime and stability of Heap Sort?

Answer 8

Runtime: Theta(N lgN)
Build Heap –> Theta(N)
Perform N deleteMin operations to retrieve the elements in sorted order –> O(lgN)

Space: O(N)
Stable: No

Question 9

What is the runtime and stability of Quick Sort , and what is challenging about implementing it?

Answer 9

Tbest: Theta (N lgN)
Tworst: Theta (n^2)

Stable: No

The most challenging aspect of heapsort is picking a pivot element.

Question 10

What is the runtime and stability of Counting Sort ?

Answer 10

Toverall: Theta (N+M)

Stable: Yes

Question 11

What are the runtime, space complexity, and stability of Bucket Sort?

Answer 11

Toverall: Theta (N+M)
Space: Theta (N+M)
Stable: Yes

Question 12

What is the runtime, space complexity, and stability of Radix Sort?

Answer 12

Tbest:
Tworst:
Taverege:
Toverall:

Stable:

Question 13

How does partitioning in place work (quick sort)?

Answer 13

Use swaps to push all elements x >= v to the right.

Question 14

What algorithm was introduced in class to partition quicksort arrays?

Answer 14

Lomuto Partition

Question 15

What is the most evident limitation of counting sort?

Answer 15

You need to use an array that with an index count large enough to match every value. This becomes impossible if you are storing large values.