Sorting algorithm?

Could anyone help me with an algorithm to sort an array of numbers? I am currently using recursive quicksort, however I get a 'Watchdog Tripped Error - Code Executed Too Long' error in the simulator with only around 100 elements in the array. I assume this is because of the recursion running too deep. The code is below for anyone that is interested.

So I am looking for a sorting algorithm to sort through possibly 300 elements of an array.

// numeric quick sort

	function qSort(arr, low, high)

	{

		if (arr == null || arr.size() == 0)

		{

			return;

		}

 

		if (low >= high)

		{

			return;

		}

 

		// pick the pivot

		var middle = low + (high - low) / 2;

		var pivot = arr[middle];

 

		// make left < pivot and right > pivot

		var i = low;

		var j = high;

		while (i <= j)

		{

			while (arr.value() < pivot.value())

			{

				i++;

			}

 

			while(arr[j].value() > pivot.value())

			{

				j--;

			}

 

			if (i <= j)

			{

				var temp = arr;

				arr= arr[j];

				arr[j] = temp;

				i++;

				j--;

			}

		}

 

		// recursively sort two sub parts

		if (low < j)

		{

			qSort(arr, low, j);

		}

 

		if (high > i)

		{

			qSort(arr, i, high);

		}

	}

[/CODE]

Alan.raceQs over 8 years ago

Did you ever get an answer to this?
I'm looking to sort an array of objects (Dictionaries) by one of the dictionary elements.
PS your qSort works really well for a small array of 16 items.
But it sorts low to high 2,1,5,4,3 sorts to 1,2,3,4,5 ... I need it to sort high to low ->5,4,3,2,1. Can you supply the elegant solution please. I have fudged it by
multiplying by -1:

while (-1* arr.value() <-1* pivot.value())
  {
   i++;
  }
 
  while(-1* arr[j].value() > -1* pivot.value())
[/code]

travis.vitek over 8 years ago

I wrote this code a long time ago, and didn't end up using it. There is an implementation of an optimized bubble_sort that appears to be working as well as some other useful functions for dealing with sorted collections.

// Shuffles the range of elements in array
    function random_shuffle_range(array, first, last) {

        // randomly order them
        var n = last - first;
        for (var i = n - 1; 0 < i; --i) {
            var j = Math.rand() % (i + 1);

            var tmp = array[first + i];
            array[first + i] = array[first + j];
            array[first + j] = tmp;
        }
    }

    // Shuffles the entire array
    function random_shuffle(array) {
        random_shuffle_range(array, 0, array.size());
    }

    function bubble_sort_aux(array, lo, hi, cmp) {
        var n = hi;

        do {
            var newn = 0;

            for (var i = lo; i != n; ++i) {

                if (cmp.invoke(array, array[i-1])) {
                    var tmp = array[i-1];
                    array[i-1] = array;
                    array= tmp;

                    newn = i;
                }
            }

            n = newn;

        } while (n != 0);
    }

    function bubble_sort(array, cmp) {
        bubble_sort_aux(array, 0, array.size(), cmp);
    }
[/code]

To use the the sort function, you'd call it like this...

// at global scope
function less_than(a, b) {
    return a < b;
}

function greater_than(a, b) {
    return a > b;
}

// somewhere in your code...
bubble_sort(array, new Lang.Method($, :less_than));

// or, if less_than is a member function of this class
bubble_sort(array, self.method(:less_than));


If you needed to sort by a value in maps in the collection, you could do that two different ways. You could just define the comparison function to access the fields directly...

function key_less_than(a, b) {
    return a["key"] < b["key"];
}


or you could define a class that encapsulates the key you want to use for the comparisons...

class key_compare {
    hidden var _M_key;

    function initialize(key) {
        _M_key = key;
    }

    function less_than(a, b) {
        return a[_M_key] < b[_M_key];
    }

    function greater_than(a, b) {
        return a[_M_key] > b[_M_key];
    }
}

var cmp = new key_compare("key");
bubble_sort(array, cmp.method(:less_than));


I could probably brew up a quick_sort or shell_sort if necessary, but testing showed that this bubble_sort is probably good enough for most needs. If I remember right, I did have problems with stack space with my implementation of quick_sort, but I can't seem to find the code right now.

Travis

jim_m_58 over 8 years ago

If the data is gathered at runtime, would be be possible to build it sorted? If there are 299 things, and you're adding the 300th, figure out where the new one goes and move what's needed to make a space for it, and the result is you never have to do a full sort.

And instead of walking up to 299 values looking for the spot, you could check against the 150th one, and see which half needs to be checked, then check the middle of that half, and so on, until you get just a few to walk (maybe never more than ~15 total compares to find the right spot for 300). After that it's just a loop to make space, with no new compares needed. A binary search to find the the spot, in other words.