DAA Quiz 1/GLBITM

What is the time complexity of Quick Sort in the average case?

• O(log n)

• O(n)

• O(n log n)

• O(n^2)

The main key point behind Shell Sort and its advantages over simple insertion sort.

• Shell Sort improves efficiency over simple insertion sort by allowing exchanges of distant elements

• Shell Sort only works with small datasets.

• Insertion sort is faster than Shell Sort for all cases.

• Shell Sort does not allow any element exchanges.

Compare the time complexities of Merge Sort and Heap Sort. Which one is generally faster and why?

• Heap Sort is generally faster than Merge Sort.

• Merge Sort is generally faster than Heap Sort.

• Both algorithms have the same time complexity and speed.

• Merge Sort is slower due to its recursive nature.

What is the best-case time complexity of Merge Sort?

• O(log n)

• O(n^2)

• O(n log n)

• O(n)

Describe a scenario where using a linear time sorting algorithm is preferable over comparison-based sorting algorithms.

• Using comparison-based sorting algorithms is faster for sorting integers within a limited range.

• Linear time sorting algorithms are ideal for sorting large datasets with no known range.

• Using a linear time sorting algorithm is preferable when sorting integers within a known, limited range.

• Using a linear time sorting algorithm is best for sorting strings alphabetically.

Implement a basic version of Quick Sort in pseudocode.

• function quickSort(array) { if (array.length <= 1) { return array; } let pivot = array[array.length - 1]; let left = []; let right = []; for (let i = 0; i < array.length - 1; i++) { if (array[i] < pivot) { left.push(array[i]); } else { right.push(array[i]); } } return quickSort(left).concat(pivot, quickSort(right)); }

• function quickSort(array) { return array; }

• function quickSort(array) { for (let i = 0; i < array.length; i++) { left.push(array[i]); } }

• function quickSort(array) { let pivot = array[0]; }

What is the worst-case time complexity of Shell Sort?

• O(n log n)

• O(n^2)

• O(log n)

• O(n)

List the advantages and disadvantages of using Heap Sort compared to Quick Sort.

• Heap Sort is generally slower in practice compared to Quick Sort, but it guarantees O(n log n) time complexity in all cases.

• Quick Sort has a guaranteed O(n) time complexity.

• Heap Sort is not a comparison-based sorting algorithm.

• Heap Sort is faster than Quick Sort in all cases.

Explain how the choice of pivot affects the performance of Quick Sort.

• The pivot choice has no effect on the sorting process.

• The choice of pivot affects Quick Sort's performance by influencing the balance of partitions, impacting time complexity.

• Choosing the first element as a pivot always results in optimal performance.

• The pivot only affects the space complexity of Quick Sort.

What are the characteristics of sorting algorithms that operate in linear time, and can you name one?

• Bubble Sort

• Counting Sort

• Merge Sort

• Quick Sort