Dark Mode

Recent questions tagged sorting

0 votes

1 answer

91

Cormen Edition 3 Exercise 8.3 Question 1 (Page No. 199)
RADIX-SORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digit i illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

1.3k views

0 votes

2 answers

92

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.

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

1.6k views

0 votes

0 answers

93

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?

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

349 views

0 votes

1 answer

94

Cormen Edition 3 Exercise 8.2 Question 2 (Page No. 196)
Prove that COUNTING-SORT is stable.

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

376 views

0 votes

0 answers

95

Cormen Edition 3 Exercise 8.2 Question 1 (Page No. 196)
COUNTING-SORT(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 COUNTING-SORT on the array $A=\langle 6,0,2,0,1,3,4,6,1,3,2 \rangle $

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

353 views

0 votes

0 answers

96

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.)

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

450 views

0 votes

0 answers

97

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$?

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

265 views

0 votes

1 answer

98

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?

akash.dinkar12 asked in Algorithms Jun 28, 2019

by akash.dinkar12

349 views

0 votes

0 answers

99

Cormen Edition 3 Exercise 7.2 Question 4 (Page No. 178)
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order ... -sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

494 views

0 votes

1 answer

100

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.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

1.7k views

0 votes

1 answer

101

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$

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

1.5k views

0 votes

1 answer

102

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 n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.

akash.dinkar12 asked in Algorithms Jun 26, 2019

by akash.dinkar12

505 views

0 votes

0 answers

103

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$.

akash.dinkar12 asked in Algorithms Jun 26, 2019

by akash.dinkar12

602 views

1 vote

1 answer

104

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 $

akash.dinkar12 asked in Algorithms Jun 26, 2019

by akash.dinkar12

1.7k views

0 votes

1 answer

105

Cormen Edition 3 Exercise 2.1 Question 2 (Page No. 22)
Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.

akash.dinkar12 asked in Algorithms Jun 25, 2019

by akash.dinkar12

752 views

0 votes

0 answers

106

Discrete mathematics 7th ed by Kenneth Rosen,chapter3:Algorithm
Should not there be a second condition stating i = j-1 in While loop's conditional statement,if not then it seems to me while loop will be a infinite loop..

souren asked in Algorithms Jun 12, 2019

by souren

977 views

0 votes

0 answers

107

#CLRS #Algorithm Doubt about randomized QuickSort.

iarnav asked in Algorithms May 27, 2019

by iarnav

1.0k views

1 vote

1 answer

108

#Algorithms QuickSort Algorithm Doubt regarding pivot and analysis.

iarnav asked in Algorithms May 22, 2019

by iarnav

906 views

3 votes

3 answers

109

Made Easy Test Series: Algorithm-Sorting
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??

srestha asked in Algorithms May 12, 2019

1.9k views

0 votes

1 answer

110

Made Easy Test Series: Algo- Mathematical Solution
Through an experiment, it is found that selection sort performs $5000$ comparisons when sorting an array of size $k.$ If the size of array is doubled, what will be the number of comparisons? will it be $\left ( 5000 \right )^{2}$ or $\left ( 5000 \right )\times 4$. Someone check plz

srestha asked in Algorithms May 6, 2019

440 views

1 vote

1 answer

111

Mimimum number of comparison to sort 13 elements/numbers for any comparison based sorting algorithm?

iarnav asked in Algorithms May 4, 2019

by iarnav

839 views

1 vote

1 answer

112

Made Easy Test Series:Algorithm
Given a sorted array of distinct integer $A\left [ 1,2,....n \right ]$, the tightest upper bound to check the existence of any index $i$, for which $A[i]=i$ ... index and then checking if $A[i]=i$, but answer given as $O(log n).$Please help me out, which will be correct answer?

srestha asked in Algorithms Apr 28, 2019

762 views

0 votes

2 answers

113

#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?

iarnav asked in Algorithms Apr 25, 2019

by iarnav

988 views

1 vote

4 answers

114

Total number of function calls in Merge sort Algorithm
In Merge sort Algorithm when I took input array of size 2 and I got 4 function calls as including original function call with which I call MS algorithm i.e. MS (1,2) and which in turn calls two recursive function calls to merge ... function calls. So, how can I analyze the total number of function calls when input array size is n? thank you!

iarnav asked in Algorithms Apr 25, 2019

by iarnav

3.9k views

1 vote

5 answers

115

made easy test series:algorithms,sorting
why not merge sort?we don’t swap in merge sort,we just create auxillary arrays and merge them by changing elements in the original array.should we consider that as a swap?

hitesh159 asked in Algorithms Apr 16, 2019

2.1k views

3 votes

4 answers

116

Cormen Edition 3 Exercise 6.1 Question 4 (Page No. 154)
Where in a max-heap might the smallest element reside, assuming that all elements are distinct ?

akash.dinkar12 asked in Algorithms Apr 5, 2019

by akash.dinkar12

2.7k views

1 vote

0 answers

117

Can Merge Sort Time Complexity be O(n^2) in any condition?

aditykansara asked in Algorithms Jan 31, 2019

by aditykansara

1.3k views

4 votes

1 answer

118

ME Mock 4
Consider a new sorting algorithm similar to the BubbleSort algorithm, called RumbleSort. Given an array as input, RumbleSort attempts to sort the array and produces a sorted array as output. Here's the pseudo-code for RumbleSort. With regards to the above RumbleSort ... algorithm will work correctly for a given input is $\mathcal Ο(n^2)$ Which of the above statements is/are true?

balchandar reddy san asked in Algorithms Jan 30, 2019

by balchandar reddy san

1.2k views

3 votes

2 answers

119

MadeEasy WorkBook: Algorithms - Sorting
Consider the following array with 7 elements for insertion sort? 25, 15, 30, 9, 99, 20, 26 In how many passes, the given sequence will be sorted? (a) 4 pass (b) 5 pass (c) 6 pass (d) More than 6 pass Answer is 6 passes. Can anyone explain it step by step.

Jyoti Kumari97 asked in Algorithms Jan 26, 2019

by Jyoti Kumari97

3.0k views

0 votes

0 answers

120

Merge sort
What is the extra memory needed for merge sort: 1] In case of Iterative merge sort.(DS:Array) 2]In case of Recursive merge sort.(DS:Array) 3] In case of Iterative merge sort.(DS:Linked List) 4]In case of Recursive merge sort.(DS:Linked List)

Nandkishor3939 asked in Algorithms Jan 21, 2019

by Nandkishor3939

692 views

Page:

« prev
1
2
3
4
5
6
7
8
9
...
19
next »

Recent questions tagged sorting