- script sort_index -1,{
OnInit:
OnWhisperGlobal:
if (playerattached()) {
.@total = atoi(@whispervar0$);
}
if (!.@total) {
.@total = 1000;
}
if (playerattached()) {
dispbottom "==== [SORT INDEX] Testing for " + .@total + " elements.";
}
else {
debugmes "==== [SORT INDEX] Testing for " + .@total + " elements.";
}
freeloop 1;
sleep2 1000;
// Create random array
for (.@i = 0; .@i < .@total; .@i++) {
.@array[.@i] = rand(100);
}
// Functions to call
setarray .@tests$, "merge_sort_index", "merge_sort_index_asm", "comb_sort_index", "comb_sort_index_asm", "counting_sort_index", "counting_sort_index_asm";
// Runs tests
for (.@count = getarraysize(.@tests$); .@j < .@count; ++.@j) {
.@start = gettimetick(0);
callfunc( .@tests$[.@j], .@array, .@output, .@total);
.@end = gettimetick(0);
.@broken = false;
// Check if test passed
for (.@i = 0; .@i < .@total - 1; .@i++) {
if (.@array[ .@output[.@i] ] > .@array[ .@output[.@i+1] ]){
.@broken = true;
break;
}
}
if (playerattached()) {
dispbottom "[" + .@tests$[.@j] + "] Time used -> " + ( .@end - .@start ) + " ms [" + (.@broken ? "FAILED" : "PASSED") + "]";
}
else {
debugmes "[" + .@tests$[.@j] + "] Time used -> " + ( .@end - .@start ) + " ms [" + (.@broken ? "FAILED" : "PASSED") + "]";
}
}
}
- script sort -1,{
OnInit:
OnWhisperGlobal:
if (playerattached()) {
.@total = atoi(@whispervar0$);
}
if (!.@total) {
.@total = 1000;
}
if (playerattached()) {
dispbottom "==== [SORT] Testing for " + .@total + " elements.";
}
else {
debugmes "==== [SORT] Testing for " + .@total + " elements.";
}
freeloop 1;
sleep2 1000;
// Create random array
for (.@i = 0; .@i < .@total; .@i++) {
.@array[.@i] = rand(100);
}
// Functions to call
setarray .@tests$, "merge_sort", "merge_sort_asm", "comb_sort", "comb_sort_asm", "counting_sort", "counting_sort_asm";
// Runs tests
for (.@count = getarraysize(.@tests$); .@j < .@count; ++.@j) {
.@start = gettimetick(0);
callfunc( .@tests$[.@j], .@array, .@output, .@total);
.@end = gettimetick(0);
.@broken = false;
// Check if test passed
for (.@i = 0; .@i < .@total - 1; .@i++) {
if (.@output[.@i] > .@output[.@i+1]){
.@broken = true;
break;
}
}
if (playerattached()) {
dispbottom "[" + .@tests$[.@j] + "] Time used -> " + ( .@end - .@start ) + " ms [" + (.@broken ? "FAILED" : "PASSED") + "]";
}
else {
debugmes "[" + .@tests$[.@j] + "] Time used -> " + ( .@end - .@start ) + " ms [" + (.@broken ? "FAILED" : "PASSED") + "]";
}
}
}
/**
* Sorting array using a BottomUp Merge Sort algorythm
* http://en.wikipedia.org/wiki/Merge_sort
*
* @param {array} input
* @param {array} sorted input
* @param {optional|integer} array size
*/
function script merge_sort {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
.@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];
.@l++;
} else {
.@tmp_arr[.@left] = .@_arr[.@m];
.@m++;
}
.@left++;
}
if (.@middle - .@l) {
copyarray .@tmp_arr[.@left], .@_arr[.@l], .@middle - .@l;
.@left += .@middle - .@l;
}
if (.@right - .@m) {
copyarray .@tmp_arr[.@left], .@_arr[.@m], .@right - .@m;
.@left += .@right - .@m;
}
}
.@width *= 2;
copyarray .@_arr, .@tmp_arr, .@size;
}
copyarray getarg(1), .@_arr, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a BottomUp Merge Sort algorythm
* http://en.wikipedia.org/wiki/Merge_sort
*
* @param {array} input
* @param {array} sorted input
* @param {optional|integer} array size
*/
function script merge_sort_asm {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
if (.@size < 2) {
return;
}
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
.@width = 1;
LOOP1:
.@left = 0;
LOOP2:
.@middle = .@size < .@left + .@width ? .@size : .@left + .@width;
.@right = .@size < .@left + .@width * 2 ? .@size : .@left + .@width * 2;
.@l = .@left;
.@m = .@middle;
goto LOOP3_START;
LOOP3:
if (.@_arr[.@l] < .@_arr[.@m]) {
.@tmp_arr[.@left++] = .@_arr[.@l++];
} else {
.@tmp_arr[.@left++] = .@_arr[.@m++];
}
LOOP3_START:
jump_zero(.@l >= .@middle || .@m >= .@right, LOOP3);
if (.@middle - .@l) {
copyarray .@tmp_arr[.@left], .@_arr[.@l], .@middle - .@l;
.@left += .@middle - .@l;
}
if (.@right - .@m) {
copyarray .@tmp_arr[.@left], .@_arr[.@m], .@right - .@m;
.@left += .@right - .@m;
}
jump_zero(.@left >= .@size, LOOP2);
.@width *= 2;
copyarray .@_arr, .@tmp_arr, .@size;
jump_zero(.@width >= .@size, LOOP1);
copyarray getarg(1), .@_arr, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a BottomUp Merge Sort algorythm
* export a sorted list of the array index
* http://en.wikipedia.org/wiki/Merge_sort
*
* @param {array} input
* @param {array} sorted input's indexes
* @param {optional|integer} array size
*/
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;
}
/**
* Sorting array using a BottomUp Merge Sort algorythm
* export a sorted list of the array index
* http://en.wikipedia.org/wiki/Merge_sort
*
* @param {array} input
* @param {array} sorted input's indexes
* @param {optional|integer} array size
*/
function script merge_sort_index_asm {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
.@i = 1;
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
LOOP0: // start at index 1
.@_idx[.@i] = .@i++;
jump_zero( .@i == .@size, LOOP0 );
.@width = 1;
LOOP1:
.@left = 0;
LOOP2:
.@middle = .@size < .@left + .@width ? .@size : .@left + .@width;
.@right = .@size < .@left + .@width * 2 ? .@size : .@left + .@width * 2;
.@l = .@left;
.@m = .@middle;
goto LOOP3_START;
LOOP3:
if (.@_arr[.@l] < .@_arr[.@m]) {
.@tmp_arr[.@left] = .@_arr[.@l];
.@tmp_idx[.@left++] = .@_idx[.@l++];
} else {
.@tmp_arr[.@left] = .@_arr[.@m];
.@tmp_idx[.@left++] = .@_idx[.@m++];
}
LOOP3_START:
jump_zero(.@l >= .@middle || .@m >= .@right, LOOP3);
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;
}
jump_zero(.@left >= .@size, LOOP2);
.@width *= 2;
copyarray .@_arr, .@tmp_arr, .@size;
copyarray .@_idx, .@tmp_idx, .@size;
jump_zero(.@width >= .@size, LOOP1);
copyarray getarg(1), .@_idx, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a Comb Sort algorythm
* http://en.wikipedia.org/wiki/Comb_sort
*
* @param {array} input
* @param {array} sorted input
* @param {optional|integer} array size
*/
function script comb_sort {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
.@gap = .@size;
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
do {
.@gap = .@gap > 1 ? .@gap * 10 / 13 : .@gap;
.@i = .@gap;
.@swap = -1;
while (.@i < .@size) {
if (.@_arr[.@i-.@gap] > .@_arr[.@i]) {
.@swap = .@_arr[.@i-.@gap];
.@_arr[.@i-.@gap] = .@_arr[.@i];
.@_arr[.@i] = .@swap;
}
.@i++;
}
} while (.@swap > -1 || .@gap > 1);
copyarray getarg(1), .@_arr, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a Comb Sort algorythm
* http://en.wikipedia.org/wiki/Comb_sort
*
* @param {array} input
* @param {array} sorted input
* @param {optional|integer} array size
*/
function script comb_sort_asm {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
.@gap = .@size;
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
LOOP1:
.@gap = .@gap > 1 ? .@gap * 10 / 13 : .@gap;
.@i = .@gap;
.@swap = -1;
LOOP2:
if (.@_arr[.@i-.@gap] > .@_arr[.@i]) {
.@swap = .@_arr[.@i-.@gap];
.@_arr[.@i-.@gap] = .@_arr[.@i];
.@_arr[.@i] = .@swap;
}
jump_zero((++.@i) >= .@size, LOOP2);
jump_zero(.@swap == -1 && .@gap == 1, LOOP1);
copyarray getarg(1), .@_arr, .@size;
//freeloop(.@state);
return;
}
/**
* 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;
}
/**
* 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_asm {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
.@gap = .@size;
.@i = 1;
//freeloop(1);
copyarray .@_arr, getarg(0), .@size;
LOOP0: // start at index 1
.@_idx[.@i] = .@i++;
jump_zero( .@i == .@size, LOOP0 );
LOOP1:
.@gap = .@gap > 1 ? .@gap * 10 / 13 : .@gap;
.@i = .@gap;
.@swap = -1;
LOOP2:
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++;
jump_zero(.@i >= .@size, LOOP2);
jump_zero(.@swap == -1 && .@gap == 1, LOOP1);
copyarray getarg(1), .@_idx, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a Counting Sort algorythm
* http://en.wikipedia.org/wiki/Counting_sort
*
* In fact it's a hacky way
*
* @param {array} input
* @param {array} sorted input
* @param {optional|integer} array size
* @param {optional|boolean} is unsigned array ?
*/
function script counting_sort {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
// If the third element is set to true, the array list
// is considered as uint32 array, so can be in a range of [0, +2'147'483'647]
// if not (and by default) I assume the array can contain negative
// numbers and the limitation is about [-1'073'741'824, +1'073'741'824]
.@neg = getarg(3, 0) ? 0 : 1<<30;
freeloop(1);
copyarray .@_arr, getarg(0), .@size;
while (.@i < .@size) {
.@tmp[.@_arr[.@i] + .@neg]++;
.@i++;
}
while ((.@val = getarraysize(.@tmp)-1)>-1) {
do {
.@_out[--.@size] = .@val - .@neg;
} while (--.@tmp[.@val]);
deletearray .@tmp[.@val], 1;
}
copyarray getarg(1), .@_out, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a Counting Sort algorythm
* http://en.wikipedia.org/wiki/Counting_sort
*
* In fact it's a hacky way
*
* @param {array} input
* @param {array} sorted input
* @param {optional|integer} array size
* @param {optional|boolean} is unsigned array ?
*/
function script counting_sort_asm {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
jump_zero( .@size, EXIT);
// If the third element is set to true, the array list
// is considered as uint32 array, so can be in a range of [0, +2'147'483'647]
// if not (and by default) I assume the array can contain negative
// numbers and the limitation is about [-1'073'741'824, +1'073'741'824]
.@neg = getarg(3, 0) ? 0 : 1<<30;
freeloop(1);
copyarray .@_arr, getarg(0), .@size;
LOOP0:
.@tmp[.@_arr[.@i] + .@neg]++;
jump_zero((++.@i) == .@size, LOOP0);
goto START_LOOP1;
LOOP1:
LOOP2:
.@_out[--.@size] = .@val - .@neg;
jump_zero(!(--.@tmp[.@val]), LOOP2);
deletearray .@tmp[.@val], 1;
START_LOOP1:
jump_zero( (.@val = getarraysize(.@tmp)-1) == -1, LOOP1 );
EXIT:
copyarray getarg(1), .@_out, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a Counting Sort algorythm
* export a sorted list of the array index
* http://en.wikipedia.org/wiki/Counting_sort
* In fact it's a hacky way
*
* @param {array} input
* @param {array} sorted input's indexes
* @param {optional|integer} array size
* @param {optional|boolean} is unsigned array ?
*/
function script counting_sort_index {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
// If the third element is set to true, the array list
// is considered as uint32 array, so can be in a range of [0, +2'147'483'647]
// if not (and by default) I assume the array can contain negative
// numbers and the limitation is about [-1'073'741'824, +1'073'741'824]
.@neg = getarg(3, 0) ? 0 : 1<<30;
freeloop(1);
copyarray .@_arr, getarg(0), .@size;
while (.@i < .@size) {
.@index = .@_arr[.@i] + .@neg;
setd(".@tmp_" + .@index + "[" +.@tmp[.@index] + "]", .@i);
.@tmp[.@index]++;
.@i++;
}
while ((.@val = getarraysize(.@tmp)-1)>-1) {
do {
.@_out[--.@size] = getd(".@tmp_" + (.@val - .@neg) + "[" + (.@tmp[.@val]-1) + "]");
} while (--.@tmp[.@val]);
deletearray .@tmp[.@val], 1;
}
copyarray getarg(1), .@_out, .@size;
//freeloop(.@state);
return;
}
/**
* Sorting array using a Counting Sort algorythm
* export a sorted list of the array index
* http://en.wikipedia.org/wiki/Counting_sort
* In fact it's a hacky way
*
* @param {array} input
* @param {array} sorted input's indexes
* @param {optional|integer} array size
* @param {optional|boolean} is unsigned array ?
*/
function script counting_sort_index_asm {
//.@state = freeloop();
.@size = getarg(2, getarraysize(getarg(0)) );
// If the third element is set to true, the array list
// is considered as uint32 array, so can be in a range of [0, +2'147'483'647]
// if not (and by default) I assume the array can contain negative
// numbers and the limitation is about [-1'073'741'824, +1'073'741'824]
.@neg = getarg(3, 0) ? 0 : 1<<30;
freeloop(1);
copyarray .@_arr, getarg(0), .@size;
LOOP0:
.@index = .@_arr[.@i] + .@neg;
setd(".@tmp_" + .@index + "[" +.@tmp[.@index] + "]", .@i);
.@tmp[.@index]++;
.@i++;
jump_zero(.@i == .@size, LOOP0);
goto START_LOOP1;
LOOP1:
LOOP2:
.@_out[--.@size] = getd(".@tmp_" + (.@val - .@neg) + "[" + (--.@tmp[.@val]) + "]");
jump_zero(!.@tmp[.@val], LOOP2);
deletearray .@tmp[.@val], 1;
START_LOOP1:
jump_zero( (.@val = getarraysize(.@tmp)-1) == -1, LOOP1 );
copyarray getarg(1), .@_out, .@size;
//freeloop(.@state);
return;
}