1. Bubble Sort
2. Insertion Sort
3. Quick Sort
4. Merge Sort
5. Select Sort
6. Bucket Sort

Solved Example: 9972-01

Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ be the number of comparison made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds? (GATE CS 2014)

A. $t_1$ = 5

B. $t_1$ < $t_2$

C. $t_1$ > $t_2$

D. $t_1$ = $t_2$

Correct Answer: C

Solved Example: 9972-02

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64.

A. 256

B. 512

C. 1024

D. 2048

Correct Answer: B

Solved Example: 9972-03

An array of 25 distinct elements is to be sorted using quick sort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is: (GATE CS 2019)

A. 0.02

B. 0.04

C. 0.08

D. 0.16

Correct Answer: C

Solved Example: 9972-04

Consider the following array: \[23,32,45,69,72,73,89,97\] Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above array in ascending order? (GATE CS 2021 -Shift I)

A. Insertion sort

B. Selection sort

C. Quicksort using the last element as pivot

D. Merge sort

Correct Answer: A

Learning Objectives: Searching is interesting

wefaef

wergwerg

Solved Example: 9152-01

What is the space complexity of insertion sort?(Consider input size and additional storage)

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(1)

Correct Answer: A