Recent questions tagged sorting - GATE CSE Doubts

0 votes

0 answers

Geeks for Geeks Topic Test
Which of the following is not true about comparison-based sorting algorithms. The minimum possible time complexity of a comparison-based sorting algorithm is O(N log N) for a random input array. Any comparison-based sorting algorithm can be made stable by using ... . Heap Sort is not a comparison-based sorting algorithm. Choose the correct option. 1,2. 2,4. 4. 2.

asked May 16 in Algorithms by ramcharantej_24 (22 points) | 8 views

0 votes

0 answers

GATE2014-3-14 Video Solution
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 $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$

asked Apr 18 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2013-30 Video Solution
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is $\Theta(1)$ $\Theta(\sqrt{\log} n)$ $\Theta(\frac{\log n}{\log \log n})$ $\Theta(\log n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2004-29 Video Solution
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2012-39 Video Solution
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 $O (n \log n) $ $ O(n^{2} \log n) $ $ O(n^{2} + \log n) $ $ O(n^{2}) $

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2005-39 Video Solution
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) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1999-1.14, ISRO2015-42 Video Solution
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$ ... $4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2014-2-38 Video Solution
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2006-52 Video Solution
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? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2006-14, ISRO2011-14 Video Solution
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2014-1-14 Video Solution
Let $P$ be 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 comparisons made by P for the inputs $[1 \ 2 \ 3 \ 4 \ 5]$ and $[4 \ 1 \ 5 \ 3 \ 2]$ respectively. Which one of the following holds? $t_1 = 5$ $t_1 < t_2$ $t_1>t_2$ $t_1 = t_2$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2003-62 Video Solution
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\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. ... at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2003-61 Video Solution
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\)? \(\frac{n(n-1)}{2}\) \(\frac{n(n-1)}{4}\) \(\frac{n(n+1)}{4}\) \(2n[\log_2n]\)

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1995-1.16 Video Solution
For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of $O(m)$ $O(n)$ $O(m+n)$ $O(\log m + \log n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2009-39 Video Solution
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2015-3-27 Video Solution
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$ minutes? $256$ $512$ $1024$ $2018$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2003-22 Video Solution
The unusual $\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 ... $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2015-2-45 Video Solution
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 elements less than or equal to the pivot is in the left ... and $(a, $ left_end$, k)$ $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1994-1.19, ISRO2016-31 Video Solution
Algorithm design technique used in quicksort algorithm is? Dynamic programming Backtracking Divide and conquer Greedy method

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2001-1.14 Video Solution
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? $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n!)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2008-IT-43 Video Solution
If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k > 0$ which is independent of $n$, the time taken would be? $\Theta(n)$ $\Theta(kn)$ $\Theta(n \log n)$ $\Theta(n^2)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2016-2-13 Video Solution
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in $\Theta (n^2)$ time Bubblesort runs in $\Theta (n^2)$ time Mergesort runs in ... time Insertion sort runs in $\Theta (n)$ time I and II only I and III only II and IV only I and IV only

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2008-43 Video Solution
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 $T(n) \leq 2T(n/5) + n$ $T(n) \leq T(n/5) + T(4n/5) + n$ $T(n) \leq 2T(4n/5) + n$ $T(n) \leq 2T(n/2) + n$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1987-1-xviii Video Solution
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 $\left[1 \ 2 \ 3 \ 4\right]$ and $\left[5 \ 4 \ 3 \ 2 \ 1\right]$, respectively. Which of the following holds? $t_{1} = t_{2}$ $t_{1} > t_{2}$ $t_{1} < t_{2}$ $t_{1}=t_{2}+5 \log 5$

asked Apr 18 in Algorithms by admin (3.6k points) | 4 views

0 votes

0 answers

GATE1999-1.12 Video Solution
A sorting technique is called stable if it takes $O (n \log n)$ time it maintains the relative order of occurrence of non-distinct elements it uses divide and conquer paradigm it takes $O(n)$ space

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE1991-01,vii Video Solution
The minimum number of comparisons required to sort $5$ elements is ____

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE1996-2.15 Video Solution
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, $C_1 < C_2$ $C_1 > C_2$ $C_1 = C_2$ we cannot say anything for arbitrary $n$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2005-IT-59 Video Solution
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 ... Which of the following is TRUE? only I and II only I and IV only II and III only III and IV

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1992-02,ix Video Solution
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Following algorithm(s) can be used to sort $n$ in the range $[1\ldots n^3]$ in $O(n)$ time Heap sort Quick sort Merge sort Radix sort

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2000-17 Video Solution
An array contains four occurrences of $0$, five occurrences of $1$, and three occurrences of $2$ in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent). What is the minimum number of swaps ... case? Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2015-1-2 Video Solution
Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n$ ( $\geq $ 2) numbers? In the recurrence equations given in the options below, $c$ is a constant. $T(n) = 2 T (n/2) + cn$ $T(n) = T ( n - 1) + T(1) + cn$ $T(n) = 2T ( n - 1) + cn$ $T(n) = T (n/2) + cn$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2013-6 Video Solution
Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort? $O(\log n$) $O(n$) $O(n \log n$) $O(n^{2}$)

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2009-11 Video Solution
What is the number of swaps required to sort $n$ elements using selection sort, in the worst case? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2016-1-13 Video Solution
The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are: $\Theta (n \log n)$, $\Theta (n \log n)$ and $\Theta(n^2)$ $\Theta (n^2)$, $\Theta (n^2)$ and $\Theta(n \log n)$ $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n \log n)$ $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n^2)$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1998-1.22 Video Solution
Give the correct matching for the following pairs: $\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(P)} & \text{Selection sort} \\\hline \text{(B)} & \text{$O (n)$} & \text{(Q)}& \text{Insertion sort} \\\hline \text{(C)}& \text{$O (n ... $\text{A-R B-P C-S D-Q}$ $\text{A-P B-R C-S D-Q}$ $\text{A-P B-S C-R D-Q}$

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2007-14 Video Solution
Which of the following sorting algorithms has the lowest worse-case complexity? Merge sort Bubble sort Quick sort Selection sort

asked Apr 18 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE1996-14 Video Solution
A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$ Fill in the blanks: The smallest item in the array is at $A[i][j]$ where $i=__$ and $j=__$. The ... if A[i+1][j] < A[i][j] ___ then begin A[i][j]:=A[i+1][j]; i:=i+1; end else begin _____ end A[i][j]:= ____ end

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1991-13 Video Solution
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1999-8 Video Solution
Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $3$rd smallest elements in minimum number of comparisons.

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE1992-03,iv Video Solution
Assume that the last element of the set is used as partition element in Quicksort. If $n$ distinct elements from the set $\left[1\dots n\right]$ are to be sorted, give an input for which Quicksort takes maximum time.

asked Apr 18 in Algorithms by admin (3.6k points) | 1 view

Page:

7,393 questions

1,744 answers

10,711 comments

90,368 users