GATE CS Searching, Sorting, Hashing questions

The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j.$ What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of $1. . . n$ with at most $n$ inversions?

In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$?

The usual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates?

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort?

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$ then the order of these elements after second pass of the algorithm is:

A sorting technique is called stable if

Give the correct matching for the following pairs: …

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot $1, 2, 3, \dots n$ $n, n-1, n-2, \dots, 2, 1$ Let $C_1$ and $C_2$ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

The average number of key comparisons required for a successful search for sequential search on $n$ items is

For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of

Merge sort uses:

Algorithm design technique used in quicksort algorithm is?

Following algorithm(s) can be used to sort $n$ in the range $[1\ldots n^3]$ in $O(n)$ time

The minimum number of comparisons required to sort $5$ elements is ______

The complexity of comparison based sorting algorithms is: