Quicksort - Revision history

Sandman at 23:49, 27 July 2007

2007-07-27T23:49:45Z

←Older revision		Revision as of 23:49, 27 July 2007
Line 3:		Line 3:

	==Definition==		==Definition==
-	'''INT''' 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.
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.
Line 21:		Line 21:
	\| '''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]])
	\|}		\|}

Sandman at 09:55, 17 July 2007

2007-07-17T09:55:39Z

←Older revision		Revision as of 09:55, 17 July 2007
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''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )

	Sorts an [[array]] by the Quicksort ordering algorithm.		Sorts an [[array]] by the Quicksort ordering algorithm.

-	This function is very handy for user defined [[type]]s 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 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]]

Sandman: /* Parameters */

2007-07-12T00:40:57Z

Parameters

←Older revision		Revision as of 00:40, 12 July 2007
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''' size \|\| - The size of an element in the array in bytes.
	\|-		\|-
	\| '''INT''' datacount \|\| - The number of elements in the array.		\| '''INT''' datacount \|\| - The number of elements in the array.
Line 19:		Line 19:
	\| '''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''' type \|\| - The type of the sort-variable. (0:[[int]]eger, 1:[[float]])

Sandman: /* Parameters */

2007-07-12T00:40:40Z

Parameters

←Older revision		Revision as of 00:40, 12 July 2007
Line 19:		Line 19:
	\| '''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''' type \|\| - The type of the sort-variable. (0:[[int]]eger, 1:[[float]])

Sandman at 00:12, 12 July 2007

2007-07-12T00:12:25Z

←Older revision		Revision as of 00:12, 12 July 2007
Line 5:		Line 5:
	'''STRING''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )		'''STRING''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )

-	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.

	== Parameters ==		== Parameters ==
Line 17:		Line 17:
	\| '''INT''' datacount \|\| - The number of elements in the array.		\| '''INT''' datacount \|\| - 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.

Sandman: /* Definition */

2007-07-12T00:11:41Z

Definition

←Older revision		Revision as of 00:11, 12 July 2007
Line 5:		Line 5:
	'''STRING''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )		'''STRING''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )

-	~~Sort~~ 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 types for elements in which a sort-variable is present.

Sandman at 00:06, 12 July 2007

2007-07-12T00:06:20Z

New page

[[Category:functions]]
[[Category:sorting]]

==Definition==
'''STRING''' quicksort ( <'''VOID POINTER''' array> , <'''INT''' size> , <'''INT''' datacount> , <'''INT''' dataoffset> , <'''BYTE''' datasize> , <'''BYTE''' type> )

Sort 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.

== Parameters ==
{|
| '''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''' datacount || - 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.
|-
| '''BYTE''' datasize || - The size of the sort-variable in bytes.
|-
| '''BYTE''' type || - The type of the sort-variable. (0:[[int]]eger, 1:[[float]])
|}

== Returns ==
'''INT''': [[true]]

== Example ==
<pre>
Program sorting;
Const
myarray_length = 10;
Global
int myarray[myarray_length-1];
Begin

// Insert random numbers
for(x=0; x<myarray_length; x++)
myarray[x] = rand(0,100);
end

// Show array
say("--------------------");
for(x=0; x<myarray_length; x++)
say(x + " - " + myarray[x]);
end

// Sort
quicksort(&myarray[0],sizeof(int),myarray_length,0,sizeof(int),0);

// Show array
say("--------------------");
for(x=0; x<myarray_length; x++)
say(x + " - " + myarray[x]);
end

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

End
</pre>
Used in example: [[say]](), [[array]], [[pointer]]