Dynamic Array's Binary Insertion Sorted
Posted: Sat Oct 03, 2026 6:05 pm
Dynamic Array's Binary Insertion Sorted
Introduction
This is useful to keep a array sorted when you always need it to be sorted and do not
want to keep calling sort every time you insert something on the array.
This is the code for insertion at AMXX 183:
This is the array's swift when performing a insertion at a specific position by ArrayInsertCellAfter().
As is performed right on C++, its has better performance than using a static array
in pawn and doing the shift.
The stock
Output example:
Test Source Code:
Introduction
This is useful to keep a array sorted when you always need it to be sorted and do not
want to keep calling sort every time you insert something on the array.
This is the code for insertion at AMXX 183:
Code: Select all
cell *insert_at(size_t index)
{
/* Make sure it'll fit */
if (!GrowIfNeeded(1))
{
return nullptr;
}
/* move everything up */
cell *src = at(index);
cell *dst = at(index + 1);
memmove(dst, src, sizeof(cell)* m_BlockSize * (m_Size - index));
m_Size++;
return src;
}As is performed right on C++, its has better performance than using a static array
in pawn and doing the shift.
The stock
Code: Select all
/**
* Insert a integer value in a sorted dynamic array, keeping the array sorted.
*
* This function has the worst case complexity O( n*log(n) ) where n is the array's size, because:
*
* 1. O( log(n) ) is the worst case complexity of the binary search performed to find the
* correct position to insert the element.
* 2. O( n ) is the worst case complexity to shift all array's elements, if the insertion
* of the element occurs at the beginning of the array.
*
* Use this algorithm is slightly faster than normal insertion and sort by the algorithm
* Quick Sort with the same complexity O( n*log(n) ) on the average case and O( n^2 )
* at the worst case.
*
* @param array a sorted Dynamic Array handler created by the constructor `ArrayCreate()`.
* @param element an integer element to insert on the array.
*/
stock binaryInsertionSorted( Array:array, element )
{
new currentCell;
new arraySize = ArraySize( array );
new lowIndex = 0;
new highIndex = arraySize - 1;
new middleIndex = arraySize / 2;
while( lowIndex < highIndex )
{
currentCell = ArrayGetCell( array, middleIndex );
if( element > currentCell )
{
lowIndex = middleIndex + 1;
}
else if( element < currentCell )
{
highIndex = middleIndex;
}
else
{
// The element is a duplicate at the position `middleIndex`
return;
}
middleIndex = lowIndex + ( ( highIndex - lowIndex ) / 2 );
}
// Here you add the element on the array
if( arraySize )
{
// Get the `currentCell` at the position `middleIndex`
currentCell = ArrayGetCell( array, middleIndex );
// To determinate whether to add the `element` after or before the position `middleIndex`.
if( currentCell < element )
{
ArrayInsertCellAfter( array, middleIndex, element )
}
else
{
ArrayInsertCellBefore( array, middleIndex, element )
}
}
else
{
ArrayPushCell( array, element );
}
}
Code: Select all
new Array:array = ArrayCreate();
binaryInsertionSorted( array, 0 );
binaryInsertionSorted( array, 3 );
binaryInsertionSorted( array, 2 );
binaryInsertionSorted( array, 1 );
binaryInsertionSorted( array, 5 );
binaryInsertionSorted( array, 7 );
binaryInsertionSorted( array, 4 );
binaryInsertionSorted( array, 10 );
binaryInsertionSorted( array, 13 );
binaryInsertionSorted( array, 15 );
binaryInsertionSorted( array, 19 );
binaryInsertionSorted( array, 21 );
binaryInsertionSorted( array, 22 );
binaryInsertionSorted( array, 25 );
binaryInsertionSorted( array, 56 );
binaryInsertionSorted( array, 78 );
binaryInsertionSorted( array, 88 );
binaryInsertionSorted( array, 20 );
binaryInsertionSorted( array, 20 );
binaryInsertionSorted( array, 21 );
binaryInsertionSorted( array, 77 );
binaryInsertionSorted( array, 78 );
binaryInsertionSorted( array, 79 );
binaryInsertionSorted( array, 179 );
printDynamicArrayCells( array );
ArrayDestroy( array );Code: Select all
lowIndex: 0, middleIndex: 0, highIndex: -1.
Adding element 0 to the array's end.
lowIndex: 0, middleIndex: 0, highIndex: 0.
Adding element 3 after the position 0.
lowIndex: 0, middleIndex: 1, highIndex: 1.
lowIndex: 0, middleIndex: 0, highIndex: 1.
lowIndex: 1, middleIndex: 1, highIndex: 1.
Adding element 2 before the position 1.
lowIndex: 0, middleIndex: 1, highIndex: 2.
lowIndex: 0, middleIndex: 0, highIndex: 1.
lowIndex: 1, middleIndex: 1, highIndex: 1.
Adding element 1 before the position 1.
lowIndex: 0, middleIndex: 2, highIndex: 3.
lowIndex: 3, middleIndex: 3, highIndex: 3.
Adding element 5 after the position 3.
lowIndex: 0, middleIndex: 2, highIndex: 4.
lowIndex: 3, middleIndex: 3, highIndex: 4.
lowIndex: 4, middleIndex: 4, highIndex: 4.
Adding element 7 after the position 4.
lowIndex: 0, middleIndex: 3, highIndex: 5.
lowIndex: 4, middleIndex: 4, highIndex: 5.
lowIndex: 4, middleIndex: 4, highIndex: 4.
Adding element 4 before the position 4.
lowIndex: 0, middleIndex: 3, highIndex: 6.
lowIndex: 4, middleIndex: 5, highIndex: 6.
lowIndex: 6, middleIndex: 6, highIndex: 6.
Adding element 10 after the position 6.
lowIndex: 0, middleIndex: 4, highIndex: 7.
lowIndex: 5, middleIndex: 6, highIndex: 7.
lowIndex: 7, middleIndex: 7, highIndex: 7.
Adding element 13 after the position 7.
lowIndex: 0, middleIndex: 4, highIndex: 8.
lowIndex: 5, middleIndex: 6, highIndex: 8.
lowIndex: 7, middleIndex: 7, highIndex: 8.
lowIndex: 8, middleIndex: 8, highIndex: 8.
Adding element 15 after the position 8.
lowIndex: 0, middleIndex: 5, highIndex: 9.
lowIndex: 6, middleIndex: 7, highIndex: 9.
lowIndex: 8, middleIndex: 8, highIndex: 9.
lowIndex: 9, middleIndex: 9, highIndex: 9.
Adding element 19 after the position 9.
lowIndex: 0, middleIndex: 5, highIndex: 10.
lowIndex: 6, middleIndex: 8, highIndex: 10.
lowIndex: 9, middleIndex: 9, highIndex: 10.
lowIndex: 10, middleIndex: 10, highIndex: 10.
Adding element 21 after the position 10.
lowIndex: 0, middleIndex: 6, highIndex: 11.
lowIndex: 7, middleIndex: 9, highIndex: 11.
lowIndex: 10, middleIndex: 10, highIndex: 11.
lowIndex: 11, middleIndex: 11, highIndex: 11.
Adding element 22 after the position 11.
lowIndex: 0, middleIndex: 6, highIndex: 12.
lowIndex: 7, middleIndex: 9, highIndex: 12.
lowIndex: 10, middleIndex: 11, highIndex: 12.
lowIndex: 12, middleIndex: 12, highIndex: 12.
Adding element 25 after the position 12.
lowIndex: 0, middleIndex: 7, highIndex: 13.
lowIndex: 8, middleIndex: 10, highIndex: 13.
lowIndex: 11, middleIndex: 12, highIndex: 13.
lowIndex: 13, middleIndex: 13, highIndex: 13.
Adding element 56 after the position 13.
lowIndex: 0, middleIndex: 7, highIndex: 14.
lowIndex: 8, middleIndex: 11, highIndex: 14.
lowIndex: 12, middleIndex: 13, highIndex: 14.
lowIndex: 14, middleIndex: 14, highIndex: 14.
Adding element 78 after the position 14.
lowIndex: 0, middleIndex: 8, highIndex: 15.
lowIndex: 9, middleIndex: 12, highIndex: 15.
lowIndex: 13, middleIndex: 14, highIndex: 15.
lowIndex: 15, middleIndex: 15, highIndex: 15.
Adding element 88 after the position 15.
lowIndex: 0, middleIndex: 8, highIndex: 16.
lowIndex: 9, middleIndex: 12, highIndex: 16.
lowIndex: 9, middleIndex: 10, highIndex: 12.
lowIndex: 11, middleIndex: 11, highIndex: 12.
lowIndex: 11, middleIndex: 11, highIndex: 11.
Adding element 20 before the position 11.
lowIndex: 0, middleIndex: 9, highIndex: 17.
lowIndex: 10, middleIndex: 13, highIndex: 17.
lowIndex: 10, middleIndex: 11, highIndex: 13.
The element 20 is a duplicate at the position 11.
lowIndex: 0, middleIndex: 9, highIndex: 17.
lowIndex: 10, middleIndex: 13, highIndex: 17.
lowIndex: 10, middleIndex: 11, highIndex: 13.
lowIndex: 12, middleIndex: 12, highIndex: 13.
The element 21 is a duplicate at the position 12.
lowIndex: 0, middleIndex: 9, highIndex: 17.
lowIndex: 10, middleIndex: 13, highIndex: 17.
lowIndex: 14, middleIndex: 15, highIndex: 17.
lowIndex: 16, middleIndex: 16, highIndex: 17.
lowIndex: 16, middleIndex: 16, highIndex: 16.
Adding element 77 before the position 16.
lowIndex: 0, middleIndex: 9, highIndex: 18.
lowIndex: 10, middleIndex: 14, highIndex: 18.
lowIndex: 15, middleIndex: 16, highIndex: 18.
lowIndex: 17, middleIndex: 17, highIndex: 18.
The element 78 is a duplicate at the position 17.
lowIndex: 0, middleIndex: 9, highIndex: 18.
lowIndex: 10, middleIndex: 14, highIndex: 18.
lowIndex: 15, middleIndex: 16, highIndex: 18.
lowIndex: 17, middleIndex: 17, highIndex: 18.
lowIndex: 18, middleIndex: 18, highIndex: 18.
Adding element 79 before the position 18.
lowIndex: 0, middleIndex: 10, highIndex: 19.
lowIndex: 11, middleIndex: 15, highIndex: 19.
lowIndex: 16, middleIndex: 17, highIndex: 19.
lowIndex: 18, middleIndex: 18, highIndex: 19.
lowIndex: 19, middleIndex: 19, highIndex: 19.
Adding element 179 after the position 19.
Array Cells: (0) 0, (1) 1, (2) 2, (3) 3,
Array Cells: (4) 4, (5) 5, (6) 7, (7) 10,
Array Cells: (8) 13, (9) 15, (10) 19, (11) 20,
Array Cells: (12) 21, (13) 22, (14) 25, (15) 56,
Array Cells: (16) 77, (17) 78, (18) 79, (19) 88,
Array Cells: (20) 179,Code: Select all
/** AMX Mod X Script
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation; either version 2 of the License, or ( at
* your option ) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* ***********************************************************
*/
#include <amxmodx>
public plugin_init()
{
register_plugin( "Binary Search Insertion", "1.0", "Addons zz" );
server_print( "^n^n^n^n^n^n^n^n^n^n^n" );
new Array:array = ArrayCreate();
binaryInsertionSorted( array, 0 );
binaryInsertionSorted( array, 3 );
binaryInsertionSorted( array, 2 );
binaryInsertionSorted( array, 1 );
binaryInsertionSorted( array, 5 );
binaryInsertionSorted( array, 7 );
binaryInsertionSorted( array, 4 );
binaryInsertionSorted( array, 10 );
binaryInsertionSorted( array, 13 );
binaryInsertionSorted( array, 15 );
binaryInsertionSorted( array, 19 );
binaryInsertionSorted( array, 21 );
binaryInsertionSorted( array, 22 );
binaryInsertionSorted( array, 25 );
binaryInsertionSorted( array, 56 );
binaryInsertionSorted( array, 78 );
binaryInsertionSorted( array, 88 );
binaryInsertionSorted( array, 20 );
binaryInsertionSorted( array, 20 );
binaryInsertionSorted( array, 21 );
binaryInsertionSorted( array, 77 );
binaryInsertionSorted( array, 78 );
binaryInsertionSorted( array, 79 );
binaryInsertionSorted( array, 179 );
printDynamicArrayCells( array );
ArrayDestroy( array );
}
/**
* Insert a integer value in a sorted dynamic array, keeping the array sorted.
*
* This function has the worst case complexity O( n*log(n) ) where n is the array's size, because:
*
* 1. O( log(n) ) is the worst case complexity of the binary search performed to find the
* correct position to insert the element.
* 2. O( n ) is the worst case complexity to shift all array's elements, if the insertion
* of the element occurs at the beginning of the array.
*
* Use this algorithm is slightly faster than normal insertion and sort by the algorithm
* Quick Sort with the same complexity O( n*log(n) ) on the average case and O( n^2 )
* at the worst case.
*
* @param array a sorted Dynamic Array handler created by the constructor `ArrayCreate()`.
* @param element an integer element to insert on the array.
*/
stock binaryInsertionSorted( Array:array, element )
{
// server_print( "I AM ENTERING ON arrayInsertSorted(3) arraySize: %d, element: %d", arraySize, element );
new currentCell;
new arraySize = ArraySize( array );
new lowIndex = 0;
new highIndex = arraySize - 1;
new middleIndex = arraySize / 2;
server_print( "" );
server_print( "lowIndex: %3d, middleIndex: %3d, highIndex: %3d.", lowIndex, middleIndex, highIndex );
while( lowIndex < highIndex )
{
currentCell = ArrayGetCell( array, middleIndex );
if( element > currentCell )
{
lowIndex = middleIndex + 1;
}
else if( element < currentCell )
{
highIndex = middleIndex;
}
else
{
// The element is a duplicate at the position `middleIndex`
server_print( "" );
server_print( "The element %d is a duplicate at the position %d.", element, middleIndex );
server_print( "" );
return;
}
middleIndex = lowIndex + ( ( highIndex - lowIndex ) / 2 );
server_print( "lowIndex: %3d, middleIndex: %3d, highIndex: %3d.", lowIndex, middleIndex, highIndex );
}
server_print( "" );
// Here you add the element on the array
if( arraySize )
{
// Get the `currentCell` at the position `middleIndex`
currentCell = ArrayGetCell( array, middleIndex );
// To determinate whether to add the `element` after or before the position `middleIndex`.
if( currentCell < element )
{
server_print( "Adding element %d after the position %d.", element, middleIndex );
ArrayInsertCellAfter( array, middleIndex, element )
}
else
{
server_print( "Adding element %d before the position %d.", element, middleIndex );
ArrayInsertCellBefore( array, middleIndex, element )
}
}
else
{
server_print( "Adding element %d to the array's end.", element, middleIndex );
ArrayPushCell( array, element );
}
server_print( "" );
}
#define MAX_CELL_LENGHT 20
#define MAX_MESSAGE_LENGHT 80
stock printDynamicArrayCells( Array:array )
{
server_print( "" );
new indexString [ 8 ];
new elementString [ 8 ];
new cellString [ MAX_CELL_LENGHT ];
new cellStringsBuffer[ MAX_MESSAGE_LENGHT ];
new arraySize = ArraySize( array );
for( new index = 0; index < arraySize; index++ )
{
// Create a cellString within a trailing comma
formatex( indexString , charsmax( indexString ) , "(%d) " , index );
formatex( elementString, charsmax( elementString ), "%d, " , ArrayGetCell( array, index ) );
formatex( cellString , charsmax( cellString ) , "%7s %-9s" , indexString, elementString );
// Add a new cellString to the output buffer and flushes it when it full
announceCellString( cellString, cellStringsBuffer );
}
// Flush the last cells
flushCellStrings( cellStringsBuffer );
server_print( "" );
}
/**
* Announce cells to the server console.
*
* @param cellStringAnnounce a cell as string.
* @param cellStringsBuffer the output string to be printed.
*
* @note It does not immediately print the cell, the output occurs when the buffer is full.
*/
stock announceCellString( cellStringAnnounce[], cellStringsBuffer[] )
{
static copiedChars;
// Reset the characters counter for the output flush
if( !cellStringsBuffer[ 0 ] )
{
copiedChars = 0;
}
// Add the cellString to the buffer
copiedChars += copy( cellStringsBuffer[ copiedChars ], MAX_MESSAGE_LENGHT - 1 - copiedChars, cellStringAnnounce );
// Calculate whether to flush now or not
if( copiedChars > MAX_MESSAGE_LENGHT - MAX_CELL_LENGHT )
{
flushCellStrings( cellStringsBuffer );
}
}
/**
* Print the current buffer, if there are any cellStrings on it.
*
* @param cellStringsBuffer the formatted cellStrings list to be printed.
*/
stock flushCellStrings( cellStringsBuffer[] )
{
if( cellStringsBuffer[ 0 ] )
{
// Print the message
server_print( "%-13s%s", "Array Cells: ", cellStringsBuffer[ 0 ] );
// Clear the buffer
cellStringsBuffer[ 0 ] = '^0';
}
}