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

The ELMO Principle - Part 2 - Sorting Algorithms

, 20 Dec 2007
Rate this:
Please Sign up or sign in to vote.
How to use the best algorithm for the job.

Introduction

In this segment of the ELMO principle, I’m going to cover non-recursive sorting algorithms. Some people might say, “The .NET Framework already provides us with array sorting mechanisms and the SortedList generic! Why should I care about sorting algorithms?” Simply put, that is the scope of the ELMO (Extremely Low Memory Optimization) principle! If you can build your own sorting algorithms for your objects, you can take advantage of extremely fast sorting without any additional overhead, boxing or un-boxing. But, in order to do that, you have to know what the most efficient and least efficient methods are for sorting. With sorting algorithms, there is no “one-size-fits-all” approach. Sorting algorithms are more or less effective depending on “what” and “how many” they are sorting.

Background

In this article, I’m going to cover three non-recursive sorting algorithms. Simply put, these are single functions that sort without having to call other functions recursively. The sorting algorithms I’m going to address are Bubble, Shell, and Insertion. The example code I’m going to post illustrates benchmarks of each sorting algorithm, given an integer array of 100,000 pseudorandom integers between 0 and 9 to sort in ascending order. The console application is multi-threaded, so I’m going to post the Main() function first, then detail each static method called by the threads. This is a pretty solid CPU exercise for your PC, so if you build something like this to benchmark, be sure you have a robust PC, and that you have closed all other applications before running this.

Building a Benchmark

    public static Random rand = new Random();

    public static int[] intArray;

    [STAThread]
    static void Main(string[] args)
    {
      Console.WriteLine(“Sorting Benchmark”);
      Console.WriteLine(“====================================\n\r”);

      // Fill array with random ints between 0 and 9
      intArray = new int[100000];

      for (int x = 0; x < 100000; x++)
      {
        intArray[x] = rand.Next(0, 9);
      }

      Console.WriteLine(“Preparing to sort {0} integers:\n\r”,intArray.Length);

      // Create separate threads for each sort
      ThreadStart tsBubble = new ThreadStart(BubbleSort);
      Thread tBubble = new Thread(tsBubble);

      ThreadStart tsShell = new ThreadStart(ShellSort);
      Thread tShell = new Thread(tsShell);

      ThreadStart tsInsertion = new ThreadStart(InsertionSort);
      Thread tInsertion = new Thread(tsInsertion);

      // Start the race
      tBubble.Start();
      tShell.Start();
      tInsertion.Start();

      Console.ReadLine();

    }

First Sort: The Bubble Sort

The Bubble sort is the least efficient of the three sorting algorithms listed here. The Bubble sort proceeds through the array from top to bottom, comparing an item to the one next to it. If it’s larger, it will swap it, and start over. In this way, smaller values “bubble” to the top of the array. A full pass of the array isn’t completed until the Bubble sort gets to the very end of the array without swapping a value. The code for the algorithm looks like the following:

    static void BubbleSort()
    {
      Console.WriteLine(“Bubble sort started…”);
      // Stamp start time

      DateTime dtStart = DateTime.Now;

      int i, j, x, iTemp;

      x = intArray.Length;

      for (i = (x - 1); i >= 0; i–)
      {
        for (j = 1; j <= i; j++)
        {
          if (intArray[j - 1] > intArray[j])
          {
            iTemp = intArray[j - 1];

            intArray[j - 1] = intArray[j];

            intArray[j] = iTemp;
          }
        }
      }

      // Stamp end time
      DateTime dtEnd = DateTime.Now;

      TimeSpan ts = dtEnd.Subtract(dtStart);

      Console.WriteLine(“Bubble sort completed in {0} sec {1} ms.”, 
                        ts.Seconds, ts.Milliseconds);
    }

Second Sort: The Insertion Sort

The Insertion sort is generally at least twice as efficient as the Bubble sort, and usually a better sorting algorithm to use when sorting larger amount of data than is recommended by the Shell sort. This algorithm works by inserting each item into its final place in the array. The simplest implementation (as detailed below) requires two array structures; the source and the sorted array. For large amounts of data, the Insertion sort obliterated the Bubble sort in benchmark tests.

    static void InsertionSort()
    {
      Console.WriteLine(“Insertion sort started…”);
      // Stamp start time
      DateTime dtStart = DateTime.Now;
      int i, j, x, index;
      x = intArray.Length;
      for (i = 1; i < x; i++)
      {
        index = intArray[i];
        j = i;

        while ((j > 0) && (intArray[j - 1] > index))
        {
          intArray[j] = intArray[j - 1];
          j = j - 1;
        }
        intArray[j] = index;
      }

      // Stamp end time
      DateTime dtEnd = DateTime.Now;
      TimeSpan ts = dtEnd.Subtract(dtStart);
      Console.WriteLine(“Insertion sort completed in {0} sec {1} ms.”, 
                        ts.Seconds, ts.Milliseconds);
    }

Third Sort: The Shell Sort

Also known as a Comb sort, the Shell sort uses diminishing increments. It performs multiple passes through the array, and each time sorts equally sized sets using the Insertion sort. As the size of the set increases, the number of sets to be sorted decreases. The sets in a Shell sort are not contiguous. For example, if there are three sets, then a set is composed of every third element in the initial array. The Shell sort is supposed to be at least five times faster than a Bubble sort. In benchmarks, it performed even faster.

    static void ShellSort()
    {
      Console.WriteLine(“Shell sort started…”);

      // Stamp start time
      DateTime dtStart = DateTime.Now;
      int i, j, inc, iTemp, x;
      x = intArray.Length;
      inc = 3;
      while (inc > 0)
      {
        for (i = 0; i < x; i++)
        {
          j = i;
          iTemp = intArray[i];

          while ((j >= inc) && (intArray[j - inc] > iTemp))
          {
            intArray[j] = intArray[j - inc];
            j = j - inc;
          }
          intArray[j] = iTemp;
        }
        if (inc / 2 != 0)
        {
          inc = inc / 2;
        }
        else if (inc == 1)
        {
          inc = 0;
        }
        else
        {
          inc = 1;
        }
      }

      // Stamp end time
      DateTime dtEnd = DateTime.Now;
      TimeSpan ts = dtEnd.Subtract(dtStart);
      Console.WriteLine(“Shell Sort completed in {0} sec {1} ms.”, 
                        ts.Seconds, ts.Milliseconds);
    }

Conclusion

I’ve detailed three extremely useful sorting algorithms for integers. These can be applied rather easily to a string array as well, but I’ll leave you guys to that implementation. When we run the above code as a console application, we get the following benchmark data (for 100,000 records) output to the Console (note, benchmarks will vary based on the system – this particular system is a dual processor 3.0 GHz with 3.5 GB of RAM, running Windows Server 2003):

Sorting Benchmark
====================================

Preparing to sort 100000 integers:

Bubble sort started…
Shell sort started…
Insertion sort started…
Shell Sort completed in 2 sec 453 ms.
Insertion sort completed in 3 sec 234 ms.
Bubble sort completed in 41 sec 764 ms.

Thanks and Credit

I'd like to extend thanks to Public Joe's information base and examples regarding sorting algorithms.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

UsualDosage
Architect
United States United States
I have been an ASP.NET/C# Programmer/Software Architect for about 10 years, specializing in web architecture, user interface, and user experience. I formerly wrote business applications for mortgage banking front-ends in C++ before switching to the .NET Framework many years ago, and I've never looked back. I'm an evangelist of HTML5 and web standards, and spend the majority of my time working on front end design, performance and scale.

My primary website is located at http://www.usualdosage.com

Comments and Discussions

 
GeneralI like the introduction PinmemberFredrik K29-Jan-08 2:00 
GeneralRe: I like the introduction PinmemberUsualDosage29-Jan-08 10:29 
GeneralRe: I like the introduction PinmemberFredrik K29-Jan-08 20:45 
GeneralHeapsort Pinmemberwtwhite2-Jan-08 17:12 
GeneralRe: Heapsort PinmemberUsualDosage29-Jan-08 10:30 
QuestionQuicksort PinmemberGurliGebis20-Dec-07 23:29 
GeneralRe: Quicksort PinmemberUsualDosage21-Dec-07 15:48 
GeneralRe: Quicksort PinmemberClevedon_Peanut27-Dec-07 1:10 
GeneralRe: Quicksort PinmemberUsualDosage27-Dec-07 10:49 
GeneralRe: Quicksort PinmemberUsualDosage7-Jan-08 16:42 
GeneralRe: Quicksort PinmemberPete Goodsall9-Jan-08 15:07 
GeneralRe: Quicksort PinmemberUsualDosage28-Jan-08 7:50 
GeneralRe: Quicksort PinmemberWarrick Procter28-Jan-08 8:53 
GeneralRe: Quicksort PinmemberPete Goodsall28-Jan-08 11:43 
GeneralRe: Quicksort PinmemberPete Goodsall28-Jan-08 11:59 
GeneralRe: Quicksort PinmemberUsualDosage28-Jan-08 14:21 
GeneralSeveral mistakes PinmemberRobert Rohde20-Dec-07 20:07 
GeneralRe: Several mistakes PinmemberUsualDosage21-Dec-07 15:46 
GeneralRe: Several mistakes PinmemberSunnanbo26-Dec-07 10:38 
GeneralRe: Several mistakes PinmemberUsualDosage27-Dec-07 10:53 

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 | Mobile
Web04 | 2.8.140827.1 | Last Updated 20 Dec 2007
Article Copyright 2007 by UsualDosage
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid