Inserting an item into a sorted list

[Ryan Graham]

I totally bombed this question in an interview so I'm posting my answer here
for comments and suggestions... perhaps (god help me) I'm just not that
bright, but this works and seems to be fairly efficent. The idea was simple,
insert an integer into a list that has already been sorted.

private int[] _list;
....
public void Insert(int value)
{
int[] tempArray;

// check for special cases
if (this._list == null)
{ // first item added create new array

this._list = new int[1];
this._list[0] = value;
return;
}
else if (this._list[this._list.Leng th-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end

tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, tempArray, this._list.Leng th);
this._list = tempArray;
this._list[this._list.Leng th-1] = value;

return;
}
else if (this._list[0] >= value)
{ // item to be added is less than the first
// item in the array, insert item to the beginning

tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, 0, tempArray, 1, this._list.Leng th);
this._list = tempArray;
this._list[0] = value;

return;
}

int left = 0;
int right = this._list.Leng th;
int middle = 0;
int mod = 0;

// binary search loop
while (left <= right)
{
// modify the pivot point
middle = (left + right) / 2;

if (value > this._list[middle])
{ // item is greater than the pivot point

//Debug.WriteLine (value + " > " + this._list[middle]);
mod = 1;
left = middle + 1;
}
else if (value < this._list[middle])
{ // item is less than the pivot point

//Debug.WriteLine (value + " < " + this._list[middle]);

mod = 0;
right = middle - 1;
}
else
{ // item is equal to the pivot point

//Debug.WriteLine (value + " = " + this._list[middle]);
break;
}
}

// modify the pivot point again
middle += mod;

// rebuild array to allow space for new item
tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, 0, tempArray, 0, middle);
Array.Copy(this ._list, middle, tempArray, middle+1, tempArray.Lengt h -
(middle +1));

// insert new item
this._list = tempArray;
this._list[middle] = value;
}

[Peter Rilling]

I have not read the code too closely, but here is what I see that could
improve performance slightly (depending on how the Array.Copy is
implemented).

Toward the end, you have two copy statements which copy each half of the
array leaving a gap for the new number.

One suggestion (and forgive me if I am too obsessive compulsive) is that
rather then two, it might be more efficient to make just one call to
Array.Copy to an array that is one bigger. Doing this will leave the last
element undefined. Then insert your value as the last element, then swap
the last element with the pivot value. If Array.Copy was efficient, it
would do a memory copy rather then enumerating the values (like I said, I
don't really know the implementation) .

Don't know if it would do anything but just a thought.
"Ryan Graham" <ry****@earthli nk.net> wrote in message
news:kc******** *********@newsr ead3.news.pas.e arthlink.net...

I totally bombed this question in an interview so I'm posting my answer
here
for comments and suggestions... perhaps (god help me) I'm just not that
bright, but this works and seems to be fairly efficent. The idea was
simple,
insert an integer into a list that has already been sorted.

private int[] _list;
...
public void Insert(int value)
{
int[] tempArray;

// check for special cases
if (this._list == null)
{ // first item added create new array

this._list = new int[1];
this._list[0] = value;
return;
}
else if (this._list[this._list.Leng th-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end

tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, tempArray, this._list.Leng th);
this._list = tempArray;
this._list[this._list.Leng th-1] = value;

return;
}
else if (this._list[0] >= value)
{ // item to be added is less than the first
// item in the array, insert item to the beginning

tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, 0, tempArray, 1, this._list.Leng th);
this._list = tempArray;
this._list[0] = value;

return;
}

int left = 0;
int right = this._list.Leng th;
int middle = 0;
int mod = 0;

// binary search loop
while (left <= right)
{
// modify the pivot point
middle = (left + right) / 2;

if (value > this._list[middle])
{ // item is greater than the pivot point

//Debug.WriteLine (value + " > " + this._list[middle]);
mod = 1;
left = middle + 1;
}
else if (value < this._list[middle])
{ // item is less than the pivot point

//Debug.WriteLine (value + " < " + this._list[middle]);

mod = 0;
right = middle - 1;
}
else
{ // item is equal to the pivot point

//Debug.WriteLine (value + " = " + this._list[middle]);
break;
}
}

// modify the pivot point again
middle += mod;

// rebuild array to allow space for new item
tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, 0, tempArray, 0, middle);
Array.Copy(this ._list, middle, tempArray, middle+1, tempArray.Lengt h -
(middle +1));

// insert new item
this._list = tempArray;
this._list[middle] = value;
}

[Marcus Andrén]

Here is a quite simple version. And a few comments:

* Array class contains a static binary search method.
* No need to special case first, last item. Just Array.Copy zero items
* Unless null array is needed for some reason it is easier to just
make the private array zero length at initalization. That way there is
no need to employ null checks in all methods manipulating it.

private int[] array = new int[0];

public void Insert(int value)
{
int[] newArray = new int[array.Length+1];

//Array is sorted so we can use binary search to find insert spot
int spot = Array.BinarySea rch(array, value);
//If value is not found, spot is set to the negative of the next
//higher value's index.
if (spot < 0)
spot = -spot - 1; //Set insert spot to index before larger item.

Array.Copy(arra y, newArray, spot);
newArray[spot] = value;
Array.Copy(arra y, spot,newArray, spot+1,array.Le ngth - spot);
array = newArray;
}

--
Marcus Andrén

[Ryan Graham]

I appreciate the input, just to clarify the intent was to practice my own
binary search algorithm.

"Marcus Andrén" <a@b.c> wrote in message
news:3k******** *************** *********@4ax.c om...

Here is a quite simple version. And a few comments:

* Array class contains a static binary search method.
* No need to special case first, last item. Just Array.Copy zero items
* Unless null array is needed for some reason it is easier to just
make the private array zero length at initalization. That way there is
no need to employ null checks in all methods manipulating it.

private int[] array = new int[0];

public void Insert(int value)
{
int[] newArray = new int[array.Length+1];

//Array is sorted so we can use binary search to find insert spot
int spot = Array.BinarySea rch(array, value);
//If value is not found, spot is set to the negative of the next
//higher value's index.
if (spot < 0)
spot = -spot - 1; //Set insert spot to index before larger item.

Array.Copy(arra y, newArray, spot);
newArray[spot] = value;
Array.Copy(arra y, spot,newArray, spot+1,array.Le ngth - spot);
array = newArray;
}

--
Marcus Andrén

[Helge Jensen]

Ryan Graham wrote:

I totally bombed this question in an interview so I'm posting my answer here
for comments and suggestions... perhaps (god help me) I'm just not that
bright, but this works and seems to be fairly efficent. The idea was simple,
insert an integer into a list that has already been sorted.

I think the best answer to the question is, "If this is an often-done
operation, you are using arrays for something you should use a sorted
tree's for".

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Greg Bacon]

In article <kc************ *****@newsread3 .news.pas.earth link.net>,
Ryan Graham <ry****@earthli nk.net> wrote:

: I totally bombed this question in an interview so I'm posting my
: answer here for comments and suggestions... perhaps (god help me) I'm
: just not that bright, but this works and seems to be fairly efficent.
: The idea was simple, insert an integer into a list that has already
: been sorted.

Did the question require logarithmic complexity? In pressure
situations, avoid cleverness! Assuming there was no complexity
requirement, you might have said something like, "Well, I'll start
with a linear search and then optimize later using binary search."

You may have even said, "Well, I'll start with the dead-simple approach
of copying to a one-longer array, adding the value to be inserted, and
the sorting the result." Then you could talk about the piggish
complexity, which you could improve by going to linear or binary
search, and also the inefficient allocation strategy, which you could
mitigate by doubling the capacity -- distinct from the length -- when
you run out of room.

Showing that you are aware of clever solutions but move first to a
correct result and then refine for performance sends a very good signal
in a job interview.

Below is an implementation, complete with unit tests.

Enjoy,
Greg

// SortedList.cs
using System;
using System.Collecti ons;

namespace MyCollections
{
public class SortedIntList
{
private int[] a = new int[0];

public void Insert(int value)
{
int i = InsertionPointL ogarithmic(valu e);

int[] anext = new int[a.Length + 1];

Array.Copy(a, 0, anext, 0, i);
anext[i] = value;
Array.Copy(a, i, anext, i + 1, a.Length - i);

a = anext;
}

private int InsertionPointL ogarithmic(int value)
{
int l = 0;
int r = a.Length - 1;

while (l <= r)
{
int m = (l + r) / 2;

if (value < a[m])
r = m - 1;
else
l = m + 1;
}

return l;
}

private int InsertionPointL inear(int value)
{
int i;
for (i = 0; i < a.Length; i++)
if (a[i] > value)
break;

return i;
}

public int this[int i]
{
get { return a[i]; }
}

public int Count
{
get { return a.Length; }
}
}
}

// InsertTest.cs
using System;

using MyCollections;

using NUnit.Framework ;

namespace SortedListTests
{
[TestFixture]
public class InsertTest
{
SortedIntList list = new SortedIntList() ;

[SetUp]
public void CreateList()
{
list = new SortedIntList() ;
}

[Test]
public void StartEmpty()
{
AssertCountEqua ls(0);
}

[Test]
public void IntoEmptyList()
{
list.Insert(3);

AssertCountEqua ls(1);
Assert.AreEqual (3, list[0], "bogus value");
}

[Test]
public void InsertIncreasin g()
{
int[] seq = new int[] { 1, 2 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

[Test]
public void InsertDecreasin g()
{
int[] seq = new int[] { 20, 10 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

[Test]
public void InsertManyAssor ted()
{
int[] seq = new int[] { 70, 10, 30, 40, 20, 50 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

[Test]
public void InsertWithDupli cates()
{
int[] seq = new int[] { 30, 20, 10, 10, 50, 10, 50, 20 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

private void InsertSequence( int[] values)
{
foreach (int value in values)
list.Insert(val ue);
}

private void AssertCorrectRe sult(int[] input)
{
AssertCountEqua ls(input.Length );

Array.Sort(inpu t);

for (int i = 0; i < input.Length; i++)
Assert.AreEqual (input[i], list[i], "bad value at index " + i);
}

private void AssertCountEqua ls(int expected)
{
Assert.AreEqual (expected, list.Count, "bad Count");
}
}
}
--
Freedom means that when you wake up in the morning, your life, liberty and
property are yours to do with them what you will. Of course, that means that
no one else's life, liberty, or property is yours. That's freedom. It's real
simple. -- James Ostrowski

[Ryan Graham]

Thank you! This is exactly the kind of response I was looking for. :)

"Greg Bacon" <gb****@hiwaay. net> wrote in message
news:11******** *****@corp.supe rnews.com...

In article <kc************ *****@newsread3 .news.pas.earth link.net>,
Ryan Graham <ry****@earthli nk.net> wrote:

: I totally bombed this question in an interview so I'm posting my
: answer here for comments and suggestions... perhaps (god help me) I'm
: just not that bright, but this works and seems to be fairly efficent.
: The idea was simple, insert an integer into a list that has already
: been sorted.

Did the question require logarithmic complexity? In pressure
situations, avoid cleverness! Assuming there was no complexity
requirement, you might have said something like, "Well, I'll start
with a linear search and then optimize later using binary search."

You may have even said, "Well, I'll start with the dead-simple approach
of copying to a one-longer array, adding the value to be inserted, and
the sorting the result." Then you could talk about the piggish
complexity, which you could improve by going to linear or binary
search, and also the inefficient allocation strategy, which you could
mitigate by doubling the capacity -- distinct from the length -- when
you run out of room.

Showing that you are aware of clever solutions but move first to a
correct result and then refine for performance sends a very good signal
in a job interview.

Below is an implementation, complete with unit tests.

Enjoy,
Greg

// SortedList.cs
using System;
using System.Collecti ons;

namespace MyCollections
{
public class SortedIntList
{
private int[] a = new int[0];

public void Insert(int value)
{
int i = InsertionPointL ogarithmic(valu e);

int[] anext = new int[a.Length + 1];

Array.Copy(a, 0, anext, 0, i);
anext[i] = value;
Array.Copy(a, i, anext, i + 1, a.Length - i);

a = anext;
}

private int InsertionPointL ogarithmic(int value)
{
int l = 0;
int r = a.Length - 1;

while (l <= r)
{
int m = (l + r) / 2;

if (value < a[m])
r = m - 1;
else
l = m + 1;
}

return l;
}

private int InsertionPointL inear(int value)
{
int i;
for (i = 0; i < a.Length; i++)
if (a[i] > value)
break;

return i;
}

public int this[int i]
{
get { return a[i]; }
}

public int Count
{
get { return a.Length; }
}
}
}

// InsertTest.cs
using System;

using MyCollections;

using NUnit.Framework ;

namespace SortedListTests
{
[TestFixture]
public class InsertTest
{
SortedIntList list = new SortedIntList() ;

[SetUp]
public void CreateList()
{
list = new SortedIntList() ;
}

[Test]
public void StartEmpty()
{
AssertCountEqua ls(0);
}

[Test]
public void IntoEmptyList()
{
list.Insert(3);

AssertCountEqua ls(1);
Assert.AreEqual (3, list[0], "bogus value");
}

[Test]
public void InsertIncreasin g()
{
int[] seq = new int[] { 1, 2 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

[Test]
public void InsertDecreasin g()
{
int[] seq = new int[] { 20, 10 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

[Test]
public void InsertManyAssor ted()
{
int[] seq = new int[] { 70, 10, 30, 40, 20, 50 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

[Test]
public void InsertWithDupli cates()
{
int[] seq = new int[] { 30, 20, 10, 10, 50, 10, 50, 20 };
InsertSequence( seq);
AssertCorrectRe sult(seq);
}

private void InsertSequence( int[] values)
{
foreach (int value in values)
list.Insert(val ue);
}

private void AssertCorrectRe sult(int[] input)
{
AssertCountEqua ls(input.Length );

Array.Sort(inpu t);

for (int i = 0; i < input.Length; i++)
Assert.AreEqual (input[i], list[i], "bad value at index " + i);
}

private void AssertCountEqua ls(int expected)
{
Assert.AreEqual (expected, list.Count, "bad Count");
}
}
}
--
Freedom means that when you wake up in the morning, your life, liberty and
property are yours to do with them what you will. Of course, that means
that
no one else's life, liberty, or property is yours. That's freedom. It's
real
simple. -- James Ostrowski

[Ryan Graham]

After reviewing suggestions from this list and others I came up with the
following last night... further comments and suggestions greatly
appreciated.

I've added the test method down at the bottom for reference.

new method (in milliseconds)
0 10,000 calls to List.Insert()
0 15,000 calls to List.Insert()
0 20,000 calls to List.Insert()
15.625 50,000 calls to List.Insert()
15.625 75,000 calls to List.Insert()
15.625 100,000 calls to List.Insert()

old method (in milliseconds)
203.125 10,000 calls to List.Insert()
265.625 15,000 calls to List.Insert()
1062.5 25,000 calls to List.Insert()
6687.5 50,000 calls to List.Insert()
18296.875 75,000 calls to List.Insert()
35468.75 100,000 calls to List.Insert()
class List
{
private const int INITIAL_BUFFER_ SIZE = 10;
private int[] _list;

private int _length = 0;

public List()
{
this._list = new int[INITIAL_BUFFER_ SIZE];
}
public void Insert(int value)
{
this.Insert(val ue, BinarySearch(va lue));

if ( this._length == this._list.Leng th )
this.IncrementA rraySize();
}

private void Insert(int value, int index)
{
for(int i = this._length; i > index; --i)
this._list[i] = this._list[i-1];

this._list[index] = value;

this._length++;
}

private int BinarySearch(in t value)
{
int left = 0;
int right = this._length -1;
int middle = 0;

while (left <= right)
{
middle = (left + right) / 2;

if (value < this._list[middle])
{ right = middle -1; }

else if (value > this._list[middle])
{ left = middle +1; }

else if (value == this._list[middle])
{ break; }

}
return left;
}

private void IncrementArrayS ize()
{
int[] tempArray = new int[this._list.Leng th *2];

Array.Copy(this ._list, tempArray, this._list.Leng th);

this._list = tempArray;
}
}

// Test Method
static void Main(string[] args)
{
int testIterations = 100000;

List list = new List();
DateTime startTime = DateTime.Now;

for (int i=0; i<testIteration s; i++)
list.Insert(i);

DateTime endTime = DateTime.Now;
TimeSpan timeSpan = endTime - startTime;
Debug.WriteLine (timeSpan.Total Milliseconds);
}
"Peter Rilling" <pe***@nospam.r illing.net> wrote in message
news:%2******** ********@TK2MSF TNGP10.phx.gbl. ..

I have not read the code too closely, but here is what I see that could
improve performance slightly (depending on how the Array.Copy is
implemented) .

Toward the end, you have two copy statements which copy each half of the
array leaving a gap for the new number.

One suggestion (and forgive me if I am too obsessive compulsive) is that
rather then two, it might be more efficient to make just one call to
Array.Copy to an array that is one bigger. Doing this will leave the last
element undefined. Then insert your value as the last element, then swap
the last element with the pivot value. If Array.Copy was efficient, it
would do a memory copy rather then enumerating the values (like I said, I
don't really know the implementation) .

Don't know if it would do anything but just a thought.
"Ryan Graham" <ry****@earthli nk.net> wrote in message
news:kc******** *********@newsr ead3.news.pas.e arthlink.net...

I totally bombed this question in an interview so I'm posting my answer
here
for comments and suggestions... perhaps (god help me) I'm just not that
bright, but this works and seems to be fairly efficent. The idea was
simple,
insert an integer into a list that has already been sorted.

private int[] _list;
...
public void Insert(int value)
{
int[] tempArray;

// check for special cases
if (this._list == null)
{ // first item added create new array

this._list = new int[1];
this._list[0] = value;
return;
}
else if (this._list[this._list.Leng th-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end

tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, tempArray, this._list.Leng th);
this._list = tempArray;
this._list[this._list.Leng th-1] = value;

return;
}
else if (this._list[0] >= value)
{ // item to be added is less than the first
// item in the array, insert item to the beginning

tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, 0, tempArray, 1, this._list.Leng th);
this._list = tempArray;
this._list[0] = value;

return;
}

int left = 0;
int right = this._list.Leng th;
int middle = 0;
int mod = 0;

// binary search loop
while (left <= right)
{
// modify the pivot point
middle = (left + right) / 2;

if (value > this._list[middle])
{ // item is greater than the pivot point

//Debug.WriteLine (value + " > " + this._list[middle]);
mod = 1;
left = middle + 1;
}
else if (value < this._list[middle])
{ // item is less than the pivot point

//Debug.WriteLine (value + " < " + this._list[middle]);

mod = 0;
right = middle - 1;
}
else
{ // item is equal to the pivot point

//Debug.WriteLine (value + " = " + this._list[middle]);
break;
}
}

// modify the pivot point again
middle += mod;

// rebuild array to allow space for new item
tempArray = new int[this._list.Leng th+1];
Array.Copy(this ._list, 0, tempArray, 0, middle);
Array.Copy(this ._list, middle, tempArray, middle+1, tempArray.Lengt h -
(middle +1));

// insert new item
this._list = tempArray;
this._list[middle] = value;
}

[Greg Bacon]

In article <ta************ **@newsread3.ne ws.pas.earthlin k.net>,
Ryan Graham <ry****@earthli nk.net> wrote:

: Thank you! This is exactly the kind of response I was looking for. :)

You're welcome. I'm glad to help.

Greg
--
Certainly, an infant under a year is too young to be stimulated by
seeing his mother undressed (unless he's a breastfeeder) . . .
-- "What To Expect The First Year" on parental nudity

[Greg Bacon]

In article <af************ *@newsread3.new s.pas.earthlink .net>,
Ryan Graham <ry****@earthli nk.net> wrote:

: After reviewing suggestions from this list and others I came up with
: the following last night... further comments and suggestions greatly
: appreciated.
:
: I've added the test method down at the bottom for reference.

If you anticipate the lists getting large, the allocation strategy
is inefficient. When you run out of room, you should double the
length of the array instead of going back for just one more. That
does mean, however, that you'll have to track length and capacity
separately.

Greg
--
The maxim of buying nothing without the money in our pockets to pay for
it would make of our country one of the happiest on earth.
-- Thomas Jefferson