Discuss and collaborate on GML scripts

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

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

```
var 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

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

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

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

Here is an updated, working version:

```
var 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

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

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

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

```
t = array[m];
array[m] = array[m];
array[m] = t;
```

*Abusing forum power since 1986.*

Offline

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

```
var 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

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

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.

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

```
// 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

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

Ah, ok..

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

Offline

Pages: **1**