Javascript Array: Algorithm sorting and picking

In this case I have an array of 4 integers between 0 and 256 that need to be sorted ascending. eg:

[0, 12, 211, 4] when I sort the I get (of course): [0, 4, 12, 211]

I simply get the integer value by requesting Array[0] (first indexed)

now, my problem is; many times, there are equal values in the array. like:

[0, 0, 0, 12] // already sorted

In these cases I need to pick a random index from the topmost equal values (0,0,0), other possiblities are (after sorting):

[211, 211, 211, 255] // results in 0 OR 1 OR 2
[13, 13, 125, 256] // results in 0 OR 1
[4, 211, 211, 255] // results in 0 
[0, 1, 1, 4] // results in 0;

so I need to pick a random index from the topmost values in a ascending sorted array. Is that to be d开发者_C百科one while sorting , or in a simpler way than a lot of if-elses?

Sorting

If speed is important (which you seem to suggest it is) then have you looked at sorting networks? I have found these to be incredibly fast when sorting small sets of numbers.

To sort with a sorting network:

Network for N=4, using Bose-Nelson Algorithm.

CreationDate: Tue Feb 15 04:44:06 2011 Creator: perl module Algorithm::Networksort version 1.05. Network for N=4, using Bose-Nelson Algorithm. Input line. Comparator size 1. Comparator size 2. There are 5 comparators in this network, grouped into 3 parallel operations.

[[0,1],[2,3]] [[0,2],[1,3]] [[1,2]]

This is graphed in 4 columns.

Pseudo:

if [0] > [1] {  swap(0, 1)  }
if [2] > [3] {  swap(2, 3)  }
if [0] > [2] {  swap(0, 2)  }
if [1] > [3] {  swap(1, 3)  }
if [1] > [2] {  swap(1, 2)  }

Finding Set of Indexes

Anyway this problem can be solved with a sort of divide and conquer (pseudo):

// First index is unique
if [0] != [1]
    return 0
// First 2 are equal
else if [1] != [2]
    return 0 or 1
// First 3 are equal
else if [2] != [3]
    return 0 or 1 or 2
// All are equal
else
    return 0 or 1 or 2 or 3
end

Or you can do this with a loop:

for i = 0 to 2

    if [i] != [i+1]
       return random(0 to i)
       break loop
    end if

loop

You should go for the algorithm which makes most semantic sense and is easiest to maintain probably over anything else, unless speed is crucial.

This will return a random index of equal values:

var myNums = new Array(211, 211, 211,211,214, 255);
myNums = myNums.sort();
if(myNums.length == 0)
    alert("Array is zero sized");
else
{
   var smallest = myNums[0];
   var last=0;
   var start = 0;
   while(smallest == myNums[last])
       last++;
   last = last-1;
   var randIndex = Math.floor(Math.random() *(last - start + 1)+ start);
   alert(randIndex);
}

See it work here: http://jsfiddle.net/rAbh3/

Making a for loop from right to left to select the elements will do the trick and if is done after the sorting process it will only add N to the complexity

Changing from nlogn to nlogn + n is not that much cpu expensive.

Edit: The top most equal values in your example, shouldn't it be:

[211, 211, 211, 255] // results in 0 OR 1 OR 2
[13, 13, 125, 256] // results in 0 OR 1
[4, 211, 211, 255] // results in 1 or 2 
[0, 1, 1, 4] // results in 1 or 2;

??