The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged sorting
0
votes
0
answers
1
Sorting
Let P be a Quicksort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 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? A. t1 = 5 B. t1< t2 C. t1> t2 D. t1 = t2
asked
Aug 2
in
Algorithms
by
Solarica Palit
(
141
points)

23
views
sorting
+1
vote
2
answers
2
Sorting
Could a binary search tree be built using o(n lg n) comparisons in the comparison model? Explain why or why not.
asked
Aug 2
in
Algorithms
by
Ravi Dubey
(
133
points)

27
views
sorting
algorithms
timecomplexity
testseries
+1
vote
0
answers
3
Massachusetts Institute of Technology Professors Ron Rivest and Srini Devadas
asked
Jul 30
in
Algorithms
by
Rishav Kumar Singh
Active
(
2k
points)

17
views
sorting
+2
votes
3
answers
4
sorting
When the recurrence relation for both are same , why they both getting different result? Q1. In a modified merge sort, the input array is splitted at a position onethird of the length(N) of the array. What is the worst case time complexity of this merge sort? ANSWER: recurrence ... is If for first case it is N(log3/2N) then for second case also it should be N(log4/3N) BUT its not. WHY?
asked
Jul 30
in
Algorithms
by
Rishav Kumar Singh
Active
(
2k
points)

53
views
algorithms
sorting
timecomplexity
0
votes
1
answer
5
Searching
Q) Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that ab = k , k being a positive integer. a) O(logn) b) O(n) c)O(nlogn) d)O(n^2) Which of the option is Correct And Why?
asked
Jul 9
in
Algorithms
by
pradeepchaudhary
(
179
points)

225
views
algorithms
sorting
timecomplexity
binarysearch
0
votes
2
answers
6
Merge Sort
A list of n string, each of length n, is sorted into lexicographic order using the mergesort algorithm. The worst case running time of this computation is (A) (B) (C) (D)
asked
Jul 8
in
Algorithms
by
pradeepchaudhary
(
179
points)

94
views
mergesort
algorithms
sorting
merging
0
votes
1
answer
7
Sorting:
You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate? 1)QuickSort 2)MergeSort 3)HeapSort 4)Selection Sort Explain? How
asked
Jul 8
in
Algorithms
by
pradeepchaudhary
(
179
points)

81
views
sorting
algorithms
timecomplexity
heapsort
0
votes
2
answers
8
Quick Sort Time Complexity
Quick sort gives O(nlogn) worst case performance if the pivot is selected as: a) First element of the array b) Median of first, last and middle elements c) Arithmetic mean of the elements d) None of these Now, the answer is given as Option (b). But, ... order of elements and not on pivot element. So, answer should be option (d) i.e None of these Correct me if I am wrong
asked
Jul 1
in
Algorithms
by
garvit_vijai
(
11
points)

123
views
quicksort
sorting
timecomplexity
0
votes
2
answers
9
Number of comparison in the Sorted list
Suppose there are 4 sorted list of 16 elements each. If we merge these lists into a single sorted list of 64 elements. The key comparisons that are needed in the worst case using an efficient algorithm are ________.
asked
Jun 24
in
DS
by
srestha
Veteran
(
91.8k
points)

81
views
algorithms
sorting
0
votes
0
answers
10
Sorting
You are asked to sort 15 randomly generated numbers. One should prefer  1. Bubble Sort 2. Quick Sort 3. Merge Sort 4. Heap Sort Please explain why others 3 sorting algorithms except the answer can't be used ?
asked
Jun 15
in
Algorithms
by
Rahul Ranjan 1
(
141
points)

95
views
sorting
algorithms
timecomplexity
heapsort
mergesort
+1
vote
1
answer
11
Sorting
Which sorting algorithm is good if we already knew the range of number  Counting Sort OR Radix Sort
asked
Jun 5
in
DS
by
jatinkumar
(
219
points)

86
views
sorting
timecomplexity
algorithms
+1
vote
1
answer
12
Sorting
Which of the following sorting techniques have minimum number of comparision in best case? 1. Insertion Sort 2. Selection Sort 3. Merge Sort 4. Heap Sort 5.Quick Sort The answer is insertion sort but my doubt is in insertion sort algo. inside the for loop the while ... in best case.Wont it have O(n^2) Comparisons.Becasue comparisons will be done in all the cases weather its sorted or not.
asked
May 6
in
Algorithms
by
Na462
Active
(
4.5k
points)

110
views
sorting
algorithms
+3
votes
2
answers
13
PGEE 2018
Given an array of n elements, where each element is at most k away from its target position, which algorithm is best suitable for sorting and what will be time complexity of the algorithm ( Note since pgee paper are not provided I am unable to recall options)
asked
Apr 21
in
Algorithms
by
Tesla!
Boss
(
16.2k
points)

140
views
iiithpgee
algorithms
sorting
0
votes
1
answer
14
MY DOUBT: Worst case space complexity of Quick sort (NOT FOR A STRAIGHT ANSWER)
asked
Apr 21
in
DS
by
Akash Kumar Roy
(
473
points)

106
views
algorithms
sorting
datastructure
spacecomplexity
0
votes
1
answer
15
Sorting
asked
Mar 19
in
Algorithms
by
pankaj_vir
Loyal
(
9.2k
points)

138
views
testseries
sorting
algorithms
heapsort
radixsort
+3
votes
1
answer
16
Online and Offline Sorting Algorithms
How to know that whether a sorting algorithm is online or offline ? For example , Insertion sort is online but Merge Sort is offline..Please explain ..
asked
Mar 18
in
Algorithms
by
ankitgupta.1729
Loyal
(
6.6k
points)

119
views
algorithms
sorting
+1
vote
1
answer
17
Merge sort algorithm
Consider the modified merge sort where we divide array into 5 equal sub arrays instead if 2(as in standard merge sort).What is the time complexity if modified merge sort? Is there any improvement over standard merge sort?
asked
Mar 9
in
Algorithms
by
rahul sharma 5
Boss
(
24.5k
points)

230
views
algorithms
mergesort
sorting
timecomplexity
0
votes
1
answer
18
Radix Sort Problem
The complexity of Radix Sort is $O(wn)$, for $n$ keys which are integers of word size $w$. Here, $w=log_2(n^k)=k\times log_2(n)$ So, the complexity is $O(wn)=O(k\times log_2(n)\times n)$ For instance if size is $n^3$ the complexity ... nlogn)$ Then why we say radix sort sorts the input in linear time? Similar Concept used to solve : https://gateoverflow.in/3353/gate2008it43
asked
Feb 19
in
Algorithms
by
Na462
Active
(
4.5k
points)

86
views
algorithms
radixsort
timecomplexity
sorting
0
votes
1
answer
19
CMI2017A08
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)]. We sort these in ascending order by the second coordinate. Which of the following corresponds to a ... 7),(6, 5, 9)] [(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]
asked
Feb 5
in
Algorithms
by
Tesla!
Boss
(
16.2k
points)

166
views
cmi2017
algorithms
sorting
0
votes
0
answers
20
virtual gate sorting algo
An array of n distinct elements is said to be unsorted if for every index i such that 2 ≤ i ≤ n − 1, either A[i] > max{A[i − 1], A[i + 1]}, or A[i] < min{A[i − 1], A[i + 1]}. What is the timecomplexity of the fastest algorithm that takes as input a sorted array ... (n log n) but not O(n) (B) O(n) but not O( √n) (C) O( √n) but not O(log n) (D) O(log n) but not O(1)
asked
Jan 31
in
Algorithms
by
Utsav09
Active
(
1.1k
points)

78
views
sorting
testseries
virtualgate
algorithms
0
votes
0
answers
21
Merge Sort
Let A,B,C,D,E are sorted sequences having length 70,74,80,85,102 respectively.They are merged into a single sequence by merging together two sequences at a time.The minimum number of comparisons that will be needed by algorithm in best case for going merging is _________.
asked
Jan 31
in
Algorithms
by
VS
Loyal
(
8.9k
points)

240
views
mergesort
algorithms
sorting
+1
vote
1
answer
22
Worst Case Time Complexity
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?
asked
Jan 24
in
DS
by
vishal chugh
Active
(
1.7k
points)

326
views
algorithms
timecomplexity
datastructure
sorting
+2
votes
0
answers
23
number of comparison require in RADIX sort
asked
Jan 23
in
Algorithms
by
sunil sarode
Active
(
1.3k
points)

171
views
algorithms
sorting
radix
0
votes
1
answer
24
quick sort
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the best case performance is a) O(n2) b) O(nlogn) c) Θ(nlogn) d) O(n3)
asked
Jan 14
in
Algorithms
by
iarnav
Loyal
(
7.9k
points)

