An array of 25 distinct elements is to be sorted using quicksort. 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 _____.

There are n unsorted arrays: A₁, A₂, ..., A_n. Assume that n is odd. Each of A₁, A₂, ..., A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁, A₂, ..., A_n is

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

The number of elements that can be sorted in Θ(log n) time using heap sort is

What is the number of swaps required to sort n elements using selection sort, in the worst case?

In quick sort, for sorting n elements, the (n/4)^th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort? 

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

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

In a permutation a₁...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 ?

In a permutation a₁...a_n of n distinct integers, an inversion is a pair (a_i, a_j) such that ii > 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?

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?

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. Which of the following statements is true?

A sorting technique is called stable if

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 two dimensional array A[1...n][1...n] of integers is partially sorted if

    ∀i, j ∈ [1...n−1],   A[i][j] < A[i][j+1] and 
                           A[i][j] < A[i+1][j] 

Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.

procedure  insert (x: integer);
var        i,j: integer;
begin
(1) i:=1; j:=1, A[i][j]:=x;
(2) while (x > ...... or x > ......) do
(3) if A[i+1][j] < A[i][j] ......... then begin
(4) A[i][j]:=A[i+1][j]; i:=i+1;
(5) end
(6) else begin
(7) ............
(8) end
(9) A[i][j]:= .............
    end  

Merge sort uses

Consider the following sequence of numbers

  92, 37, 52, 12, 11, 25  

Use bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.

Consider the recursive algorithm given below:

 procedure bubblersort (n);
 var i,j: index; temp : item;
 begin
    for i:=1 to n-1 do
    if A[i] > A [i+1] then
 begin
    temp : A[i];
    A[i]:=A[i+1]; 
    A[i+1]:=temp
    end;
   bubblesort (n-1)
 end 

Let a_n be the number of times the ‘if…then….’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining a_n in terms of a_n-1. Solve for a_n.

Following algorithm(s) can be used to sort n integers in the range [1...n³] in O(n) time

The minimum number of comparisons required to sort 5 elements is _____

Quicksort is ________ efficient than heapsort in the worst case.

Let P be a quicksort program to sort numbers in ascending order. Let t₁ and t₂ be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1] respectively. Which of the following holds?

If we use Radix Sort to sort n integers in the range [n^k/2, n^k], for some k>0 which is independent of n, the time taken would be?

Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the arrays are indexed starting from 0, consider the following four statements

1. a[i] ≥ b [i] => c[2i] ≥ a [i]
2. a[i] ≥ b [i] => c[2i] ≥ b [i]
3. a[i] ≥ b [i] => c[2i] ≤ a [i]
4. a[i] ≥ b [i] => c[2i] ≤ b [i] 

1. Quicksort
2. Heapsort
3. Mergesort

Which of the following data structures is most suitable for radix sort?

Consider an array with n elements. Which of the following options gives the maximum number of swap(a_j, a_j+1) operations to sort the array elements using efficient bubble sort algorithm?

The worst case time complexity of Quick Sort is __________

The worst case time complexity of Merge Sort is _______

Which of the following sorting procedures is the slowest?

Which of the following sorting methods would be most suitable for sorting a list which is almost sorted?

The running time of insertion sort is

A sort which compares adjacent elements in a list and switches where necessary is _________

The correct order of the efficiency of the following sorting algorithms according to their overall running time comparison is

A sort which iteratively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called

The algorithm that will efficiently sort an array that is nearly sorted except for the interchange of some adjacent pairs of numbers like {1,3,2,5,4,6} is

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quick sort runs in Q(n²) time
II. Bubble sort runs in Q(n²) time
III. Merge-sort runs in Q(n²) time
IV. Insertion sort runs in Q(n²) time

How much extra space is used by heap sort?

What is meant by stable sorting algorithm?

Consider the following statements
1. Insertion sort and merge sort are stable
2. Heap sort is inherently unstable
3. Selection sort is not inherently stable, but may be coded in such a way that it is stable

What is the complexity of merge sort?

Time complexity of Merge sort is

In which sorting algorithm average number of comparison is (n² – n) / 2?