Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Year
Exams
Recent questions tagged sorting
0
votes
0
answers
Geeks for Geeks Topic Test
Which of the following is not true about comparisonbased sorting algorithms. The minimum possible time complexity of a comparisonbased sorting algorithm is O(N log N) for a random input array. Any comparisonbased sorting algorithm can be made stable by using ... . Heap Sort is not a comparisonbased sorting algorithm. Choose the correct option. 1,2. 2,4. 4. 2.
asked
May 16
in
Algorithms
by
ramcharantej_24
(
22
points)

8
views
algorithms
sorting
#gate
0
votes
0
answers
GATE2014314 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
gate20143
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE201330 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
gate2013
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE200429 Video Solution
The tightest lower bound on the number of comparisons, in the worst case, for comparisonbased 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
gate2004
algorithms
sorting
asymptoticnotations
easy
videosolution
0
votes
0
answers
GATE201239 Video Solution
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the mergesort 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
gate2012
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE200539 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
gate2005
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE19991.14, ISRO201542 Video Solution
If one uses straight twoway 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
gate1999
algorithms
sorting
normal
isro2015
videosolution
0
votes
0
answers
GATE2014238 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
gate20142
algorithms
sorting
normal
numericalanswers
videosolution
0
votes
0
answers
GATE200652 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
gate2006
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE200614, ISRO201114 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
gate2006
algorithms
sorting
easy
isro2011
videosolution
0
votes
0
answers
GATE2014114 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
gate20141
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE200362 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
gate2003
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE200361 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(n1)}{2}\) \(\frac{n(n1)}{4}\) \(\frac{n(n+1)}{4}\) \(2n[\log_2n]\)
asked
Apr 18
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2003
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE19951.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
gate1995
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE200939 Video Solution
In quicksort, 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
gate2009
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE2015327 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
gate20153
algorithms
sorting
videosolution
0
votes
0
answers
GATE200322 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
gate2003
algorithms
sorting
timecomplexity
normal
videosolution
0
votes
0
answers
GATE2015245 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
gate20152
algorithms
normal
sorting
videosolution
0
votes
0
answers
GATE19941.19, ISRO201631 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
gate1994
algorithms
sorting
easy
isro2016
videosolution
0
votes
0
answers
GATE20011.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
gate2001
algorithms
sorting
timecomplexity
easy
videosolution
0
votes
0
answers
GATE2008IT43 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
gate2008it
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE2016213 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
gate20162
algorithms
sorting
timecomplexity
normal
ambiguous
videosolution
0
votes
0
answers
GATE200843 Video Solution
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth 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
gate2008
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE19871xviii 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
gate1987
algorithms
sorting
videosolution
0
votes
0
answers
GATE19991.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 nondistinct elements it uses divide and conquer paradigm it takes $O(n)$ space
asked
Apr 18
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate1999
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE199101,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
gate1991
normal
algorithms
sorting
videosolution
0
votes
0
answers
GATE19962.15 Video Solution
Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot $1, 2, 3, \dots n$ $n, n1, n2, \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
gate1996
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE2005IT59 Video Solution
Let $a$ and $b$ be two sorted arrays containing $n$ integers each, in nondecreasing 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
gate2005it
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE199202,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
gate1992
easy
algorithms
sorting
videosolution
0
votes
0
answers
GATE200017 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
gate2000
algorithms
sorting
normal
descriptive
videosolution
0
votes
0
answers
GATE201512 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
gate20151
algorithms
recurrence
sorting
easy
videosolution
0
votes
0
answers
GATE20136 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
gate2013
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE200911 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
gate2009
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE2016113 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
gate20161
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE19981.22 Video Solution
Give the correct matching for the following pairs: $\begin{array}{llll}\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{AR BP CS DQ}$ $\text{AP BR CS DQ}$ $\text{AP BS CR DQ}$
asked
Apr 18
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1998
algorithms
sorting
easy
videosolution
0
votes
0
answers
GATE200714 Video Solution
Which of the following sorting algorithms has the lowest worsecase complexity? Merge sort Bubble sort Quick sort Selection sort
asked
Apr 18
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2007
algorithms
sorting
timecomplexity
easy
videosolution
0
votes
0
answers
GATE199614 Video Solution
A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n1], 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
gate1996
algorithms
sorting
normal
videosolution
0
votes
0
answers
GATE199113 Video Solution
Give an optimal algorithm in pseudocode 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 timecomplexity of your algorithm.
asked
Apr 18
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1991
sorting
timecomplexity
algorithms
difficult
videosolution
0
votes
0
answers
GATE19998 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
gate1999
algorithms
sorting
normal
descriptive
videosolution
0
votes
0
answers
GATE199203,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
gate1992
algorithms
sorting
easy
videosolution
Page:
1
2
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Jun 2020
nehaPal13
7 Points
Radheram
6 Points
vps123
4 Points
ummokkate
1 Points
Musa
1 Points
AliH
1 Points
DukeThunders
1 Points
Doraemon
1 Points
kpc
1 Points
Kushagra गुप्ता
1 Points
7,393
questions
1,744
answers
10,711
comments
90,368
users