This wiki is out of date, use the continuation of this wiki instead

Quicksort

From FenixWiki

(Difference between revisions)
Jump to: navigation, search
Revision as of 00:11, 12 July 2007 (edit)
Sandman (Talk | contribs)
(→Definition)
← Previous diff		 Current revision (23:49, 27 July 2007) (edit) (undo)
Sandman (Talk | contribs)
m
 
(4 intermediate revisions not shown.)
Line 3: Line 3:
==Definition== ==Definition==
-'''STRING''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )+'''INT''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' elementsize> , <'''INT''' elements> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' datatype> )
-Sorts an array by the Quicksort ordering algorithm.+Sorts an [[array]] by the Quicksort ordering algorithm.
-This function is very handy for user defined types for elements in which a sort-variable is present.+This function is very handy for user defined [[type]]s for elements in which a sort-[[variable]] is present. For simple arrays or arrays in which the first variable is the sort-variable, [[sort]]() can be used. For arrays in which the sort-variable is a String, [[ksort]]() can be used.
== Parameters == == Parameters ==
Line 13: Line 13:
| '''VOID POINTER''' array || - [[Pointer]] to the first element of the [[array]] to be sorted. | '''VOID POINTER''' array || - [[Pointer]] to the first element of the [[array]] to be sorted.
|- |-
-| '''INT''' size || - The [[size]] of an element in the array in bytes.+| '''INT''' elementsize || - The size of an element in the array in bytes.
|- |-
-| '''INT''' datacount || - The number of elements in the array.+| '''INT''' elements || - The number of elements in the array.
|- |-
-| '''INT''' dataoffset || - The number of [[byte]]s the sort-variable in each element is relative to the start of that element.+| '''INT''' dataoffset || - The number of [[byte]]s the sort-[[variable]] in each element is relative to the start of that element.
|- |-
| '''BYTE''' datasize || - The size of the sort-variable in bytes. | '''BYTE''' datasize || - The size of the sort-variable in bytes.
|- |-
-| '''BYTE''' type || - The type of the sort-variable. (0:[[int]]eger, 1:[[float]])+| '''BYTE''' datatype || - The datatype of the sort-variable. (0:[[int]]eger, 1:[[float]])
|} |}
Line 30: Line 30:
<pre> <pre>
Program sorting; Program sorting;
 +
 +Type _player
 + String name;
 + int score;
 +End
 +
Const Const
- myarray_length = 10;+ maxplayers = 5;
Global Global
- int myarray[myarray_length-1];+ _player player[maxplayers-1];
Begin Begin
- // Insert random numbers+ // Insert some values
- for(x=0; x<myarray_length; x++)+ player[0].name = "That one bad looking dude";
- myarray[x] = rand(0,100);+ player[1].name = "Ah pretty lame guy";
 + player[2].name = "Some cool dude";
 + player[3].name = "OMG ZOMG guy";
 + player[4].name = "This person is ok";
 + 
 + player[0].score = 70;
 + player[1].score = 30;
 + player[2].score = 80;
 + player[3].score = 90;
 + player[4].score = 50;
 + 
 + 
 + // Show array
 + say("-------------------- unsorted");
 + for(x=0; x<maxplayers; x++)
 + say(player[x].name + " - " + player[x].score);
end end
 +
 +/* Sort by name ( quicksort() can't be used to sort Strings,
 + as a String in Fenix is a pointer to the actual String,
 + so it would sort the pointer addresses */
 +
 + // sort()
 + sort(player); // sorts by name because name is the first variable in each element
 +
 + // Show array
 + say("-------------------- name - sort()");
 + for(x=0; x<maxplayers; x++)
 + say(player[x].name + " - " + player[x].score);
 + end
 +
 + // ksort()
 + ksort(player,player[0].name,maxplayers);
 +
 + // Show array
 + say("-------------------- name - ksort()");
 + for(x=0; x<maxplayers; x++)
 + say(player[x].name + " - " + player[x].score);
 + end
 +
 +/* Sort by score (sort() cannot be used here, because score is not the first variable) */
 +
 + // ksort()
 + ksort(player,player[0].score,maxplayers);
// Show array // Show array
- say("--------------------");+ say("-------------------- score - ksort()");
- for(x=0; x<myarray_length; x++)+ for(x=0; x<maxplayers; x++)
- say(x + " - " + myarray[x]);+ say(player[x].name + " - " + player[x].score);
end end
- // Sort+ // quicksort()
- quicksort(&myarray[0],sizeof(int),myarray_length,0,sizeof(int),0);+ quicksort(&player[0],sizeof(_player),maxplayers,sizeof(String),sizeof(int),0);
// Show array // Show array
- say("--------------------");+ say("-------------------- score - quicksort()");
- for(x=0; x<myarray_length; x++)+ for(x=0; x<maxplayers; x++)
- say(x + " - " + myarray[x]);+ say(player[x].name + " - " + player[x].score);
end end
Line 63: Line 111:
End End
</pre> </pre>
-Used in example: [[say]](), [[array]], [[pointer]]+Used in example: [[say]](), [[sort]](), [[ksort]](), [[quicksort]](), [[type]], [[array]], [[pointer]]

Current revision


Contents

[edit] Definition

INT quicksort ( <VOID POINTER array> , <INT elementsize> , <INT elements> , <INT dataoffset> , <BYTE datasize> , <BYTE datatype> )

Sorts an array by the Quicksort ordering algorithm.

This function is very handy for user defined types for elements in which a sort-variable is present. For simple arrays or arrays in which the first variable is the sort-variable, sort() can be used. For arrays in which the sort-variable is a String, ksort() can be used.

[edit] Parameters

VOID POINTER array - Pointer to the first element of the array to be sorted.
INT elementsize - The size of an element in the array in bytes.
INT elements - The number of elements in the array.
INT dataoffset - The number of bytes the sort-variable in each element is relative to the start of that element.
BYTE datasize - The size of the sort-variable in bytes.
BYTE datatype - The datatype of the sort-variable. (0:integer, 1:float)

[edit] Returns

INT: true

[edit] Example 

Program sorting;

Type _player
    String name;
    int score;
End

Const
    maxplayers = 5;
Global
    _player player[maxplayers-1];
Begin

    // Insert some values
    player[0].name = "That one bad looking dude";
    player[1].name = "Ah pretty lame guy";
    player[2].name = "Some cool dude";
    player[3].name = "OMG ZOMG guy";
    player[4].name = "This person is ok";

    player[0].score = 70;
    player[1].score = 30;
    player[2].score = 80;
    player[3].score = 90;
    player[4].score = 50;


    // Show array
    say("-------------------- unsorted");
    for(x=0; x<maxplayers; x++)
        say(player[x].name + " - " + player[x].score);
    end

/* Sort by name ( quicksort() can't be used to sort Strings,
   as a String in Fenix is a pointer to the actual String,
   so it would sort the pointer addresses */

    // sort()
    sort(player); // sorts by name because name is the first variable in each element

    // Show array
    say("-------------------- name - sort()");
    for(x=0; x<maxplayers; x++)
        say(player[x].name + " - " + player[x].score);
    end

    // ksort()
    ksort(player,player[0].name,maxplayers);

    // Show array
    say("-------------------- name - ksort()");
    for(x=0; x<maxplayers; x++)
        say(player[x].name + " - " + player[x].score);
    end

/* Sort by score (sort() cannot be used here, because score is not the first variable) */

    // ksort()
    ksort(player,player[0].score,maxplayers);

    // Show array
    say("-------------------- score - ksort()");
    for(x=0; x<maxplayers; x++)
        say(player[x].name + " - " + player[x].score);
    end

    // quicksort()
    quicksort(&player[0],sizeof(_player),maxplayers,sizeof(String),sizeof(int),0);

    // Show array
    say("-------------------- score - quicksort()");
    for(x=0; x<maxplayers; x++)
        say(player[x].name + " - " + player[x].score);
    end

    // Wait until ESC is pressed
    Repeat
         frame;
    Until(key(_esc))

End

Used in example: say(), sort(), ksort(), quicksort(), type, array, pointer

Retrieved from "http://fenixwiki.booleansoup.com/index.php/Quicksort"
Personal tools