Looking for a Sorting Algorithm
I came upon a system that had an interesting sorting process. It could take an array of ~1000 numbers and evenly distribute them into 12 "buckets". I use the term "bucket" loosely because the elements sent to each bucket were filled in FIFO order. Then one by one, each bucket is reintroduced into the sort process and it repeats. After the third pass however, the elements in bucket 1 are all in order, followed by the elements in bucket 2 in order, and so on. So now when the buckets are emptied into the sorted array, they are all in order.
Has anyone come upon a sort algorithm like this? It's really not like the bucket sort because in bucket sort the elements are in random order. With this process, the elements in the bucket are in the order they were placed in the bucket (FIFO).
Any help or guidance would be appreciated.
TIA.
Re: Looking for a Sorting Algorithm
Welcome to the forums. :wave:
What development language are we referring to?
Re: Looking for a Sorting Algorithm
Guess what it's called?
Bucket Sort :afrog:
Re: Looking for a Sorting Algorithm
The big difference between bucket sort and this sort is that in bucket sort, the elements are grouped together (1-10, 11-20, etc) and then sorted within the bucket (recursively if needed). With this process, there is no liberty to rearrange the items within the bucket. Therefore, positioning within the bucket is a key priority. I'm guessing the trick to this is not how you group the elements together but rather how you determine which bucket to place the element at what pass. This may be a variant of the bucket sort but I haven't seen anything like it.
An analogy would be filling tubes with ping-pong balls where the tube is just the right diameter for the ball to pass. The balls all have a number 1-1000 and there are 12 tubes that, between them all, can hold all the balls. The balls are in random order, and then sent to the various tubes. Which tube is a function of the algorithm. Because of the diameter of the tube, the balls cannot swap positions once inside the tube. Then the first tube releases, followed by the second tube, etc until all the tubes are empty. This new order of balls is sent through the process again. And then they are released again. After the 3rd pass, however, each tube has all of its balls in order and the tubes are in order so once released all the balls will be in order 1-1000.
As for language, I don't have the source code (that's why I'm asking here) but it looks like it was written in FoxPro. I would probably do the code in VB6 or SQL stored procedure. I'm really more interested in the algorithm than the coding.
I've tried looking at this like a matrix where the front elements of each bucket are always sent to the first bucket and so on, with the back elements sent to the last bucket, so that the final pass is like a transpose of the buckets.
Re: Looking for a Sorting Algorithm
You can find explanations/algorithms for several types of Sorting in this thread, hopefully yours is one of them.