game-editor.com

Hello!

While working with the Sabre engine, I had to use a sorting algorithm and I ended up
searching information about different sorting algorithms.

I found this one called "Shaker sort", (also known as "Cocktail sort") and
with the help of this link: http://www.dreamincode.net/forums/topic ... aker-sort/ wrote
a GE version of it.

It's pretty simple and it works well, so I decided to share it with you.

Here's how Wikipedia animates the sorting process:

So, simplified, what the function does, is that it sweeps back and forth through the array,
swapping adjacent elements if they are in wrong order (bigger one before smaller one) until the array has been sorted.

Download example ged:


More info about Shaker sort:
http://en.wikipedia.org/wiki/Cocktail_sort

The function code with some commenting to make it more understandable:

Code: Select all

void shakerSort(int * input_array, int array_count)
{
    int i;
    int swap;
    int temp;
 
    do
    {
        swap = 0; //no values have been swapped
 
        for (i = array_count - 1; i > 0; i --) //go through the array starting from the end
        {
            if (testArray[i - 1] > testArray[i]) //if the value of the smaller index element is
            {                                    //higher than the value of the current element
 
                temp = input_array[i - 1];       //swap the values
                testArray[i - 1] = testArray[i];
                testArray[i] = temp;
                swap = 1; //some values have been swapped
            }
        }
 
        for (i = 1; i < array_count; i ++) //go through the array starting from the beginning
        {
            if (testArray[i - 1] > testArray[i]) //if the value of the smaller index element is
            {                                    //higher than the value of the current element
 
                temp = testArray[i - 1];         //swap the values
                testArray[i - 1] = testArray[i];
                testArray[i] = temp;
                swap = 1; //some values have been swapped
            }
        }
    }
    while(swap); //continue the do loop when swap is equal to 1 (-> some values have been swapped)
 
}

insertion sorts are faster. you could even do merge sort if game editor allowed recursion

Interresting, thanks icl. I was confusing this with the regular bubblesort. I'll have to check out Fojam's Insertion sort too (thanks Fojam).

If anyone has examples of other sorting methods, mght be a good idea to list them here. All in one place?

Thought I'd add some links for peeps. The spatial sort looks interesting for geometrical stuff. The animations one (in the first link) is a good one as quick visual introduction to the various main types of sorts. Some unsual ones in the open directory links (some are too complicated for me thou).

Sorting Algorithm Animations
http://www.sorting-algorithms.com/

wikipedia article (Sorting algorithm)
http://en.wikipedia.org/wiki/Sorting_algorithm

Data Structure Algorithms
http://www.w3professors.com/Pages/Cours ... ml#ArrayOD

Some of these are advanced (more maths intensive)

OPEN DIRECTORY PROJECT (Sorting and Searching)
http://www.dmoz.org/Computers/Algorithm ... Searching/

Spatial_sorting
http://www.cgal.org/Manual/latest/doc_h ... _main.html

Swarm-Based Spatial Sorting (free .pdf)
http://arxiv.org/abs/0805.1727

Fojam wrote:insertion sorts are faster. you could even do merge sort if game editor allowed recursion

I though GE allowed for recursion? I remember skydereign showed me a filling function that would use recursion to fill an array.

You should make quick sort! The fastest sorting, also used by the STL library

Game A Gogo wrote:I though GE allowed for recursion?

Indeed. The idea that someone can say it doesn't support recursion is weird. It uses C, it's not like makslane would deliberately remove recursion. So, gE definitely can recurse as I've done it quite a lot.

skydereign wrote:

Game A Gogo wrote:I though GE allowed for recursion?

Indeed. The idea that someone can say it doesn't support recursion is weird. It uses C, it's not like makslane would deliberately remove recursion. So, gE definitely can recurse as I've done it quite a lot.

Wow, recursion is hugely useful, never thought to use it in gE. Thanks for bringing this up...