GMLscripts.com

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

xot

Administrator

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.

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?

xot

Administrator

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.

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

Replaced your code with the code from pastebin.

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

xot

Administrator

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.

BlueMoonProductions

Member

Registered: 2010-08-25

Posts: 22

Re: quicksort algorithm

Ah, ok..

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