For coutning sort, create an algorithm that doesnt compare elemnts among themsev

Question

For coutning sort, create an algorithm that doesnt compare elemnts among themsevles, that it counts them. You need to sort the array that is below the links in order, with showing the steps, its comparisions, etc.

This algorithm does not compare elements among themselves, it counts them. The algorithm can sort numbers in O(n + k) steps, where k is the maximum element. A few links for you to road: http://en.wikipedia.org/wiki/Counting_sort http://www.geeksforgeeks.org/counting-sort/https://www.es. usfca.edu/visualization/CountingSort.html After the algorithm makes sense. I'd like you to sort numbers (4, 9, 2, 3, 7, 8, 1}. using it. Show the resulting array after each step of the algorithm in a neat; table format just like in earlier cases.

Explanation / Answer

Hi,

Please find below the counting sort algorithm-

This code is for Counting sort, we are given array M[1 . . n] of length n. We need two more arrays, the array N[1 . . n] holds the sorted output and the array c[1 . . k] provides temporary working storage.

COUNTING SORT(M,N,k)

for i = 1 to k
do c[i] = 0
for j = 1 to length[A]
do C[M[j]] = C[M[j]] + 1
//C[i] now contains the number of elements equal to i
for i = 2 to k
do C[i] = C[i] + C[i-1]
//C[i] now contains the number of elements less than or equal to i
for j = length[A] downto 1
do N[C[M[j]]] = M[j]
C[M[j]] = C[M[J]] - 1

C Code to implement Count Sort-

#include <stdio.h>
void count_sort(int array1[], int k, int n)
{
int i, j;
int B[15], C[200];
for (i = 0; i <= k; i++)
C[i] = 0;
for (j =1; j <= n; j++)
C[array1[j]] = C[array1[j]] + 1;
for (i = 1; i <= k; i++)
C[i] = C[i] + C[i-1];
for (j = n; j >= 1; j--)
{
B[C[array1[j]]] = array1[j];
C[array1[j]] = C[array1[j]] - 1;
}
printf(" The Sorted array is : ");
for(i = 1; i <= n; i++)
printf(" %d", B[i]);
}

int main()
{
int n,i,k = 0, array1[15];
printf("Enter the number of elements : ");
scanf("%d", &n);
printf(" Enter the elements to be sorted : ");
for ( i = 1; i <= n; i++)
{
scanf("%d", &array1[i]);
if (array1[i] > k)
{
k = array1[i];
}
}
count_sort(arr, k, n);
return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.