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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged sorting
+1
vote
2
answers
1
ISRO202033
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort ? $67,12,10,5,4,7,23$ $4,7,10,23,67,12,5$ $4,5,7,67,10,12,23$ $10,7,4,67,23,12,5$
asked
Jan 13
in
Algorithms
by
Satbir
Boss
(
23.8k
points)

95
views
isro2020
algorithms
sorting
normal
+1
vote
2
answers
2
ISRO202065
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input? Insertion sort Quick sort Merge sort Selection sort
asked
Jan 13
in
Algorithms
by
Satbir
Boss
(
23.8k
points)

91
views
isro2020
algorithms
sorting
normal
0
votes
0
answers
3
Cormen Edition 3 Exercise 8.4 Question 5 (Page No. 204)
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear averagecase time.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

77
views
cormen
algorithms
sorting
bucketsort
descriptive
difficult
0
votes
0
answers
4
Cormen Edition 3 Exercise 8.4 Question 4 (Page No. 204)
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2, .,n$.Suppose that the points are uniformly distributed; that is, the probability of finding a point in ... the origin. (Hint: Design the bucket sizes in BUCKETSORT to reflect the uniform distribution of the points in the unit circle.)
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

30
views
cormen
algorithms
sorting
bucketsort
descriptive
difficult
0
votes
1
answer
5
Cormen Edition 3 Exercise 8.4 Question 3 (Page No. 204)
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

39
views
cormen
algorithms
sorting
bucketsort
expectation
descriptive
0
votes
0
answers
6
Cormen Edition 3 Exercise 8.4 Question 2 (Page No. 204)
Explain why the worstcase running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear averagecase running time and makes its worstcase running time $O(n\ lg\ n)$?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

27
views
cormen
algorithms
sorting
bucketsort
descriptive
0
votes
1
answer
7
Cormen Edition 3 Exercise 8.4 Question 1 (Page No. 204)
BUCKETSORT(A) 1 let B[0...n1] be a new array 2 n = A.length 3 for i  0 to n  1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i = 0 to n  1 8 sort list B[i] with ... ,B[n1] together in order illustrate the operation of BUCKETSORT on the array $A=\langle .79,.13,.16,.64,.39,.20,.89,.53,.71,.42\rangle$
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

41
views
cormen
algorithms
sorting
bucketsort
descriptive
+1
vote
1
answer
8
Cormen Edition 3 Exercise 8.3 Question 4 (Page No. 200)
Show how to sort $n$ integers in the range $0$ to $n^31$ in $O(n)$ time.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

61
views
cormen
algorithms
sorting
radixsort
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 8.3 Question 3 (Page No. 200)
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

20
views
cormen
algorithms
sorting
radixsort
descriptive
0
votes
2
answers
10
Cormen Edition 3 Exercise 8.3 Question 2 (Page No. 200)
Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

47
views
cormen
algorithms
sorting
stablesort
descriptive
0
votes
1
answer
11
Cormen Edition 3 Exercise 8.3 Question 1 (Page No. 199)
RADIXSORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digit i illustrate the operation of RADIXSORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

31
views
cormen
algorithms
sorting
radixsort
descriptive
0
votes
0
answers
12
Cormen Edition 3 Exercise 8.2 Question 4 (Page No. 197)
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the range $[a..b]$ in $O(1)$ time.Your algorithm should use $\Theta(n+k)$ preprocessing time.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

32
views
cormen
algorithms
sorting
countingsort
descriptive
0
votes
0
answers
13
Cormen Edition 3 Exercise 8.2 Question 3 (Page No. 196)
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.length Show that the algorithm still works properly. Is the modified algorithm stable?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

15
views
cormen
algorithms
sorting
countingsort
descriptive
0
votes
0
answers
14
Cormen Edition 3 Exercise 8.2 Question 2 (Page No. 196)
Prove that COUNTINGSORT is stable.
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

17
views
cormen
algorithms
sorting
countingsort
descriptive
0
votes
0
answers
15
Cormen Edition 3 Exercise 8.2 Question 1 (Page No. 196)
COUNTINGSORT(A, B, k) 1 let C[0, ,k] be a new array 2 for i = 0 to k 3 C[i] = 0 4 for j = 1 to A.length 5 C[A[j]] = C[A[j]] + 1 6 // C[i] now contains the number of elements equal to i . 7 for i =1 to k 8 C[i] = C[ ... j] 12 C[A[j]] = C[A[j]]  1 illustrate the operation of COUNTINGSORT on the array $A=\langle 6,0,2,0,1,3,4,6,1,3,2 \rangle $
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

25
views
cormen
algorithms
sorting
countingsort
descriptive
0
votes
0
answers
16
Cormen Edition 3 Exercise 8.1 Question 4 (Page No. 194)
Suppose that you are given a sequence of $n$ elements to sort.The input sequence consists of $n/k$ subsequences, each containing $k$ elements.The elements in a given subsequence are all smaller than the elements in the ... of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

34
views
cormen
algorithms
sorting
descriptive
0
votes
0
answers
17
Cormen Edition 3 Exercise 8.1 Question 3 (Page No. 194)
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

18
views
cormen
algorithms
sorting
descriptive
0
votes
1
answer
18
Cormen Edition 3 Exercise 8.1 Question 1 (Page No. 193)
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
asked
Jun 28, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

25
views
cormen
algorithms
sorting
descriptive
0
votes
0
answers
19
Cormen Edition 3 Exercise 7.1 Question 2 (Page No. 174)
What value of $q$ does PARTITION return when all elements in the array $A[p..r]$ have the same value? Modify PARTITION so that $q=\lfloor(p+r)/2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

18
views
cormen
algorithms
sorting
quicksort
descriptive
0
votes
0
answers
20
Cormen Edition 3 Exercise 7.1 Question 1 (Page No. 173)
PARTITION(A,p,r) 1 x = A[r] 2 i = p – 1 3 for j = p to r – 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 illustrate the operation of PARTITION on the array $A=\langle 13,19,9,5,12,8,7,4,21,2,6,11\rangle$
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

25
views
cormen
algorithms
sorting
quicksort
descriptive
0
votes
1
answer
21
Cormen Edition 3 Exercise 2.3 Question 4 (Page No. 38)
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n1]$. Write a recurrence for the running time of this recursive version of insertion sort.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

41
views
cormen
algorithms
sorting
timecomplexity
descriptive
0
votes
0
answers
22
Cormen Edition 3 Exercise 2.3 Question 2 (Page No. 37)
Rewrite the MERGE procedure so that it does not use sentinels, instead of stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

19
views
cormen
algorithms
sorting
mergesort
descriptive
0
votes
1
answer
23
Cormen Edition 3 Exercise 2.3 Question 1 (Page No. 37)
Using Figure $2.4$ as a model, illustrate the operation of merge sort on the array $A=\langle 3,41,52,26,38,57,9,49 \rangle $
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

31
views
cormen
algorithms
sorting
mergesort
descriptive
0
votes
1
answer
24
Cormen Edition 3 Exercise 2.1 Question 2 (Page No. 22)
Rewrite the INSERTIONSORT procedure to sort into nonincreasing instead of nondecreasing order.
asked
Jun 25, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

26
views
cormen
algorithms
sorting
descriptive
0
votes
0
answers
25
Discrete mathematics 7th ed by Kenneth Rosen,chapter3:Algorithm
Should not there be a second condition stating i = j1 in While loop's conditional statement,if not then it seems to me while loop will be a infinite loop..
asked
Jun 12, 2019
in
Algorithms
by
souren
(
37
points)

104
views
discretemathematics
algorithms
sorting
0
votes
0
answers
26
#CLRS #Algorithm Doubt about randomized QuickSort.
asked
May 27, 2019
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

520
views
algorithms
sortingalgorithmsquicksort
sorting
asymptoticnotations
+1
vote
1
answer
27
#Algorithms QuickSort Algorithm Doubt regarding pivot and analysis.
asked
May 22, 2019
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

138
views
algorithms
sorting
0
votes
1
answer
28
Made Easy Test Series: AlgorithmSorting
An array $A$ of size n is known to be sorted except for the first $k$ elements and the last $k$ elements, where $k$ is a constant. Which of the following algorithms will be the best choice for sorting the array $A?$ $a)$ ... sorts part by part using pivot. So, why not will it be answer?? How do we know it is asking for almost sorted array??
asked
May 12, 2019
in
Algorithms
by
srestha
Veteran
(
118k
points)

185
views
algorithms
madeeasytestseries
sorting
0
votes
0
answers
29
Mimimum number of comparison to sort 13 elements/numbers for any comparison based sorting algorithm?
asked
May 4, 2019
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

122
views
algorithms
sorting
0
votes
2
answers
30
#Algorithms Quicksort VS Mergesort? Which is a faster sorting algorithm
I did Google and found out that Quicksort is better then Mergesort, but my question is which is faster among both?
asked
Apr 25, 2019
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

119
views
algorithms
sorting
Page:
1
2
3
4
5
6
...
11
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged sorting
Recent Blog Comments
they were in hurry while setting the papers they...
@Swaraj Right.. In Little Endian  Big endian...
Q42 C option is correct for C set as it is an...
@ smsubham The SQL query question No...
Are SQL query and that case 1, case 2 answer in...
50,737
questions
57,271
answers
198,141
comments
104,781
users