Why it doesn't work ?
#1

This code is supposed to sort an array from the lowest to the highest, why it doesn't work ?
Ignore prints, it's a debug
PHP Code:
if(Array[i] > Array[i+1] && Array[i+1] < sizeof(Array))
            {
                
printf("Array[%d] = %d, Array[%d+1] = %d.", i, Array[i], i, Array[i+1]);
                
tmp = Array[i];
                 
printf("Array[%d] = %d, Array[%d+1] = %d.", i, Array[i], i, Array[i+1]);
                Array[
i] = Array[i+1];
                 
printf("Array[%d] = %d, Array[%d+1] = %d.", i, Array[i], i, Array[i+1]);
                Array[
i+1] = tmp;
                 
printf("Array[%d] = %d, Array[%d+1] = %d.", i, Array[i], i, Array[i+1]);
            } 
I tried debugging the numbers 1-2-4-3-0-0-0-0-0-0
Ended up like: 1-2-3-0-0-0-0-0-0-4
Reply
#2

You can't sort an array like that, honestly, it's more complicated than what you think. It took me 2 hours to figure out how to sort an array in this morning, though I managed to find a way to get the job done, but it's really complicated, it might help you though. I've posted it in your other topic (I guess) but I've improved it a bit. Here it is:

PHP Code:
sortArray( arr[ ], len = sizeof arr )  {
    new 
tmpVar1, tmpVar2, i;
    while(
i < len) {
        for( new 
j = len - 1; j > -1; j --) {
            if( 
arr[ j ] < arr[ i ] )  {
                
tmpVar1 = arr[ i ];
                
arr[ i ] = arr[ j ];
                
arr[ j ] = tmpVar1;
            } 
        }
        
i++;
    }
    for( 
i = 0; i < len; i ++ ) {
        if( 
i == 0 ) {
            
tmpVar1 = arr[ i ];
        }
        
tmpVar2 = arr[ i + 1 ];
        
arr[ i + 1 ] = tmpVar1;
        
tmpVar1 = tmpVar2;
        if( 
i == (len - 1) ) {
            
arr[ 0 ] = arr[ len ];
        }
    }
    return 
true;
} 
Reply
#3

https://www.youtube.com/watch?v=kPRA0W1kECg

Pick one, find an implementation. QuickSort is probably the easiest.
Reply
#4

Quote:
Originally Posted by Jayse
View Post
You can't sort an array like that, honestly, it's more complicated than what you think. It took me 2 hours to figure out how to sort an array in this morning, though I managed to find a way to get the job done, but it's really complicated, it might help you though. I've posted it in your other topic (I guess) but I've improved it a bit. Here it is:

PHP Code:
sortArray( arr[ ], len = sizeof arr )  {
    new 
tmpVar1, tmpVar2, i;
    while(
i < len) {
        for( new 
j = len - 1; j > -1; j --) {
            if( 
arr[ j ] < arr[ i ] )  {
                
tmpVar1 = arr[ i ];
                
arr[ i ] = arr[ j ];
                
arr[ j ] = tmpVar1;
            } 
        }
        
i++;
    }
    for( 
i = 0; i < len; i ++ ) {
        if( 
i == 0 ) {
            
tmpVar1 = arr[ i ];
        }
        
tmpVar2 = arr[ i + 1 ];
        
arr[ i + 1 ] = tmpVar1;
        
tmpVar1 = tmpVar2;
        if( 
i == (len - 1) ) {
            
arr[ 0 ] = arr[ len ];
        }
    }
    return 
true;
} 
Your function can't process 7+ iterations, it breaks down. So I couldn't benchmark it.

---------------------------------------------

Here's a simple version:
pawn Code:
new array[] = {30, 100, 20, 40, 5, 23, 56, 21, 2000, 40, 60, 20, 70, 80, 290, 5000, 20};
SortValuesInArray(array);

for(new i = 0; i < sizeof(array); i ++)
{
    printf("%d", array[i]);
}

