Recent questions tagged countingsort - GATE Overflow

First time here? Checkout the FAQ!

x

0 votes

0 answers

1

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 in Algorithms by akash.dinkar12 Boss (41.3k points) | 14 views

0 votes

0 answers

2

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 in Algorithms by akash.dinkar12 Boss (41.3k points) | 5 views

0 votes

0 answers

3

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

asked Jun 28 in Algorithms by akash.dinkar12 Boss (41.3k points) | 7 views

0 votes

0 answers

4

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 $

asked Jun 28 in Algorithms by akash.dinkar12 Boss (41.3k points) | 10 views

To see more, click for the full list of questions or popular tags.

Recent questions tagged countingsort

49,845 questions

54,784 answers

189,430 comments

80,447 users