Inserting an item into a sorted list

R

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.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;
}
 
P

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 said:
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;
}
Click to expand...
 
M

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.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;
}
 
R

Ryan Graham

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

Helge Jensen

Ryan said:
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.
Click to expand...

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".
 
G

Greg Bacon

: 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 = 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 > value)
break;

return i;
}

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

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, list, "bad value at index " + i);
}

private void AssertCountEquals(int expected)
{
Assert.AreEqual(expected, list.Count, "bad Count");
}
}
}
 
R

Ryan Graham

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

Greg Bacon said:
: 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 = 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 > value)
break;

return i;
}

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

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, list, "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
simple. -- James Ostrowski
Click to expand...
 
R

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(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 = 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);
}


Peter Rilling said:
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 said:
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;
}
Click to expand...
Click to expand...
 
G

Greg Bacon

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

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

Greg
 
G

Greg Bacon

: 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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

How to speed up my VBA application ? 1
Populating a Temporary Array 6
How do I access a dynamically created PlaceHolder DropDownList control data items.... 4
Deleting last Listbox item 1
Controls created on one thread cannot be parented to a control on a different thread 8
Help with Arrays 3
HELP!! Why doesn't this code sort correctly? 2
Error while sorting with IComparer 2

Top