function script test_sort {
freeloop true;
.@total = 1000;
for ( .@i = 0; .@i < .@total; .@i++ )
.@array[.@i] = rand(50);
.@start = gettimetick(0);
callfunc getarg(0), .@array, .@output, .@total;
.@end = gettimetick(0);
for ( .@i = 0; .@i < .@total; .@i++ )
.@print$[.@i] = .@array[ .@output[.@i] ];
debugmes implode( .@print$, "," );
dispbottom "time used -> "+( .@end - .@start )+" mili-seconds";
}
prontera,152,188,5 script test merge sort haru 1_F_MARIA,{
callfunc "test_sort", "merge_sort_haru";
end;
}
prontera,155,188,5 script test merge sort keyworld 1_F_MARIA,{
callfunc "test_sort", "merge_sort_index";
end;
}
prontera,158,188,5 script test counting sort 1_F_MARIA,{
callfunc "test_sort", "counting_sort_index";
end;
}
prontera,161,188,5 script test comb sort keyworld 1_F_MARIA,{
callfunc "test_sort", "comb_sort_index";
end;
}
prontera,164,188,5 script test comb sort haru 1_F_MARIA,{
callfunc "test_sort", "comb_sort_haru";
end;
}
prontera,158,185,5 script counting sort asm 1_F_MARIA,{
callfunc "test_sort", "counting_sort_index_asm";
end;
}
// callfunc "merge_sort", <input array>, <output index>, <total index>;
// Credits to Haru -> http://hercules.ws/board/topic/4321-
function script merge_sort_haru {
.@size = getarg(2);
copyarray .@arr, getarg(0), .@size;
while ( .@i < .@size ) {
set getelementofarray(getarg(1), .@i), .@i;
.@i++;
}
.@width = 1;
while ( .@width < .@size ) {
.@i = 0;
while ( .@i < .@size ) {
.@left = .@i;
.@middle = .@i + .@width;
.@right = .@i + 2*.@width;
if (.@size < .@middle) .@middle = .@size;
if (.@size < .@right) .@right = .@size;
.@i0 = .@left;
.@i1 = .@middle;
.@j = .@left;
while ( .@j < .@right ) {
if (.@i0 < .@middle && (.@i1 >= .@right || .@arr[.@i0] <= .@arr[.@i1])) {
.@tmp_array[.@j] = .@arr[.@i0];
.@tmp_array2[.@j] = getelementofarray(getarg(1), .@i0);
.@i0++;
} else {
.@tmp_array[.@j] = .@arr[.@i1];
.@tmp_array2[.@j] = getelementofarray(getarg(1), .@i1);
.@i1++;
}
.@j++;
}
.@i += 2 * .@width;
}
.@width *= 2;
copyarray .@arr, .@tmp_array, .@size;
copyarray getarg(1), .@tmp_array2, .@size;
}
return;
}
// Keyworld's merge sort
function script merge_sort_index {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
while ((++.@i) < .@size) { // start at index 1
.@_idx[.@i] = .@i;
}
.@width = 1;
while (.@width < .@size) {
.@left = 0;
while (.@left < .@size) {
.@middle = .@size < .@left + .@width ? .@size : .@left + .@width;
.@right = .@size < .@left + .@width * 2 ? .@size : .@left + .@width * 2;
.@l = .@left;
.@m = .@middle;
while (.@l < .@middle && .@m < .@right) {
if (.@_arr[.@l] < .@_arr[.@m]) {
.@tmp_arr[.@left] = .@_arr[.@l];
.@tmp_idx[.@left] = .@_idx[.@l];
.@l++;
} else {
.@tmp_arr[.@left] = .@_arr[.@m];
.@tmp_idx[.@left] = .@_idx[.@m];
.@m++;
}
.@left++;
}
if (.@middle - .@l) {
copyarray .@tmp_arr[.@left], .@_arr[.@l], .@middle - .@l;
copyarray .@tmp_idx[.@left], .@_idx[.@l], .@middle - .@l;
.@left += .@middle - .@l;
}
if (.@right - .@m) {
copyarray .@tmp_arr[.@left], .@_arr[.@m], .@right - .@m;
copyarray .@tmp_idx[.@left], .@_idx[.@m], .@right - .@m;
.@left += .@right - .@m;
}
}
.@width *= 2;
copyarray .@_arr, .@tmp_arr, .@size;
copyarray .@_idx, .@tmp_idx, .@size;
}
copyarray getarg(1), .@_idx, .@size;
//freeloop(.@state);
return;
}
// my counting sort, idea from keyworld
function script counting_sort_index {
.@total = .@size = getarg( 2, getarraysize( getarg(0) ) );
copyarray .@arr, getarg(0), .@size;
while ( .@i < .@size ) {
setd ".@index_"+ .@arr[.@i] +"["+( .@tmp[.@arr[.@i]] )+"]", .@i;
.@tmp[.@arr[.@i]]++;
.@i++;
}
do {
.@index = getarraysize(.@tmp) -1;
.@tmp[.@index]--;
.@out[.@size-1] = getd( ".@index_"+ .@index +"["+( .@tmp[.@index] )+"]" );
.@size--;
} while( .@size );
copyarray getarg(1), .@out, .@total;
return;
}
/** Made by Keyworld
* Sorting array using a Comb Sort algorythm
* export a sorted list of the array index
* http://en.wikipedia.org/wiki/Comb_sort
*
* @param {array} input
* @param {array} sorted input's input
* @param {optional|integer} array size
*/
function script comb_sort_index {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
.@gap = .@size;
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
while ((++.@i) < .@size) { // start at index 1
.@_idx[.@i] = .@i;
}
do {
.@gap = .@gap > 1 ? .@gap * 10 / 13 : .@gap;
.@i = .@gap;
.@swap = -1;
while (.@i < .@size) {
if (.@_arr[.@i-.@gap] > .@_arr[.@i]) {
.@swap = .@i - .@gap;
.@tmp = .@_arr[.@swap];
.@_arr[.@swap] = .@_arr[.@i];
.@_arr[.@i] = .@tmp;
.@tmp = .@_idx[.@swap];
.@_idx[.@swap] = .@_idx[.@i];
.@_idx[.@i] = .@tmp;
}
.@i++;
}
} while (.@swap > -1 || .@gap > 1);
copyarray getarg(1), .@_idx, .@size;
//freeloop(.@state);
return;
}
// callfunc "comb_sort", <input array>, <output index>, <total index>;
function script comb_sort_haru {
.@size = .@gap = getarg(2);
copyarray .@arr, getarg(0), .@size;
while ( .@i < .@size ) {
set getelementofarray( getarg(1), .@i ), .@i;
.@i++;
}
.@gap10 = .@size * 10;
do {
if ( .@gap10 > 10 ) {
.@gap10 = .@gap10 * 10 / 13;
.@gap = .@gap10 / 10;
}
.@i = .@swap = 0;
while ( .@i + .@gap < .@size ) {
if ( .@arr[.@i] > .@arr[ .@i + .@gap ] ) {
.@tmp = .@arr[.@i];
.@arr[.@i] = .@arr[ .@i + .@gap ];
.@arr[ .@i + .@gap ] = .@tmp;
.@tmp = getelementofarray( getarg(1), .@i );
set getelementofarray( getarg(1), .@i ), getelementofarray( getarg(1), .@i + .@gap );
set getelementofarray( getarg(1), .@i + .@gap ), .@tmp;
.@swap = 1;
}
.@i++;
}
} while ( .@swap || .@gap10 > 10 );
return;
}
// my counting sort, idea from keyworld
function script counting_sort_index_asm {
.@total = .@size = getarg( 2, getarraysize( getarg(0) ) );
copyarray .@arr, getarg(0), .@size;
LOOP1:
setd ".@index_"+ .@arr[.@i] +"["+( .@tmp[.@arr[.@i]] )+"]", .@i;
.@tmp[.@arr[.@i]]++;
.@i++;
__jump_zero ( .@i == .@size ), LOOP1;
LOOP2:
.@index = getarraysize(.@tmp) -1;
.@tmp[.@index]--;
.@out[.@size-1] = getd( ".@index_"+ .@index +"["+( .@tmp[.@index] )+"]" );
.@size--;
__jump_zero !.@size, LOOP2;
copyarray getarg(1), .@out, .@total;
return;
}