Counting Sort

 Counting Sort

Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array.

Advantages of Counting Sort:

• Counting sort generally performs faster than all comparison-based sorting algorithms, such as merge sort and quicksort, if the range of input is of the order of the number of input.
• Counting sort is easy to code.

Disadvantages of Counting Sort:

• Counting sort doesn’t work on decimal values.
• Counting sort is inefficient if the range of values to be sorted is very large.

Complexity:

• Best :       O(n+k)
• Worst: O(n+k)
• Average: O(n+k)
• Space : O(max)
• Stability Yes

CODE:

1. #include <stdio.h>
2. void countingsort(int a[], int k, int n);
3. void main()
4. {
5. int n, i, k=0, a[15];
6. printf("How many element in array:");
7. scanf("%d", &n);
8. printf("\n Enter the element for array:");
9. for(i=1; i<=n; i++)
10. {
11. scanf("%d", &a[i]);
12. if(a[i]>k)
13. {
14. k = a[i];
15. }
16. }
17. countingsort(a,k,n);
18. }
19. void countingsort(int a[], int k, int n)
20. {
21. int i, j;
22. int b[15], c[100];
23. for(i=0; i<=k; i++)
24. c[i] = 0;
26. for(j=1; j<=n; j++)
27. c[a[j]] = c[a[j]] + 1;
29. for(i=1; i<=k; i++)
30. c[i] = c[i] + c[i-1];
32. for(j=n; j>=1; j--)
33. {
34. b[c[a[j]]] = a[j];
35. c[a[j]] = c[a[j]]-1;
36. }
37. printf("\nThe Sorted array is:");
38. for(i=1; i<=n; i++)
39. {
40. printf("\t");
41. printf("%d",b[i]);
42. }
43. }

👉Execute👈

//Output

/*

How many element in array:5

 Enter the element for array:7

1 

5

6

8

The Sorted array is: 1 5 6 7 8

*/

  

EXPLAINATION:

- The code starts by declaring variables for the size of the array, n, and k. Then it declares an integer variable called c[100] to hold 100 integers.

- It also declares two arrays: b[15] to hold 15 integers and c[100] to hold 100 integers.

- The first part of the program is where it sets up all these variables so they are ready for use later on in the program.

- Next, it prints out "How many element in array:" followed by a prompt for input from which you enter how many elements there are in your array (n).

- After this line is printed out, it prints out "Enter the element for array:" followed by another prompt asking you what index number you want to start counting at (i).

- This will be used later when we sort our list because we need to know what index number corresponds with each value that we want to put into our sorted list.

- After this line is printed out, scanf() reads whatever was entered as i into a[] and assigns that value back into i before continuing on with its looping statements inside main().

- Inside main(), there's one looping

- The code attempts to sort an array of integers.

- The code begins by declaring the variables n, k, a[], b[], c[].

- It then declares the variable i and j.

- The next line in the code declares a for loop that iterates through all of the elements in the array.

- In this loop, it increments c[a] by 1 for each iteration until it reaches k. After reaching k, it will then increment c[i] by 1 and continue to do so until it reaches n-1.

- This process continues until b has been initialized with all values from 0 to n-1 inclusive.

- The next section of code initializes b with all values from 0 to n-1 inclusive and                 

 //ThE ProFessoR