Sorting

Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations. A merge oper...

$$\text { The pseudocode of a function fun( ) is given below : }$$ fun(int A[0, .., n-1]) { for i = 0 to n-2 for j=0 to n-i-2 if (A[]]>A[j + 1]) then swap A[j] and A[j+1] } Let $A[0, \ldots, 29]$ be an array storing 30 d...

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?

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 firs...

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

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 ? $$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ Quicksort run...

Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of a[ ] as a pivot and rearranges the array so that all...

Assume that a mergesort algorithm in the worst case takes $$30$$ seconds for an input of size $$64.$$ Which of the following most closely approximates the maximum input size of a problem that can be solved in $$6$$ minut...

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equations given in the options below, c is a con...

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

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t 1 and t 2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Wh...

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

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation 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?

The coupling between different modules of a software is categorized as follows $${\rm I}.\,\,\,\,\,\,\,\,\,\,\,$$ Content coupling $${\rm II}.\,\,\,\,\,\,\,\,\,$$ Common coupling $${\rm III}.\,\,\,\,\,\,\,$$ Control coup...

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 com...

Which of the following sorting algorithms has the lowest worst-case complexity?

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?

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

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

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...

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?

Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

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 the second pass of the algorithm is:

A sorting technique is called stable if:

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1, 2, 3,......., n ii) n, n-1, n-2,......, 2, 1 Let C 1 and C 2 be the number of comparisons made for the inputs (i)...

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

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

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an input for which Quicksort takes maximum time.

Minimum number of comparisons required to sort 5 elements

Let P be a quicksort program to sort numbers in ascending order. Let t 1 and t 2 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?