Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
October 6th, 2012, 01:18 AM
 Corpsecreate
Contributing User

Join Date: Oct 2010
Posts: 38
Time spent in forums: 1 Day 1 h 50 m 12 sec
Reputation Power: 3
Sorting array of integers or doubles

Hi all,

I am well aware of the multiple sorting algorithms (Shell Sort, Merge Sort, Insertion Sort... and so on) and it got me thinking of my own sorting algorithm. Basically I am asking if this idea for sorting has been attempted before, and if its possible/feesible. Theres a very high chance that this has been tried before and is likely to be a bad idea but I thought I would give some people smarter than me something to work on.

The idea is pretty simple. Lets say you have an array of 100 unique integers valued from 1-100. The integers are randomly ordered. The sorting algorithm would work in 2 stages.

In stage 1, the algorithm will just traverse through the array and find the largest value. In this case that value would be 100.

In stage 2, the algorithm would then traverse the array and rank the current element relative to the largest value as a percentage. For example, the number 28 would be ranked as 28/100 = 0.28. This rank would be used to identify the slot in the array the value should be moved to by multiplying the rank by the array length.

position = (int)(value/largest*arrayLength)-1

0.28*100 = 28
So the 28th element should be the value 28. This would be repeated for until all elements have been properly placed. Heres an example output using 10 values.

{4, 10, 3, 6, 7, 1, 9, 2, 8, 5}
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0} // empty array, we insert 10 first since we know it is the largest element and should occupy the last position.
{0, 0, 0, 0, 0, 0, 0, 0, 0, 10} Inserting 4
{0, 0, 0, 4, 0, 0, 0, 0, 0, 10} Inserting 3
{0, 0, 3, 4, 0, 0, 0, 0, 0, 10} Inserting 6
{0, 0, 3, 4, 0, 6, 0, 0, 0, 10} Inserting 7
{0, 0, 3, 4, 0, 6, 7, 0, 0, 10} Inserting 1
{1, 0, 3, 4, 0, 6, 7, 0, 0, 10} Inserting 9
{1, 0, 3, 4, 0, 6, 7, 0, 9, 10} Inserting 2
{1, 2, 3, 4, 0, 6, 7, 0, 9, 10} Inserting 8
{1, 2, 3, 4, 0, 6, 7, 8, 9, 10} Inserting 5
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Done!!!

Now the problems with this algorithm are numerous. In the above examples, the only reason no problem is caused is because no value's rank matches another. If you had this array:

{1, 3, 99}

The value 1 would be assigned position (1/99*3)-1 = -1. An out of bounds error. Likewise if you had:

{40, 42, 99}

The value 40 would be assigned position (40/99*3)-1 = 0 and the value 42 would be assigned position (42/99*3)-1 = 0. They would both be given the same position!

So maybe its possible, by using standard deviations, averages, variance or some other mathematical calculation, to uniquely allocate each element into its correct position. In the case that two different values are given the same position, then a swap-type implementation could be used to move them into the correct order.

This is outside of my ability but I thought I would share my idea with people more capable than myself. Is this algorithm at all possible? Is it completely stupid and has no chance of being at all useful? Let me know what you think.

Edit: I managed to easily avoid the out of bounds problem by scaling the input value to the range 1 to N-2. The first pass also now find the smallest value as well as the largest value (it might as well, and its needed for the scaling).

 Viewing: Dev Shed Forums > Programming Languages > Java Help > Sorting array of integers or doubles