-
Notifications
You must be signed in to change notification settings - Fork 0
Aashish Sort 1
Aashish Sort 1 is an original sorting algorithm I invented. It is based on the idea behind Bucket Sort and Radix Sort, but it is recursive.
Aashish Sort 1 separates items by their most significant digits, then recursively calls itself, ignoring the first most significant digit, then the second most significant digit, then the third, etc.
Take the following array as an example:
58, 47, 1, 43, 47, 106
First the algorithm would start off by finding the largest number in the array, which is 106. It counts the number of digits, 3, which is in the hundreds place. It then separates all the arrays into ten buckets based on their third digit from the right, the hundreds place. The buckets would be the numbers 0 through 9. I have labelled them 000 through 999 to make it easier to understand.
In this case, there is only one number whose hundreds place is non-zero. Here is the result of this operation:
Original array: 58, 47, 1, 43, 47, 106
Bucket 0xx: 58, 47, 1, 43, 47
Bucket 1xx: 106
Buckets 2xx through 9xx are empty.
Next, the algorithm recursively calls itself on each of the above buckets, but ignores the hundreds place and moves on to the tens place. It first calls itself on Bucket 000. It separates these numbers into nine buckets based on their tens place. Like so:
Original Bucket 0xx: 58, 47, 1, 43, 47
Bucket 00x: 1
Buckets 01x through 030 are empty.
Bucket 04x: 47, 43, 47
Bucket 05x: 58
Buckets 06x through 09x are empty.
Now it recursively calls itself on each of the above buckets. Bucket 000 has only one item, so it ignores it.
It calls itself on Bucket 40, ignoring the ten's place and moving on to the ones place.
Original Bucket 040: 47, 43, 47
Buckets 040 through 049 are empty.
Bucket 043: 43
Buckets 044 through 046 are empty.
Bucket 047: 47, 47
Buckets 048 and 049 are empty.
Not it is done with Bucket 04x, so it returns:
Original Bucket 0xx: 58, 47, 1, 43, 47
Bucket 00x: 1
Buckets 01x through 03x are empty.
Bucket 04x: 43, 47, 47
Bucket 05x: 58
Buckets 06x through 090 are empty.
Now it calls itself on bucket 05x. It only has one item, so it returns.
Finally, it merges everything back into the original array start at the first bucket, going from left to right, then moving on to the next bucket.
1, 43 47, 47, 58.
Time complexity is extremely unstable. If the array is filled with 500 one-digit numbers (numbers between 0 and 9), then it will take roughly 500 cycles. However, if it is an array filled with 50 ten-digit numbers (numbers between 10000000000 and 9999999999) it will also take roughly 500 cycles. In other words, this algorithm is unsuitable for arrays with very large numbers. However, while slower than Counting Sort and Pigeonhole Sort, it uses less space than both of those, so it can be seen as a compromise between those and the traditional algorithms.