Quiz 2

Question 1

Is heapsort a stable sorting algorithm?

Answer 1

No, it is not stable.

Question 2

Does heapsort sort in place?

Answer 2

Yes, it sorts in place.

Question 3

Is insertion sort stable?

Answer 3

Yes, insertion sort is stable.

Question 4

Is insertion sort in-place?

Answer 4

Yes, insertion sort operates in place.

Question 5

Is merge sort stable?

Answer 5

Yes, merge sort is stable.

Question 6

Is merge sort in-place?

Answer 6

No, merge sort requires extra space.

Question 7

What is the lower bound for comparison-based sorting algorithms?

Answer 7

Ω(n log n)

Question 8

What is the runtime of randomized quicksort in the average case?

Answer 8

O(nlogn)

Question 9

Is quicksort stable?

Answer 9

No, quicksort is not a stable sorting algorithm.

Question 10

Does quicksort sort in place?

Answer 10

Yes, quicksort operates in place.

Question 11

Is selection sort stable?

Answer 11

No, selection sort is not stable.

Question 12

Is selection sort in-place?

Answer 12

Yes, it sorts in place.

Question 13

What is heapsort?

Answer 13

Heapsort is a comparison-based sorting algorithm that sorts an array in place by building a heap data structure and extracting elements in order.

Question 14

How does heapsort work?

Answer 14

Heapsort works by first organizing the data into a binary heap. The largest element is placed at the root. Then it repeatedly extracts the root and places it at the end of the sorted array. With each extraction, the heap property is restored.

Question 15

What is the worst case runtime complexity of heapsort?

Answer 15

O(nlogn)

Question 16

What is the space complexity of heapsort?

Answer 16

O(1). Heapsort operates in place, requiring constant extra space.

Question 17

When should heapsort be preferred over other sorting algorithms?

Answer 17

When fast in-place sorting is required. The O(nlogn) runtime is comparable to efficient algorithms like quicksort, but heapsort has the advantage of being in-place.

Question 18

What is insertion sort?

Answer 18

Insertion sort iterates through the array, swapping the current element with others to insert it in the correct sorted position.

Question 19

What is the best case runtime complexity of insertion sort?

Answer 19

O(n) when the array is already sorted.

Question 20

What is the average and worst case runtime complexity of insertion sort?

Answer 20

O(n^2)

Question 21

When is insertion sort preferred?

Answer 21

For small or mostly sorted data. The simplicity provides advantages in these cases.

Question 22

What is merge sort?

Answer 22

Merge sort divides the array recursively into halves until single elements remain. It then merges the smaller sorted arrays to produce the final sorted array.

Question 23

What is the runtime complexity of merge sort?

Answer 23

O(nlogn) for all cases.

Question 24

What are the space requirements of merge sort?

Answer 24

O(n) auxiliary space is required. It is not an in-place sort.

Question 25

When should merge sort be used over other O(nlogn) algorithms?

Answer 25

When a stable sort is required. Merge sort is stable, unlike quicksort and heapsort.

Question 26

What is quicksort?

Answer 26

Quicksort picks a pivot element and partitions the array into two subarrays of elements less than and greater than the pivot. It recursively sorts the subarrays.

Question 27

What is the runtime complexity of quicksort?

Answer 27

O(nlogn) average case. O(n^2) worst case.

Question 28

How can quicksort's worst case be improved?

Answer 28

Choosing the pivot randomly or the median of a sample.

Question 29

What are the space requirements of quicksort?

Answer 29

O(logn) space for call stack. O(n) total space. In-place.

Question 30

When is quicksort preferred over other sorts?

Answer 30

Its in-place nature and O(nlogn) average case make it one of the fastest sorts.

Question 31

What is selection sort?

Answer 31

Selection sort repeatedly finds the minimum remaining element and swaps it into the next position.

Question 32

What is the runtime complexity of selection sort?

Answer 32

O(n^2) in all cases.

Question 33

What are the advantages of selection sort?

Answer 33

Simple implementation. Minimal data movement.

Question 34

What is quick select?

Answer 34

Quick select finds the kth smallest element in an unsorted array, based on the quicksort partitioning approach.

Question 35

What is the runtime complexity of quick select?

Answer 35

O(n) average case. O(n^2) worst case.

Question 36

When should quick select be used instead of sorting?

Answer 36

When only a few order statistics are needed instead of full sorting.