Implements a Sorted List using Insertion Sort

• Download source files - 5.42 Kb

Introduction

Insertion sort is a simple N^2 sort that is a faster choice among its class. The .NET framework already has a SortList structure that is implemented using dictionary pairs each of (key,value). Although the .NET SortList is sufficient enough and should run faster in most cases, I became fascinated to implement a different sort list based on Insertion Sort. The trick of this implementation is that when new elements are added to the sort list, it would get automatically sorted, and the sorting is only done on the newly added elements - because the original list is already sorted.

Using the code

There are three major classes for the implementation of the insertion sorted list. The first is the ComparerClass which implements IComparer. It has a public delete called compare_op. See code below:

// Delegates
// compare_op delegate
// : delegate to compare two objects of same type
    public delegate int compare_op(object A, object B);

Parameter of this delegate type is supplied to the ComparerClass constructor.

The InsertionSortedList class is the main class that contains the sorted list. Its base class is CollectionBase, but it could have been based on ArrayList.

The constructor of InsertionSortedList class takes a parameter of type IComparer and saves it to a private variable. It also initializes its enumerator.

The overloaded method Add has three different forms. See code below:

// Add a single object
public void Add(object o)
{
  List.Add(o);
  iterator.isSorted = false;
}
// Add a variable length of objects
public void Add(params object[] add_list)
{
  foreach(object o in add_list)
    List.Add(o);
  iterator.isSorted = false;
}
// Add a collection list of objects
public void Add(CollectionBase add_list)
{
  foreach(object o in add_list)
    List.Add(o);
  iterator.isSorted = false;
}

The three forms of Add can be used to add one object, an arbitrary number of objects, or a collection list of objects to the class. It will set the iterator's property isSorted to false.

The last major method is Sort(), which takes a parameter begin_index so that the sort will start from this specified position in the list.

// Insertion sort
public void Sort(int begin_index)
{
  // throw if comparer is null;
  if (comparer == null)
    throw new CompareOperatorNotSuppliedException();
  // return if begin_index >= collection length
  if (begin_index >= List.Count - 1)
    return;

  // from begin_index onward to length of list
  for (int i = begin_index; i < List.Count; i++)
  {
    object v = List[i]; // object v to be sorted
    int j = i - 1; // j is i - 1
    // while j is not zero, look for a position for v
    while (j >= 0 && comparer.Compare(List[j],v) > 0)
    {
      List[j+1] = List[j];
      j--;
    }
    List[j+1] = v; // found a position -> sort v
  }
}

The last class is the iterator class that implements IEnumerator. The point worth mention is that the Current property would determine if the list is sorted or not. If not, it would sort the list first and preserve the sorted list count.

public object Current
{
  get
  {
    // if it is not sorted, sort, then return current
    if (is_sorted == false)
    {
      parent.Sort(last_sort_pos+1);
      last_sort_pos = parent.Count-1;
    }
    return parent[counter];
  }
}

To use the InsertionSortedList class, you have to initialize it with a class that implements the IComparer interface. It will be used to do compare operations by the Sort method. In my test code, I have a line shown below to include an integer or string comparer:

// Init an insertion sorted list with an integer comparer
InsertionSortedList iC = new InsertionSortedList(
new ComparerClass(new ComparerClass.compare_op(compare_int)));

......

// Initialize a new insertion sorted list with string comparer
InsertionSortedList iC2 = new InsertionSortedList(
new ComparerClass(new ComparerClass.compare_op(compare_str)));

Then you can use the Add method to add some elements. When iterating through the list, for example, during printing to Console, the list will come as sorted.

Points of Interest

Of course, there are many ways to implement a sorted list. SortList in the .NET Framework is good enough, but some tricky stuff includes - you have to supply both a value and key pair, since it uses a dictionary based structure. You may modify the source code Sort() method to use other sorting algorithms such as quick sort, merge sort, heap sort, etc.

History

• Version 1.0 - July 12, 2005.
• Version 1.01 - July 13, 2005.