Member Avatar for Member #593255

Hey guys! I need I quick help
I heard about a sorting algorithm that I want to use but I can't find any info about it..so if any of you know the name of this sort or a place where I can read about it, it would be great:icon_mrgreen:
what the algorithm does is-
sorts n items using an array by the size of the biggest key
the items go in to the array acourding to it's key..
let's say the keys are - 1,3,6,9,12
the array would look like this-
_|1|_|3|_|_|6|_|_|9|_|_|12|
and then we put it all in an array by the size of number of items like that-
1|3|6|9|12|
and it's sorted :cool:
it also can just increase the counters in the array like that
0|1|0|1|0|0|1|0|0|1|0|0|1|
really need the info today!! any help would be highly appreciated!!!

Edited by Member #593255 because: n/a
  • 5 Contributors
  • 4 Replies
  • 253 Views
  • 2 Weeks Discussion Span
  • Latest Post Latest Post by SasseMan

Dani AI

Generated

Short answer: the technique described sits in the counting/pigeonhole family of integer-key sorts. ’s “pigeonhole” and ’s “counting sort” are both on target; ’s bucket/radix comment and ’s note about hashing point to related tradeoffs and alternatives.

Clarification and when to pick which: pigeonhole sort literally places items into an array slot for each key; counting sort stores counts (and optionally uses prefix sums) to produce a stable output. Both run in O(n + k) time and need O(k) extra space, where k is the span (max_key − min_key + 1). Bucket and radix sorts are useful when keys aren’t small integers or when digit-by-digit processing is preferable. Hashing does fast lookup but does not produce a sorted order by itself without a subsequent gather/scan.

Practical fixes for sparse or large-key ranges: avoid allocating an array of size k when k is huge and most slots are empty. Two common approaches work well in practice:

  • Coordinate compression (map distinct keys to 0..m-1, m ≤ n) and then apply counting/pigeonhole logic.
  • Use an associative container (hash map or ordered map) that stores counts or small lists for only seen keys, then iterate keys in sorted order if needed.

Example (coordinate compression + buckets, Python-style pseudocode):

keys = [1, 3, 6, 9, 12]
uniq = sorted(set(keys))                 # O(m log m), m distinct keys
index = {k:i for i,k in enumerate(uniq)}
buckets = [[] for _ in range(len(uniq))]
for item in items:
    buckets[index[item.key]].append(item)
result = [x for b in buckets for x in b]

Notes and cautions: make counting sort stable when relative order of equal keys matters (use prefix-sum reconstruction). If memory is the limiting factor and external storage is available, consider external or streaming sorts.

Recommended Answers

All 4 Replies

Member Avatar for Narue

Looks like a pigeonhole sort to me.

Member Avatar for cam875

I didn't quite understand what you meant in your description but it sounds awfully familiar especially the part about storing the number of occurences if I read right, like a counting sort which is a very quick sort but memory wise can get out of hand due to the array having a pre-known boundary that must be created.

Member Avatar for pogson

The first step is hashing, using the data/keys as array addresses. The second step just reduces the sparseness by gathering the items.

see Hash Function

You calcualate the hash keys numerically from the data and store it according to the keys. To find something, calculate its key and retreive it from the array. It's sorted in that you can always find it again in one step even though things are scattered about...

Normally, the first step is all that is used so that the keys would be self-indexing. In the second step, you lose that advantage. Of course, the ideal hash function must have the right balance between sparseness and collisions. You could possibly get a duplicate key and must keep track of that in a collision table. I think this is what terabyte hard drives are good for... To be useful some other data must be stored along with what was used to calculate the key. Typically these are other columns in a database besides the ones indexed.

Member Avatar for SasseMan

It sound to me like you are describing bucket sort, or radix sort where you use the entire integer to place in buckets instead of parts of it. It is fast but not very space efficient. Runs practically in O(n) (linear) time.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.