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
Blogs
Previous Year
Exams
Recent questions tagged sorting
0
votes
1
answer
Selection sort
Can anybody explain me why the number of swaps in selection sort algorithm is (n1) in worst case ? Let's say the array is {6,5,4,3,2,1} then the number of swaps should be 5. But I think the no of swaps should be 3. Please explain.
asked
Feb 7
in
Algorithms
by
Akshay0798
(
7
points)

35
views
algorithms
sorting
0
votes
0
answers
Previous Year GATE
The number of elements that can be sorted in Θ(log n) time using heap sort is ___________ .
asked
Jan 17
in
Algorithms
by
Rishav Chetan
(
9
points)

17
views
sorting
+1
vote
1
answer
NIELIT NIC STA 2020 setC ques 80
Given array is {1,2,4,3}. Bubble sort is used to sort it. How many passes will be done to sort the array? 4 2 1 3 Answer given is 3 but I am getting 2. Need to confirm before challenging the key :)
asked
Nov 26, 2020
in
Programming
by
ayush.5
(
99
points)

38
views
sorting
+1
vote
1
answer
NIELIT STA 2018
Given an random unsorted array ‘A’ in which every element is at most ‘d’ distance from is position in sorted array where d<Size(A). If we applied the insertion sort over this array, then the time complexity of algorithm is: O($n\log d$) O($n^2\log d$) O($nd$) O($n^2d$)
asked
Nov 18, 2020
in
Algorithms
by
Sudarshan Bandyopadh
(
11
points)

41
views
algorithms
sorting
timecomplexity
0
votes
1
answer
Deletion in heap
How to delete the last node in a maxheap or minheap? Do we delete it directly or like in normal case replace it with itself then call max heapify on it and then finally decrease heap size?
asked
Oct 11, 2020
in
Algorithms
by
RasMalai
(
27
points)

40
views
sorting
algorithms
selfdoubt
0
votes
0
answers
Question on heap from MIT quiz
Link: https://ocw.mit.edu/courses/electricalengineeringandcomputerscience/6006introductiontoalgorithmsspring2008/exams/quiz1.pdf
asked
Oct 10, 2020
in
Algorithms
by
RasMalai
(
27
points)

18
views
sorting
0
votes
1
answer
UGC NET CS 2015 Jun  II
Which of the following algorithms sort n integers, having the range 0 to (n2  1), in ascending order in O(n) time ? A Selection sort B Bubble sort C Radix sort D Insertion sort
asked
Sep 24, 2020
in
Algorithms
by
Musa
(
5
points)

19
views
sorting
0
votes
0
answers
#madeeasytestseries
Assume each item is a 8 digit octal number and the maximum number of comparisons needed to sort 10 items using radix sort is________? according to me answer should be zero bcz radix sort is non comparision base algorithm but they give this explanation The max. no ... number having→ 8 digits The octal number system base value is → 8 So, items*digits*base=10*8*8=640 answer=640
asked
Aug 28, 2020
in
Algorithms
by
404 found
(
37
points)

35
views
algorithms
sorting
0
votes
0
answers
Algorithms Concept doubt
Can some one give examples of External Sorting Algorithms ?
asked
Aug 17, 2020
in
Algorithms
by
Shivateja MST
(
45
points)

40
views
algorithms
sorting
0
votes
2
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, 2020
in
Algorithms
by
ramcharantej_24
(
13
points)

148
views
algorithms
sorting
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, 2020
in
Algorithms
by
admin
(
573
points)

13
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, 2020
in
Algorithms
by
admin
(
573
points)

10
views
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, 2020
in
Algorithms
by
admin
(
573
points)

9
views
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, 2020
in
Algorithms
by
admin
(
573
points)

12
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, 2020
in
Algorithms
by
admin
(
573
points)

8
views
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

8
views
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

8
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

9
views
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

6
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

9
views
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, 2020
in
Algorithms
by
admin
(
573
points)

8
views
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, 2020
in
Algorithms
by
admin
(
573
points)

6
views
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, 2020
in
Algorithms
by
admin
(
573
points)

8
views
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, 2020
in
Algorithms
by
admin
(
573
points)

12
views
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, 2020
in
Algorithms
by
admin
(
573
points)

8
views
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

11
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, 2020
in
Algorithms
by
admin
(
573
points)

10
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, 2020
in
Algorithms
by
admin
(
573
points)

5
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

54
views
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, 2020
in
Algorithms
by
admin
(
573
points)

7
views
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, 2020
in
Algorithms
by
admin
(
573
points)

32
views
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, 2020
in
Algorithms
by
admin
(
573
points)

5
views
gate20151
algorithms
recurrence
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.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
9,095
questions
3,154
answers
14,583
comments
95,939
users