stock SortValuesInArray(array[], size_of = sizeof(array))
{
    new temp;
    for(new i = 1, j = 0; i < size_of; i ++)
    {
        for(j = i; j != 0; j --)
        {
            if(array[j] < array[j - 1])
            {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
        }
    }
    return 1;
}
It performs 50,000 iterations in ~840 milliseconds.

This other one does it in ~430 milliseconds (quickSort in PAWN): http://forum.sa-mp.com/showpost.php?...postcount=1737 - The reason behind that is that it operates 2 values at a time.

However, my version is faster with less integers in the array. But for a simple one-five (or more) usage, the difference is insignificant.
Reply
#5

Quote:
Originally Posted by SickAttack
View Post
Your function can't process 7+ iterations, it breaks down. So I couldn't benchmark it.
Uhhm, but I tried benchmarking it and it works. which method did you use to benchmark it?


PHP Code:
    new 
        
arr[ 10 ] = { 70, 12, 1, 9, 7, 6, 3, 7, 10, 90 }
    ;
    
START_BENCH( 1000 );
    {
        
sortArray( arr );
    }
    
FINISH_BENCH( "sortArray" );
    for(new 
k; k < sizeof arr; k++)
        
printf("%i", arr[ k ]); 
PHP Code:
sortArray( arr[ ], len = sizeof arr )  { 
    new 
tmpVar1, tmpVar2, i; 
    while(
i < len) { 
        for( new 
j = len - 1; j > -1; j --) { 
            if( 
arr[ j ] < arr[ i ] )  { 
                
tmpVar1 = arr[ i ]; 
                
arr[ i ] = arr[ j ]; 
                
arr[ j ] = tmpVar1; 
            }  
        } 
        
i++; 
    } 
    for( 
i = 0; i < len; i ++ ) { 
        if( 
i == 0 ) { 
            
tmpVar1 = arr[ i ]; 
        } 
        
tmpVar2 = arr[ i + 1 ]; 
        
arr[ i + 1 ] = tmpVar1; 
        
tmpVar1 = tmpVar2; 
        if( 
i == (len - 1) ) { 
            
arr[ 0 ] = arr[ len ]; 
        } 
    } 
    return 
true; 
} 
PHP Code:
 Bench for sortArray: executes, by average, 28.01 times/ms.
1
3
6
7
7
9
10
12
70
90 
Reply
#6

Quote:
Originally Posted by Jayse
View Post
Uhhm, but I tried benchmarking it and it works. which method did you use to benchmark it?
pawn Code:
new tick = GetTickCount();
for(new i = 0; i < 7; i ++)
{
    new array[] = {30, 100, 20, 40, 5, 23, 56, 21, 2000, 40, 60, 20, 70, 80, 290, 5000};
    sortArray(array);
}

printf("%d", GetTickCount() - tick);

sortArray( arr[ ], len = sizeof arr )  {  
    new tmpVar1, tmpVar2, i;  
    while(i < len) {  
        for( new j = len - 1; j > -1; j --) {  
            if( arr[ j ] < arr[ i ] )  {  
                tmpVar1 = arr[ i ];  
                arr[ i ] = arr[ j ];  
                arr[ j ] = tmpVar1;  
            }  
        }  
        i++;  
    }  
    for( i = 0; i < len; i ++ ) {  
        if( i == 0 ) {  
            tmpVar1 = arr[ i ];  
        }  
        tmpVar2 = arr[ i + 1 ];  
        arr[ i + 1 ] = tmpVar1;  
        tmpVar1 = tmpVar2;  
        if( i == (len - 1) ) {  
            arr[ 0 ] = arr[ len ];  
        }  
    }  
    return true;  
}
Reply
#7

PHP Code:
main( )
{
    new array[ 
10 ], tick;
    for( new 
i; i < 10; i ++ ) {
        array[ 
i ] = random( 10000 ) - random( 2000 );
    }
    
tick = GetTickCount();
    for(new 
i = 0; i < 50000; i ++) {
        
sortArray(array);
    }
    
printf("sortArray: %dms", GetTickCount() - tick);
    
tick = GetTickCount();
    for(new 
i = 0; i < 50000; i ++) {
        
SortValuesInArray(array);
    }
    
printf("SortValuesInArray: %dms", GetTickCount() - tick);
    return 
true;
}
stock SortValuesInArray(array[], size_of = sizeof(array))
{
    new 
temp;
    for(new 
i = 1, j = 0; i < size_of; i ++)
    {
        for(
j = i; j != 0; j --)
        {
            if(array[
j] < array[j - 1])
            {
                
temp = array[j];
                array[
j] = array[j - 1];
                array[
j - 1] = temp;
            }
        }
    }
    return 
1;
}
sortArray( arr[ ], len = sizeof arr )  { 
    new 
tmpVar1, tmpVar2, i; 
    while(
i < len) { 
        for( new 
j = len - 1; j > -1; j --) { 
            if( 
arr[ j ] < arr[ i ] )  { 
                
tmpVar1 = arr[ i ]; 
                
arr[ i ] = arr[ j ]; 
                
arr[ j ] = tmpVar1; 
            }  
        } 
        
i++; 
    } 
    for( 
i = 0; i < len; i ++ ) { 
        if( 
i == 0 ) { 
            
tmpVar1 = arr[ i ]; 
        } 
        
tmpVar2 = arr[ i + 1 ]; 
        
arr[ i + 1 ] = tmpVar1; 
        
tmpVar1 = tmpVar2; 
        if( 
i == (len - 1) ) { 
            
arr[ 0 ] = arr[ len ]; 
        } 
    } 
    return 
true; 
} 
Code:
sortArray: 1822ms
SortValuesInArray: 641ms
it compiles and executes fine. Yours is faster anyways. I guess I should get rid of that second loop in mine.

Edit:

I got rid of the loop, but it still performs pretty much the same, like a very small difference, any idea why?

PHP Code:
sortArray( arr[ ], len = sizeof arr )  { 
    new 
tVar, i; 
    while(
i <= len) { 
        for( new 
j = len ; j > -1; j --) { 
            if( 
arr[ j ] < arr[ i ] )  { 
                
tVar = arr[ i ]; 
                
arr[ i ] = arr[ j ]; 
                
arr[ j ] = tVar; 
            }  
        } 
        
i++; 
    } 
    return 
true; 
} 
Code:
-183,0,756,1748,2740,5751,5980,6320,6493,7657
sortArray: 1957ms
SortValuesInArray: 637ms
I guess I've just hijacked someone else's thread.

Edit again:

Okay I guess now it's optimized, but still slower than SickAttack's one.

PHP Code:
sortArray( arr[ ], len = sizeof arr )  { 
    new 
tVar; 
    for( new 
i; i <= len; i++ ) { 
        for( new 
j = ( len - 1 ) ; j > ( i - 1 ); j --) { 
            if( 
arr[ j ] < arr[ i ] )  { 
                
tVar = arr[ i ]; 
                
arr[ i ] = arr[ j ]; 
                
arr[ j ] = tVar; 
            }  
        } 
    } 
    return 
true; 
} 
Code:
before sorting: 9,12,14,19,7,17,15,0,17,19
after sorting: 0,7,9,12,14,15,17,17,19,19
sortArray: 854ms
SortValuesInArray: 641ms
Reply
#8

It can become much faster with a bit more of work, but at the end of the day it's not really needed. It will execute in about 0 milliseconds in most of the cases (if not all). I've never seen someone use a sorting algorithm for something non-performance friendly, but that doesn't mean there wouldn't be any cases. So it would be good to do our best in case someone needs it for something. I'd also like a challenge.

I updated my function, and it's slightly faster (~8 milliseconds). I'll try to edit it more tomorrow, I have something in mind.

pawn Code:
stock SortValuesInArray(array[], size_of = sizeof(array))
{
    new temp;
    for(new i = size_of, j = 0; i != 0; i --)
    {
        for(j = (size_of - i); j != 0; j --)
        {
            if(array[j] < array[j - 1])
            {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
        }
    }
    return 1;
}
P.S. We almost have the same function, lol.
Reply
#9

Finally I fixed my loop conditions, and improved the function a bit. I'm shocked that conditions in loops affects the code this much, it used to execute in ~850ms now it's ~620ms.
PHP Code:
sortArray( arr[ ], len = sizeof arr ) {  
    new 
tVar, i, j;  
       for( 
i = len - 1; i > -1; i -- ) {  
        for( 
j = 0; j < i; j ++ ) {  
            if( 
arr[ i ] < arr[ j ] ) { 
                
tVar = arr[ i ];  
                
arr[ i ] = arr[ j ];  
                
arr[ j ] = tVar;  
            } 
        }  
    }  
    return 
true;  
} 
full testing code:
PHP Code:
main( )
{
    
    new array[ 
10 ];
    for( new 
i; i < 10; i ++ ) {
        array[ 
i ] = random( 200 );
    }
    for(new 
j; j < 10; j ++) {
        new 
tick = GetTickCount();
        for( new 
i; i < 50000; i++ ) sortArray( array );
        
printf("Test No. %i: Time taken to execute \"sortArray\" 50000 times is: %ims", j + 1, GetTickCount() - tick );
    }
    for(new 
j; j < 10; j ++) {
        new 
tick = GetTickCount();
         for( new 
i; i < 50000; i++ ) SortValuesInArray( array );
        
printf("Test No. %i: Time taken to execute \"SortValuesInArray\" 50000 times is: %ims", j + 1, GetTickCount() - tick );
    }
    
    return 
true;
}
sortArray( arr[ ], len = sizeof arr ) { 
    new 
tVar, i, j; 
       for( 
i = len - 1; i > -1; i -- ) { 
        for( 
j = 0; j < i; j ++ ) { 
            if( 
arr[ i ] < arr[ j ] ) {
                
tVar = arr[ i ]; 
                
arr[ i ] = arr[ j ]; 
                
arr[ j ] = tVar; 
            }
        } 
    } 
    return 
true; 
}  
stock SortValuesInArray(array[], size_of = sizeof(array))
{
    new 
temp;
    for(new 
i = size_of, j = 0; i != 0; i --)
    {
        for(
j = (size_of - i); j != 0; j --)
        {
            if(array[
j] < array[j - 1])
            {
                
temp = array[j];
                array[
j] = array[j - 1];
                array[
j - 1] = temp;
            }
        }
    }
    return 
1;
} 
Code:
Test No. 1: Time taken to execute "sortArray" 50000 times is: 629ms
Test No. 2: Time taken to execute "sortArray" 50000 times is: 620ms
Test No. 3: Time taken to execute "sortArray" 50000 times is: 621ms
Test No. 4: Time taken to execute "sortArray" 50000 times is: 620ms
Test No. 5: Time taken to execute "sortArray" 50000 times is: 617ms
Test No. 6: Time taken to execute "sortArray" 50000 times is: 614ms
Test No. 7: Time taken to execute "sortArray" 50000 times is: 622ms
Test No. 8: Time taken to execute "sortArray" 50000 times is: 622ms
Test No. 9: Time taken to execute "sortArray" 50000 times is: 616ms
Test No. 10: Time taken to execute "sortArray" 50000 times is: 617ms

Test No. 1: Time taken to execute "SortValuesInArray" 50000 times is: 655ms
Test No. 2: Time taken to execute "SortValuesInArray" 50000 times is: 656ms
Test No. 3: Time taken to execute "SortValuesInArray" 50000 times is: 661ms
Test No. 4: Time taken to execute "SortValuesInArray" 50000 times is: 659ms
Test No. 5: Time taken to execute "SortValuesInArray" 50000 times is: 652ms
Test No. 6: Time taken to execute "SortValuesInArray" 50000 times is: 657ms
Test No. 7: Time taken to execute "SortValuesInArray" 50000 times is: 670ms
Test No. 8: Time taken to execute "SortValuesInArray" 50000 times is: 658ms
Test No. 9: Time taken to execute "SortValuesInArray" 50000 times is: 660ms
Test No. 10: Time taken to execute "SortValuesInArray" 50000 times is: 656ms
Reply
#10

Well, here's the final version of this method:
pawn Code:
stock SortValuesInArray(array[], size_of = sizeof(array))
{
    for(new i = (size_of - 1), j, temp; i != 0; i --)
    {
        for(j = 0; j < i; j ++)
        {
            if(array[i] < array[j])
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    return 1;
}
It's ~60 milliseconds slower than quickSort (though this might depend on the pivot), and ~20 milliseconds faster than yours.
Reply


Forum Jump:


Users browsing this thread: