Question

CountingSort(A, B, k) for i=1 to k C[i]= 0; for j=1 to n C[A[j]] += 1;...

CountingSort(A, B, k)

for i=1 to k

C[i]= 0;

for j=1 to n

C[A[j]] += 1;

for i=2 to k

C[i] = C[i] + C[i-1];

for j=n downto 1

B[C[A[j]]] = A[j];

C[A[j]] -= 1;

illustrate the operation of COUNTING-SORT on the array A = {6,0,2,0, 1, 3, 5, 6, 1, 3, 2}. Specifically, show the four arrays A, B, C, and C'.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let A[1, . . . , n] be an array of n distinct numbers. If i...
Let A[1, . . . , n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. 1. Which arrays with distinct elements from the set {1, 2, . . . , n} have the smallest and the largest number of inversions and why? State the expressions exactly in terms of n. 2. For any 0 < a < 1/2, construct an array for...
First, understand the Selection-sort algorithm below: Selection-sort(A: Array [1..n] of numbers) 1       for i=n down to...
First, understand the Selection-sort algorithm below: Selection-sort(A: Array [1..n] of numbers) 1       for i=n down to 2 2                position=i 3                for j=1 to (i–1) 4                          if A[j]>A[position] then position=j 5                if position ≠ i then 6                          temp=A[i] 7                          A[i]=A[position] 8                          A[position]=temp (4 points) If input A=[12,5,11,6,10,7,9,8], what will A be after the 3rd iteration of the outermost for loop of the Selection-sort algorithm completes? A=[__, __, __, __, __, __, __, __] (8 points) Modify the algorithm to solve the...
1. Consider three vectors: ( 8 marks) C i j k B i j k A...
1. Consider three vectors: ( 8 marks) C i j k B i j k A i j k 0ˆ 3 ˆ 5 ˆ 2ˆ 7 ˆ 1ˆ 4ˆ 6 ˆ 2 ˆ = + + = + − = + − ! ! ! 1.1 Evaluate D= 2A+B? (2 marks) 1.2 Evaluate 2A•(-­‐B) (2 marks) 1.3 Find the angle between D and 2C using cross product method (4 marks
Suppose an array A stores n integers, each of which is in {0, 1, 2, ...,...
Suppose an array A stores n integers, each of which is in {0, 1, 2, ..., 99}. Which of the following sorting algorithms can sort A in O(n) time in the worst case? Question 16 options: A) merge sort B) counting sort C) quicksort D) None of these options is correct. E) insertion sort
PDA for {a^i b^j i != j} PDA for {a^i b^j c^k, i = j or...
PDA for {a^i b^j i != j} PDA for {a^i b^j c^k, i = j or j = k} PDA for # of a's = # of b's PDA for # b's = twice # of a's
We are given an array A of size n containing n positive and negative integers (the...
We are given an array A of size n containing n positive and negative integers (the array is indexed starting from 0). Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n and Pk=j k=i A[k] is maximized. Input sequence: [2, -4, 1, 9, -6, 7, -3] Output: [1, 9, -6, 7] or i = 2 and j = 5 Input sequence: [1, 2, 3, 4, 5, 6, -3] Output: [1,...
int i,sum=0;   int array[8]={//You decide this};   int *a,*b,*c;   a = array;   b = &array[3];   c =...
int i,sum=0;   int array[8]={//You decide this};   int *a,*b,*c;   a = array;   b = &array[3];   c = &array[5];   c[-1] = 2;   array[1] = b[1]-1;   *(c+1) = (b[-1]=5) + 2;   sum += *(a+2) + *(b+2) + *(c+2);   printf("%d %d %d %d\n", sum, array[b-a], array[c-a], *a-*b); array[8]={ ?? }; what is array[8]?
Hello, I feel like I am super close but I can not figure out why my...
Hello, I feel like I am super close but I can not figure out why my C++ code it not displaying the proper medium. Thank you! Here is an example of the output: Input : a[] = {1, 3, 4, 2, 6, 5, 8, 7} Output : Mean = 4.5 Median = 4.5 Code so far:   #include <iostream> using namespace std; int main() { int a[100]; int n,i,sum=0; float mean, medium; //read array size // read array cout<<"Enter array size:...
Here are two relations: R(A,B): {(0, 1), (2,3), (0, 1), (2,4), (3,4)} S(B, C): {(0, 1),...
Here are two relations: R(A,B): {(0, 1), (2,3), (0, 1), (2,4), (3,4)} S(B, C): {(0, 1), (2, 4), (2, 5), (3, 4), (0, 2), (3, 4)} Compute the following: a) 11'A+B.A2,B2(R); b) 71'B+l,C-l(S); c) TB,A(R); d) TB,c(S); e) J(R); f) J(S); g) /A, SUM(Bj(R); h) IB.AVG(C)(S'); ! i) !A(R); ! j) IA,MAX(C)(R t:><1 S); k) R ~L S; I) R ~H S; m) R ~ S; n) R ~R.B<S.B S. I want to know the solution for j to m
Are the vectors a = i + j − k, b = i − j +...
Are the vectors a = i + j − k, b = i − j + k, and c = i + j + k coplanar?
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT