Click here to Skip to main content
Click here to Skip to main content

Implements a Sorted List using Insertion Sort

, 13 Jul 2005
Rate this:
Please Sign up or sign in to vote.
This article describes how I implemented a sorted list using insertion sort. The source code is in C#.

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Ming_Lei
Web Developer
United States United States
Live in Seattle, WA.

Comments and Discussions

 
Generalbinary search Pinmembertim51230-Nov-05 8:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.1411019.1 | Last Updated 14 Jul 2005
Article Copyright 2005 by Ming_Lei
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid