Home Tutorials Forums Articles Blogs Movies Library Employment Press

Go Back   ActionScript.org Forums > ActionScript Forums Group > ActionScript 3.0

Reply
 
Thread Tools Rate Thread Display Modes
Old 06-24-2012, 12:42 AM   #1
midnightgreen
Member
 
Join Date: Jun 2009
Location: UK
Posts: 94
Default Insert Number into a sequence

I am looking for ideas to write a function that can insert an arbitary number into an arbitary sequence of numbers in an array, so that the result is in an ascending order.

ActionScript Code:
var _objects:Vector.<int>; = Vector.<int>([ 1, 2, 4, 6, 7 ]); insertNum(5); // i want this: 1, 2, 4, 5, 6, 7

- I first thought of looping through the array and inserting the number after the first number that it is larger, but that would result in:
1, 2, 5, 4, 6, 7, where the 5 precedes 4. Similarly if I loop backwards, and I have the number 3 for example, then the result could be 1, 2, 5, 3, 6, 7

NOTE: Using sort, or sortOn() is NOT a possibility (as it is a simplified example, in the real case these numbers would be properties on a vector array of Objects)

PS: the array can only receive new elements using this method, so it will always be sorted, although it may have gaps

Last edited by midnightgreen; 06-24-2012 at 10:05 AM.
midnightgreen is offline   Reply With Quote
Old 06-24-2012, 12:58 AM   #2
[afz]snickelfitz
Senior Member
 
[afz]snickelfitz's Avatar
 
Join Date: Dec 2011
Location: Tucson, AZ
Posts: 2,332
Default

Try this:
ActionScript Code:
var arr:Vector.<int> = Vector.<int>([ 1, 2, 4, 6, 7 ]); insertNum(5); // i want this: 1, 2, 4, 5, 6, 7 function insertNum(value:int):void {     var n:int = arr.length;         for (var i:int = 0; i < n; i++)     {         if(value > arr[i] && value < arr[i+1])         {             arr.splice(i+1,0,value);             trace(arr);         }     } }
[afz]snickelfitz is offline   Reply With Quote
Old 06-24-2012, 04:09 AM   #3
newblack
dondeEstanMisPantalones?
 
newblack's Avatar
 
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355
Send a message via AIM to newblack
Default

Your examples don't make sense.

If you're asking if you can insert in less than linear time, you have to have an already sorted list and do a binary search for the insertion point, which is O(log n).
__________________
i am gibreel farishta
general relativity
jellytanks alpha redux
newblack is offline   Reply With Quote
Old 06-24-2012, 09:36 AM   #4
midnightgreen
Member
 
Join Date: Jun 2009
Location: UK
Posts: 94
Default

newblack: Yes I forgot to mention, the array can only receive new elements using this method, so it will always be sorted.

however any element can be removed, so while the list will remain sorted, there migth be gaps

Last edited by midnightgreen; 06-24-2012 at 09:49 AM.
midnightgreen is offline   Reply With Quote
Old 06-24-2012, 09:49 AM   #5
midnightgreen
Member
 
Join Date: Jun 2009
Location: UK
Posts: 94
Default

[afz]snickelfitz Yeah, actually this seems promising!
will only need to take care of the situation for arrays shorter than 2, as well as when you get to the end of the array (so i+1 would be out of range )
midnightgreen is offline   Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

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. The time now is 03:30 AM.

///
Follow actionscriptorg on Twitter

 


Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Ad Management plugin by RedTyger
Copyright 2000-2013 ActionScript.org. All Rights Reserved.
Your use of this site is subject to our Privacy Policy and Terms of Use.