You are not logged in.
Pages: 1
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
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
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
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
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
Replaced your code with the code from pastebin.
Last edited by xot (2011-04-10 05:06:52)
Offline
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
Ah, ok..
But what do you think about the script? (A)
Offline
Pages: 1