Inserting an item into a sorted list -- c#

c# : Inserting an item into a sorted list

Peter Rilling
10/7/2005 10:12:36 PM

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.

[quoted text, click to view]

Ryan Graham
10/7/2005 11:06:56 PM

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.Length-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end

tempArray = new int[this._list.Length+1];
Array.Copy(this._list, tempArray, this._list.Length);
this._list = tempArray;
this._list[this._list.Length-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.Length+1];
Array.Copy(this._list, 0, tempArray, 1, this._list.Length);
this._list = tempArray;
this._list[0] = value;

return;
}

int left = 0;
int right = this._list.Length;
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.Length+1];
Array.Copy(this._list, 0, tempArray, 0, middle);
Array.Copy(this._list, middle, tempArray, middle+1, tempArray.Length -
(middle +1));

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

gbacon NO[at]SPAM hiwaay.net
10/8/2005 12:00:00 AM

In article <kcD1f.4677$4h2.2319@newsread3.news.pas.earthlink.net>,
[quoted text, click to view]

: 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.Collections;

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

public void Insert(int value)
{
int i = InsertionPointLogarithmic(value);

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 InsertionPointLogarithmic(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 InsertionPointLinear(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()
{
AssertCountEquals(0);
}

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

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

[Test]
public void InsertIncreasing()
{
int[] seq = new int[] { 1, 2 };
InsertSequence(seq);
AssertCorrectResult(seq);
}

[Test]
public void InsertDecreasing()
{
int[] seq = new int[] { 20, 10 };
InsertSequence(seq);
AssertCorrectResult(seq);
}

[Test]
public void InsertManyAssorted()
{
int[] seq = new int[] { 70, 10, 30, 40, 20, 50 };
InsertSequence(seq);
AssertCorrectResult(seq);
}

[Test]
public void InsertWithDuplicates()
{
int[] seq = new int[] { 30, 20, 10, 10, 50, 10, 50, 20 };
InsertSequence(seq);
AssertCorrectResult(seq);
}

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

private void AssertCorrectResult(int[] input)
{
AssertCountEquals(input.Length);

Array.Sort(input);

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

private void AssertCountEquals(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

Ryan Graham
10/8/2005 9:23:47 AM

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

[quoted text, click to view]

Marcus Andrén
10/8/2005 11:10:14 AM

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.BinarySearch(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(array, newArray, spot);
newArray[spot] = value;
Array.Copy(array, spot,newArray, spot+1,array.Length - spot);
array = newArray;
}

--

Helge Jensen
10/8/2005 11:24:27 AM

[quoted text, click to view]

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:helge.jensen@slog.dk
sip:helge.jensen@slog.dk

Ryan Graham
10/8/2005 6:25:29 PM

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

[quoted text, click to view]

Ryan Graham
10/8/2005 6:30:30 PM

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(value, BinarySearch(value));

if ( this._length == this._list.Length )
this.IncrementArraySize();
}

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(int 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 IncrementArraySize()
{
int[] tempArray = new int[this._list.Length *2];

Array.Copy(this._list, tempArray, this._list.Length);

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<testIterations; i++)
list.Insert(i);

DateTime endTime = DateTime.Now;
TimeSpan timeSpan = endTime - startTime;
Debug.WriteLine(timeSpan.TotalMilliseconds);
}

[quoted text, click to view]

gbacon NO[at]SPAM hiwaay.net
10/9/2005 12:00:00 AM

In article <taU1f.282$y14.34@newsread3.news.pas.earthlink.net>,
[quoted text, click to view]

: 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) . . .

gbacon NO[at]SPAM hiwaay.net
10/9/2005 12:00:00 AM

In article <afU1f.283$y14.3@newsread3.news.pas.earthlink.net>,
[quoted text, click to view]

: 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.

Ryan Graham
10/9/2005 12:00:00 AM

Yeah, that's exactly what I've done actually. :)

[quoted text, click to view]

Got something to say? Click here to post a reply to this thread.

Don't see what you're looking for? Try a search.

View other messages about c#

View Other Months
June 2003
July 2003
August 2003
September 2003
October 2003
November 2003
December 2003
January 2004
February 2004
March 2004
April 2004
May 2004
June 2004
July 2004
August 2004
September 2004
October 2004
November 2004
December 2004
January 2005
February 2005
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008

home · blog · groups

Questions? Comments? Contact the dn