Question

In: Computer Science

1. Sort the given keys using Counting sort algorithm. Also write the algorithm.          4, 1,...

1. Sort the given keys using Counting sort algorithm. Also write the algorithm.

         4, 1, 0, 2, 1, 5, 0, 4                                                                    

No code or programs, please. Manually solve the problem, please. Thanks

Solutions

Expert Solution

Input data (A[]) : 4, 1, 0, 2, 1, 5, 0, 4

Since maximum value is 5, we can take count array of length 5. However to be more general, let us take a count array of lenhth 10.

Step 1: Initialize count array with 0 values.

for(i=0; i<10; i++)

count[i] = 0;

Step 2: Store the count of each element in the count array.

for(i=0; i<n; i++)

count[A[i]]++;

Thus contents of count array = [2, 2, 1, 0, 2, 1, 0, 0, 0, 0]

Step 3: Modify the count array such that each element at each index stores the sum of previous counts.

for (int i = 1; i < 10; ++i)

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

Thus contents of count array = [ 2, 4, 5, 5, 7, 8, 8, 8, 8 8]

Step 4: Output each item from the input sequence in current count index followed by decreasing its count by 1.

for(i=0; i<n; i++){

output[count[A[i]]-1] = A[i];

count[A[i]]--;

Thus output[6] = 4, output[3] = 1, output[1] = 0, output[4] = 2, output[2] = 1, output[7] = 5, output[0] = 0, output[5] = 4

Step 5: Copy output to original array.

for(i=0;i<n;i++)

A[i] = output[i];

Thus content of A = [0, 0, 1, 1, 2, 4, 4 5]


Related Solutions

Sort the given keys using Counting sort algorithm. Also write the algorithm. 5, 2, 3, 1,...
Sort the given keys using Counting sort algorithm. Also write the algorithm. 5, 2, 3, 1, 0, 2, 1, 5, 0  
Write Insertion Sort and Bubble Sort Program for C# also write their algorithm and Explain their...
Write Insertion Sort and Bubble Sort Program for C# also write their algorithm and Explain their working.
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using...
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using Max Heap.
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using...
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using Max Heap.
Please write a python code which implements the counting sort algorithm by creating a CountingSort function...
Please write a python code which implements the counting sort algorithm by creating a CountingSort function with an array input in the form of a list. Then write code to sort 3 randomly generated arrays and the data array listed below, print the output clearly for all four test arrays, develop and comment on the growth function of your code. Comment on the Big O notation of the code. ( Please do not forget to comment on your code to...
(C++)Counting Sort: Write C++ codes for counting sort. The input array is A = {20, 18,...
(C++)Counting Sort: Write C++ codes for counting sort. The input array is A = {20, 18, 5, 7, 16, 10, 9, 3, 12, 14, 0}
Please describe the reason(s) why we choose the counting sort algorithm to sort each digit in...
Please describe the reason(s) why we choose the counting sort algorithm to sort each digit in the Radix Sort?
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
Use counting sort, sort the following numbers: 4, 2, 5, 4, 2, 3, 0, 2, 4,...
Use counting sort, sort the following numbers: 4, 2, 5, 4, 2, 3, 0, 2, 4, 3
1. Write pseudocode for the algorithm using iteration (looping). Envision an algorithm that when given any...
1. Write pseudocode for the algorithm using iteration (looping). Envision an algorithm that when given any positive integer n, it will print out the sum of the squares from 1 to n. For example given 3 the algorithm will print 14 (because 1 + 4 + 9 =14) You can use multiplication denoted as * in your solution and you do not have to define it (For example. 3*3=9) For example if n is 6 it will print: The sum...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT