Shaker sort algorithm

You must understand the Game Editor concepts, before post here.

Shaker sort algorithm

Postby lcl » Thu Mar 28, 2013 2:33 pm

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:
Image
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:
shakerSort.zip
(424.82 KiB) Downloaded 294 times


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)
 
}

shakerSort.png
SABRE (semi-3D engine) official development topic: viewtopic.php?f=6&t=12644
A game project that utilizes SABRE: viewtopic.php?f=4&t=13297
User avatar
lcl
 
Posts: 2238
Joined: Thu Mar 25, 2010 5:55 pm
Location: Finland
Score: 265 Give a positive score

Re: Shaker sort algorithm

Postby Fojam » Fri Mar 29, 2013 11:31 am

insertion sorts are faster. you could even do merge sort if game editor allowed recursion
CLICK TO GIVE ME POINTS

My Latest Projects:
Super Smash Bros: viewtopic.php?f=6&t=12307 PLEASE help by making sprites!
User avatar
Fojam
 
Posts: 513
Joined: Thu Mar 19, 2009 10:02 pm
Location: under your bed!!!
Score: 69 Give a positive score

Re: Shaker sort algorithm

Postby GEuser » Sat Mar 30, 2013 10:41 pm

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?
GEuser
 
Posts: 204
Joined: Thu Jan 05, 2012 3:08 pm
Score: 19 Give a positive score

Re: Shaker sort algorithm

Postby GEuser » Sun Mar 31, 2013 12:37 am

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
GEuser
 
Posts: 204
Joined: Thu Jan 05, 2012 3:08 pm
Score: 19 Give a positive score

Re: Shaker sort algorithm

Postby Game A Gogo » Thu Apr 18, 2013 1:03 pm

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
Programming games is an art,
    Respect it.
User avatar
Game A Gogo
 
Posts: 3465
Joined: Wed Jun 29, 2005 10:49 pm
Location: French Canada *laughs*
Score: 181 Give a positive score

Re: Shaker sort algorithm

Postby skydereign » Thu Apr 18, 2013 6:05 pm

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.
User avatar
skydereign
 
Posts: 3513
Joined: Mon Jul 28, 2008 8:29 am
Score: 588 Give a positive score

Re: Shaker sort algorithm

Postby GEuser » Fri Apr 19, 2013 4:21 pm

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...
GEuser
 
Posts: 204
Joined: Thu Jan 05, 2012 3:08 pm
Score: 19 Give a positive score


Return to Advanced Topics

Who is online

Users browsing this forum: No registered users and 0 guests