Raised This Month: $12 Target: $400
 3% 

Dynamic Array's Binary Insertion Sorted


Post New Thread Reply   
 
Thread Tools Display Modes
Author Message
addons_zz
Veteran Member
Join Date: Aug 2015
Location: Dreams, zz
Old 12-21-2016 , 15:54   Dynamic Array's Binary Insertion Sorted
Reply With Quote #1

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:
Code:
    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;     }
https://github.com/alliedmodders/amxmodx/blob/e95099817b1383fe5d9c797f761017a862fa8a97/amxmodx/datastructs.h#L97-L113

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

Code:
/**  * 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 );     } }

Output example:

Code:
    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 );
HTML Code:
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,
Test Source Code:
Spoiler


References:
  1. Wikipedia - Time complexity
  2. Wikipedia - Computational complexity theory
  3. Wikipedia - Binary search algorithm
  4. Wikipedia - Quicksort
  5. A Moment of Zen - Binary Insertion Sort
  6. GeeksQuiz - Binary Insertion Sort
  7. StackOverflow - How to add elements in Binary search tree iteratively?
  8. Data Structures and Algorithms with Object-Oriented Design Patterns in C++ - Binary Insertion Sort
  9. StackExchange Computer Science - Adding elements to a sorted array
__________________
Plugin: Sublime Text - ITE , Galileo
Multi-Mod: Manager / Plugin / Server

Support me on Patreon, Ko-fi, Liberapay or Open Collective

Last edited by addons_zz; 12-22-2016 at 07:44. Reason: Fixed insertion error
addons_zz is offline
shehzad1234
BANNED
Join Date: Jan 2016
Location: https://t.me/pump_upp
Old 12-22-2016 , 02:51   Re: Dynamic Array's Binary Insertion Sorted
Reply With Quote #2

1st Comment

Good Tut bro :*
shehzad1234 is offline
Send a message via ICQ to shehzad1234 Send a message via AIM to shehzad1234 Send a message via Yahoo to shehzad1234
addons_zz
Veteran Member
Join Date: Aug 2015
Location: Dreams, zz
Old 12-22-2016 , 07:31   Re: Dynamic Array's Binary Insertion Sorted
Reply With Quote #3

Thanks, I just noticed a error on the insertion. I updated the first post within the correct code and tests.

Spoiler
__________________
Plugin: Sublime Text - ITE , Galileo
Multi-Mod: Manager / Plugin / Server

Support me on Patreon, Ko-fi, Liberapay or Open Collective

Last edited by addons_zz; 12-22-2016 at 07:35.
addons_zz is offline
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 05:27.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode