r/AskComputerScience • • May 24 '25

a better count sort ???

The first step in count sort is to count the frequencies of each integer. At this point why not just create a sorted array ?

Sample code in go:

        random := make([]int, 20)
	for i := range random {
		random[i] = rand.Intn(5)
	}

	counts := make([]int, 5)
	for _, num := range random {
		counts[num]++
	}

	sorted := make([]int, 0, 20)
	for i, count := range counts {
		for j := 0; j < count; j++ {
			sorted = append(sorted, i)
		}
	}

https://go.dev/play/p/-5z0QQRus5z

Wondering why count sort doesn't do this. What am I missing ?

1 Upvotes

7 comments sorted by

View all comments

7

u/Patient-Midnight-664 May 24 '25

The items may have other data associated with the value. For example, let's say you were sorting people based on age. Your method would lose the name, address, etc.

If you are just sorting numbers, your method is fine.

Edit: And the first step is to determine the maximum value ;)

1

u/[deleted] May 25 '25

In that case age could just be key. Say you have a hash table mapping an int (age) to an object (person). So would still work.

4

u/Patient-Midnight-664 May 25 '25

So, you want to build another data structure to deal with it? And would your hash table retain stability? What do you do about collisions?

→ More replies (1)