Gamestudio Links
Zorro Links
Newest Posts
Newbie Questions
by AndrewAMD. 12/05/23 10:56
Zorro Trader GPT
by TipmyPip. 12/04/23 11:34
Square root rule
by Smallz. 12/02/23 09:15
RTest not found error
by TipmyPip. 12/01/23 21:43
neural function for Python to [Train]
by TipmyPip. 12/01/23 14:47
Xor Memory Problem.
by TipmyPip. 11/28/23 14:23
Training with command line parameters
by TipmyPip. 11/26/23 08:42
Combine USD & BTC Pairs In Asset Loop
by TipmyPip. 11/26/23 08:30
AUM Magazine
Latest Screens
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Tactics of World War I
Who's Online Now
6 registered members (AndrewAMD, alibaba, fairtrader, ozgur, TipmyPip, Quad), 622 guests, and 1 spider.
Key: Admin, Global Mod, Mod
Newest Members
fairtrader, hus, Vurtis, Harry5, KelvinC
19019 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
[algorithm] quicksort #131642
05/24/07 16:39
05/24/07 16:39
Joined: Jul 2001
Posts: 6,904
H
HeelX Offline OP
Senior Expert
HeelX  Offline OP
Senior Expert
H

Joined: Jul 2001
Posts: 6,904
Here is a simple quicksort algorithm which sorts an integer array from lowest to highest (inplace). Useful if you want to study Lite-C syntax and so on.

Here it is:

Code:
//- quicksort --------------------------------------------------------

//prototypes
int partition (int* A, int l, int r);
void quicksort (int* A, int l, int r);

//----------------------------------------------------------------
//call quicksort with l = 0 and r = number of elements - 1
//sorts inplace from lowest to highest!
//----------------------------------------------------------------
void quicksort (int* A, int l, int r)
{
if (l < r)
{
int q = partition(A, l, r);

quicksort(A, l, q);
quicksort(A, q+1, r);
}
}

//------------------------------------------------------------
//determines the pivot element which serves
//for the partioning
//------------------------------------------------------------
int partition (int* A, int l, int r)
{
int x = A[(int)((l+r)/2)];
int i = l-1;
int j = r+1;

while (1) {
do {j--;} while (A[j] > x);
do {i++;} while (A[i] < x);

if (i < j) {
int help;

help = A[j];
A[j] = A[i];
A[i] = help;

} else {
return j;
}
}
}

//- demo -------------------------------------------------------------
void main()
{
int arr [] = {9,6,2,8,1,6,5,4,8};
quicksort(arr, 0, 8);

int i = 0;
while (1) {
if (i < 9) {
error(str_for_num(str_create(""), arr[i]));
i++;
}

wait(1);
}
}



Have fun!

Re: [algorithm] quicksort [Re: HeelX] #131643
05/24/07 18:19
05/24/07 18:19
Joined: Jul 2006
Posts: 783
London, UK
sheefo Offline
User
sheefo  Offline
User

Joined: Jul 2006
Posts: 783
London, UK
I just wrote a bubble sort algorithm and I wanted a quicksort one to compare. Great timing

Thanks. This is very useful.

Re: [algorithm] quicksort [Re: sheefo] #429628
09/15/13 17:13
09/15/13 17:13
Joined: Dec 2010
Posts: 224
NRW, Germany
NeoJones Offline
Member
NeoJones  Offline
Member

Joined: Dec 2010
Posts: 224
NRW, Germany
Yes, I wrote a bubblesort algorithm, too. But its very slow. Now Iam looking for quicksort, but I have a problem. I have a struct for example:


Code:
typedef struct {
	
	char* name; //stadtname
	var value[3]; //menge,einkauf,verkauf

} LOGS;

LOGS logs[62];



Now I will sort the array logs to "einkauf" or "verkauf":

Code:
logs[i].value[1]

or

logs[i].value[2]



I hope you understand me... can someone help me, please?


Regards


Errors are the engine of progress.

Version: A8 Commercial
OS: Win 7 64bit
Models: Cinema 4D
Re: [algorithm] quicksort [Re: NeoJones] #429645
09/16/13 02:08
09/16/13 02:08
Joined: Dec 2010
Posts: 224
NRW, Germany
NeoJones Offline
Member
NeoJones  Offline
Member

Joined: Dec 2010
Posts: 224
NRW, Germany
Ok, If someone have the same problem...

My solution was a second helper array with the same numbers of elements.
At the following code I used the "i" and "j" for my first array to sort it:

Code:
help = A[j];
A[j] = A[i];
A[i] = help;



Thanks anyway HeelX. Its faster than bubble sort! wink


Errors are the engine of progress.

Version: A8 Commercial
OS: Win 7 64bit
Models: Cinema 4D
Re: [algorithm] quicksort [Re: NeoJones] #429712
09/17/13 10:10
09/17/13 10:10
Joined: Mar 2011
Posts: 3,150
Budapest
sivan Offline
Expert
sivan  Offline
Expert

Joined: Mar 2011
Posts: 3,150
Budapest
cool, thanks!


Free world editor for 3D Gamestudio: MapBuilder Editor

Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1