# GMLscripts.com

Discuss and collaborate on GML scripts

You are not logged in.

## #1 2011-04-04 09:51:03

BlueMoonProductions
Member
Registered: 2010-08-25
Posts: 22

### quicksort algorithm

This is a quicksort algorithm I recently wrote. Quicksort is an extremely powerful algorithm to sort arrays.
The script is called using quicksort(min,max), and will sort an array ranging from array[min] to array[max].

Expandvar m, M, p;
m = argument[0]
M = argument[1]

if !(m < M)
{
return 0
}else if (m+1 == M){
if array[m] > array[m]
{
array[m] = array[m] ^ array[m];
array[m] = array[m] ^ array[m];
array[m] = array[m] ^ array[m];
}
return 0
}

p = array[ floor( (m+M)/2 ) ]
array[floor( (m+M)/2 )] = array[m]
array[m] = p

while (m < M)
{
while ( (array[m] <= p) && (m<M) )
{
m += 1
}

while ( (array[m] >= p) && (m<M) )
{
M -= 1
}

if (m < M)
{
array[m] = array[m] ^ array[m];
array[m] = array[m] ^ array[m];
array[m] = array[m] ^ array[m];
}
}

array[m] = p

quicksort(argument[0], m-1)
quicksort(M+1, argument[1])

This algorithm sorts a 6000 field array in 140 miliseconds(on my PC).

Offline

## #2 2011-04-05 05:44:54

xot
Registered: 2007-08-18
Posts: 1,240

### Re: quicksort algorithm

It looks like there are some errors. See the XOR swap code? It looks like 'm' is getting mixed up with 'M' in a few places. Not sure if there are similar problems elsewhere.

This could be useful for Lite users, and as a learning tool, but I suspect populating a ds_list with array contents, sorting that with ds_list_sort(), and sending it back to the array would be faster.

This is a bit inflexible as a general purpose script since it only works on an array called 'array[]'. Passing the array name and using variable/array manipulation functions would make it more useful, but it would probably also be a bit slower.

Abusing forum power since 1986.

Offline

## #3 2011-04-05 07:59:21

BlueMoonProductions
Member
Registered: 2010-08-25
Posts: 22

### Re: quicksort algorithm

Here is an updated, working version:

Expandvar m, M, p, n, t;
m = argument0;
M = argument1;

if m >= M
{
return 0;
}
if (m+1 == M)
{
if array[m] > array[m]
{
t = array[m];
array[m] = array[m];
array[m] = t;
}
return 0;
}

n = (m+M) div 2;
p = array[n];
array[n] = array[m];
array[m] = p;

repeat M-m
{
if (array[m] > p) break;
m += 1;
}
repeat M-m
{
if (array[m] < p) break;
M -= 1;
}

while (m < M)
{
t = array[m];
array[m] = array[m];
array[m] = t;
repeat M-m
{
if (array[m] > p) break;
m += 1;
}
repeat M-m
{
if (array[m] < p) break;
M -= 1;
}
}

array[argument1] = array[m];
array[m] = p;

quicksort(argument0, m-1);
quicksort(m+1, argument1);

Should I make variable_global/local_array function? Or is this ok?

Offline

## #4 2011-04-05 10:06:47

xot
Registered: 2007-08-18
Posts: 1,240

### Re: quicksort algorithm

Is this really working? I haven't tested it, but the code quoted below clearly doesn't do anything.

Expand    if array[m] > array[m]
{
t = array[m];
array[m] = array[m];
array[m] = t;
}
Expand    t = array[m];
array[m] = array[m];
array[m] = t;

Abusing forum power since 1986.

Offline

## #5 2011-04-05 14:27:32

BlueMoonProductions
Member
Registered: 2010-08-25
Posts: 22

### Re: quicksort algorithm

Expandvar m, M, p, n, t;
m = argument0;
M = argument1;

if m >= M
{
return 0;
}
if (m+1 == M)
{
if array[m] > array[M]
{
t = array[m];
array[m] = array[M];
array[M] = t;
}
return 0;
}

n = (m+M) div 2;
p = array[n];
array[n] = array[M];
array[M] = p;

repeat M-m
{
if (array[m] > p) break;
m += 1;
}
repeat M-m
{
if (array[M] < p) break;
M -= 1;
}

while (m < M)
{
t = array[m];
array[m] = array[M];
array[M] = t;
repeat M-m
{
if (array[m] > p) break;
m += 1;
}
repeat M-m
{
if (array[M] < p) break;
M -= 1;
}
}

array[argument1] = array[m];
array[m] = p;

quicksort(argument0, m-1);
quicksort(m+1, argument1);

EDIT: Eh, your forum acts weird.. It automatically lowercased some M's to m's..(EDIT2: M's with no spaces on both sides, to be precies) Here's a version on pastebin: http://pastebin.com/8zZDT56R

xot wrote:

Replaced your code with the code from pastebin.

Last edited by xot (2011-04-10 05:06:52)

Offline

## #6 2011-04-05 17:52:22

xot
Registered: 2007-08-18
Posts: 1,240

### Re: quicksort algorithm

Eh, your forum acts weird.. It automatically lowercased some M's to m's.

Ohhhhh, I'm very sorry. The problem is because [m] is a BBCode for the old math renderer and for some reason it is not being fully ignored within code blocks. The forum software "helpfully" converts BBCodes to lowercase so that mixed-cases render as expected. I'm amazed this hasn't come up already. I'll look into it.

Expand// Mangled code
array[b] = array[i] * array[u] + array[s] * array[m];

EDIT:
The problem should be fixed now, although the damage has already been done to previously posted code. The only simple solution was to prevent the case-changing globally. From now on, only lower-case BBCode tags will work correctly. I have repaired your last post using the code you posted at pastebin.

Expand// Non-mangled code
array[B] = array[I] * array[U] + array[S] * array[M];

Last edited by xot (2011-04-10 05:09:58)

Abusing forum power since 1986.

Offline

## #7 2011-04-09 13:13:16

BlueMoonProductions
Member
Registered: 2010-08-25
Posts: 22

### Re: quicksort algorithm

Ah, ok..

But what do you think about the script? (A)

Offline