+ 1

# help me understand this

#include <stdio.h> int main(void) { // your code goes here int t; int n,a[1000001]={0}; scanf("%d",&t); while(t--) { scanf("%d",&n); a[n]++; } for (int i=0;i<1000001;i++) { while(a[i]>0) { printf("%d\n",i); a[i]--; } } return 0; }

3 odpowiedzi

+ 3

That implements a counting sort algorithm( https://en.wikipedia.org/wiki/Counting_sort ).
1. All array elements are initialized to 0. In other words, each and every element in a is initialized to 0.
2. A number t is read in. This is the number of remaining numbers to read in and sort.
3. t numbers are read in and added to the counts in array a. Each number must be between 0 and 1 million to fit the boundaries of array a.
4. The original numbers are printed in sorted order.

0

Josh Greig yeah , I'm just trying to understand how the sorting works actually, how is this comparing of elements works?

0

Rajesh wrote, "Josh Greig yeah , I'm just trying to understand how the sorting works actually, how is this comparing of elements works?"
Response:
Counting sort doesn't rely on comparisons. It isn't a comparison-based sort. Randomly accessing each array element at a given index is what happens instead of comparing elements.
Check this video for more explanation of how counting sort works:
https://www.youtube.com/watch?v=OKd534EWcdk
Bucket sort works in a similar way: https://en.wikipedia.org/wiki/Bucket_sort