199
views
quicksort
algorithms
sorting
timecomplexity
+1
vote
0
answers
25
Sorting
Consider an execution of Quicksort with the first item of an array segment acting as pivot or splitter. After first pass of running quicksort on an array (Assume that we are sorting with increasing order)? 12,18,17,11,13,15,16,10 I want to know what will be the sequence for the first pass
asked
Dec 28, 2017
in
Algorithms
by
Subham Nagar
Junior
(
643
points)

136
views
sorting
algorithms
0
votes
1
answer
26
ISRODEC201748
Quicksort is run on $2$ inputs shown below to sort in ascending order : $1,2,3\ldots n$ $n,n1,n2\ldots 1$ Let $C$1 and $C2$ be the number of comparisons made for A and B respectively. Then, $C1>C2$ $C1=C2$ $C1<C2$ Cannot say anything for arbitrary $n$
asked
Dec 17, 2017
in
Algorithms
by
gatecse
Boss
(
18.1k
points)

772
views
isrodec2017
sorting
+1
vote
0
answers
27
Find the element that appears once in a sorted array.
asked
Dec 13, 2017
in
Algorithms
by
Tuhin Dutta
Loyal
(
7.9k
points)

197
views
algorithms
sorting
0
votes
1
answer
28
3way quicksort
3way partitioning is a modification of quicksort that partitioned the elements into groups smaller than,equal to and larger than pivot. Only the group of smaller and larger elements need to be sorted. If there are N items and K unique value the running time of modified quick sort is (A) O(nlogk) (B) O(klogn) (C) O(nk) (D) O(k^2)
asked
Dec 8, 2017
in
Algorithms
by
manish suthar
(
49
points)

193
views
algorithms
sortingalgorithmsquicksort
sorting
0
votes
1
answer
29
#swaps in case of reversely sorted array using bubble and insertion
asked
Dec 6, 2017
in
Algorithms
by
Tuhin Dutta
Loyal
(
7.9k
points)

104
views
algorithms
sorting
0
votes
0
answers
30
[Algorithms] Heap sort
Merging k sorted lists of size n/k into one sorted list of nelements using heap sort will take how much time ? My doubt First approach: here it is mentioned heap sort so, heap sort will always take nlogn.and here also we have n elements and it will ... give o(k)+(logk)*(n/k) I think answer should be nlogn only because the second approach is not heap sort. Please check.
asked
Nov 27, 2017
in
Algorithms
by
rahul sharma 5
Boss
(
24.5k
points)

120
views
algorithms
timecomplexity
sorting
heap
Page:
1
2
3
4
5
6
...
8
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
Recent Posts
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged sorting
Recent Blog Comments
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
Yes, their tracking system is incomplete. ...
India post don't update the tracking details. No ...
38,094
questions
45,586
answers
132,145
comments
49,110
users