C# Introsort

February 27, 2008 – 10:22 am

Here is a C# implementation of the Introsort algorithm. Notice that the Introsort method is nearly identical to the Quicksort method. The only difference is the addition of checking for the depth limit (number of recursions — lines 51-59); when the depth limit has been reached, the Heapsort method is called to complete the sort of the remaining items of the present partition. See David Musser’s paper for an in-depth analysis of the Introsort algorithm, as well as a discussion about choosing the correct recursion depth.

This code is used to sort collections of objects of any class that implement IComparable. It is optimized for readability, not performance (if I were worried about performance I would have used the “unsafe” keyword and sorted everything using pointers), and includes functions for Quicksort, Heapsort, and Introsort, as well as some helper methods (Swap, SiftDown).

   1:  #region Copyright (c) 2008 Michael Ferguson [www.pherg.net]
   2:  /*****************************************************************************
   3:   * File:   Sorter.cs
   4:   * Author: Michael Ferguson (http://www.pherg.net)
   5:   * Date:   19 February 2008
   6:   * 
   7:   * This program is free software: you can redistribute it and/or modify it
   8:   * under the terms of the GNU General Public License as published by the Free
   9:   * Software Foundation, either version 3 of the License, or (at your option)
  10:   * any later version.
  11:   *
  12:   * This program is distributed in the hope that it will be useful, but WITHOUT
  13:   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14:   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  15:   * more details (http://www.gnu.org/licenses/gpl.txt).
  16:   ****************************************************************************/
  17:  #endregion
  18:   
  19:  using System;
  20:  using System.Collections.Generic;
  21:   
  22:  namespace Pherg
  23:  {
  24:    class Sorter<T> where T:IComparable
  25:    {
  26:      public Sorter ()
  27:      {
  28:      }
  29:   
  30:      public void Introsort (T[] array, int left, int right, int depthLimit)
  31:      {
  32:        if (left >= right)
  33:        {
  34:          // done sorting
  35:          return;
  36:        }
  37:        else if (left == right - 1)
  38:        {
  39:          // two element list
  40:          if (array[left].CompareTo(array[right]) > 0)
  41:          {
  42:            // left is greater than the right — swap them
  43:            Swap(array, left, right);
  44:          }
  45:   
  46:          // done sorting
  47:          return;
  48:        }
  49:        else if (depthLimit == 0)
  50:        {
  51:          // depth limit has reached maximum
  52:          Heapsort(array, left, right);
  53:          return;
  54:        }
  55:   
  56:        // decrement depth limit
  57:        depthLimit -= 1;
  58:   
  59:        // since this method is recursive avoid placing these variables on the
  60:        //   stack until the last moment
  61:        int i = left;
  62:        int k = right;
  63:   
  64:        // choose a pivot and move it to the end of the list
  65:        int pivotIndex = (left + right) >> 1; // (left + right) / 2
  66:        T pivot = array[pivotIndex];
  67:        array[pivotIndex] = array[right];
  68:        array[right] = pivot;
  69:   
  70:        while (i < k)
  71:        {
  72:          // move the i index to the k until something is found that is
  73:          //  greater than the pivot
  74:          while ((array[i].CompareTo(pivot) <= 0) && (i < k))
  75:          {
  76:            i++;
  77:          }
  78:   
  79:          // move the k index to the i until something is found that is
  80:          //  less than the pivot
  81:          while ((pivot.CompareTo(array[k]) <= 0) && (i < k))
  82:          {
  83:            k -= 1;
  84:          }
  85:   
  86:          if (i < k)
  87:          {
  88:            // swap i and k
  89:            Swap(array, i, k);
  90:          }
  91:        }
  92:   
  93:        // put the pivot back
  94:        array[right] = array[k];
  95:        array[k] = pivot;
  96:   
  97:        // sort the left side
  98:        Introsort(array, left, i - 1, depthLimit);
  99:   
 100:        // sort the right side
 101:        Introsort(array, k + 1, right, depthLimit);
 102:   
 103:      }
 104:   
 105:      public void Quicksort (T[] array, int left, int right)
 106:      {
 107:        if (left >= right)
 108:        {
 109:          // done sorting
 110:          return;
 111:        }
 112:        else if (left == right - 1)
 113:        {
 114:          // two element list
 115:          if (array[left].CompareTo(array[right]) > 0)
 116:          {
 117:            // left is greater than the right — swap them
 118:            Swap(array, left, right);
 119:          }
 120:   
 121:          // done sorting
 122:          return;
 123:        }
 124:   
 125:        // since this method is recursive avoid placing these variables on the
 126:        //   stack until the last moment
 127:        int i = left;
 128:        int k = right;
 129:   
 130:        // choose a pivot and move it to the end of the list
 131:        int pivotIndex = (left + right) >> 1; // (left + right) / 2
 132:        T pivot = array[pivotIndex];
 133:        array[pivotIndex] = array[right];
 134:        array[right] = pivot;
 135:   
 136:        while (i < k)
 137:        {
 138:          // move the i index to the k until something is found that is
 139:          //  greater than the pivot
 140:          while ((array[i].CompareTo(pivot) <= 0) && (i < k))
 141:          {
 142:            i++;
 143:          }
 144:   
 145:          // move the k index to the i until something is found that is
 146:          //  less than the pivot
 147:          while ((pivot.CompareTo(array[k]) <= 0) && (i < k))
 148:          {
 149:            k -= 1;
 150:          }
 151:   
 152:          if (i < k)
 153:          {
 154:            // swap i and k
 155:            Swap(array, i, k);
 156:          }
 157:        }
 158:   
 159:        // put the pivot back
 160:        array[right] = array[k];
 161:        array[k] = pivot;
 162:   
 163:        // sort the left side
 164:        Quicksort(array, left, i - 1);
 165:  
 166:        // sort the right side
 167:        Quicksort(array, k + 1, right);
 168:      }
 169:   
 170:      public void Heapsort (T[] array, int start, int end)
 171:      {
 172:        // to begin, place the array in max-heap order
 173:   
 174:        // get the index in array of the last parent node
 175:        int left = start + ((end - start) >> 1);
 176:        int right = end;
 177:        int offset = start;
 178:   
 179:        //while (left >= 0)
 180:        while (left >= start)
 181:        {
 182:          // sift down the node at index left to the proper place so that all
 183:          //   nodes below the left index are in heap order
 184:          //SiftDown(array, left, array.Length - 1);
 185:          SiftDown(array, offset, left, end);
 186:          left -= 1;
 187:        }
 188:   
 189:        // all nodes should now be in max-heap order
 190:   
 191:        while (right > start)
 192:        {
 193:          // swap the maximum value of the heap with the last element of the
 194:          //   heap
 195:          Swap(array, right, start);
 196:   
 197:          // decrease the size of the heap by one so that the previous max
 198:          //   value will stay in its proper placement
 199:          right -= 1;
 200:   
 201:          // put the heap back in max-heap order
 202:          SiftDown(array, offset, start, right);
 203:        }
 204:      }
 205:   
 206:      private void SiftDown (T[] array, int offset, int start, int end)
 207:      {
 208:        int root = start;
 209:        int child;
 210:   
 211:        // keep going while the root has at least one child
 212:        while (((root - offset) * 2 + 1) <= (end - offset))
 213:        {
 214:          // get the left child
 215:          child = ((root - offset) * 2 + 1) + offset;
 216:   
 217:          // if the child has a sibling and the child’s value is less than its
 218:          //   siblings
 219:          if (child < end && array[child].CompareTo(array[child + 1]) < 0)
 220:          {
 221:            // point to the right child instead
 222:            child += 1;
 223:          }
 224:          if (array[root].CompareTo(array[child]) < 0)
 225:          {
 226:            // out of max-heap order
 227:            Swap(array, root, child);
 228:   
 229:            // repeat to continue sifting down the child
 230:            root = child;
 231:          }
 232:          else
 233:          {
 234:            // all sifted
 235:            break;
 236:          }
 237:        }
 238:      }
 239:   
 240:      private void Swap (T[] array, int i, int k)
 241:      {
 242:        T swap = array[i];
 243:        array[i] = array[k];
 244:        array[k] = swap;
 245:      }
 246:    }
 247:  }

Posted in C#, Programming | 1 Comment »

C# Heapsort

February 15, 2008 – 8:01 am

This is a simple implementation of the Heapsort algorithm in C#. It is a max-heap implementation, meaning that it builds the heap from the bottom up by sifting down the maximum element; this is opposed to the min-heap implementation that builds the heap top-down by sifting upward. Also, this method is a member of the Sorting class that I will present later, and the generic class T is defined in this context as any class that implements IComparable.

   1:  public void Heapsort (T[] array, int start, int end)
   2:  {
   3:    // to begin, place the array in max-heap order
   4:   
   5:    // get the index in array of the last parent node
   6:    int left = start + ((end - start) >> 1);
   7:    int right = end;
   8:    int offset = start;
   9:   
  10:    //while (left >= 0)
  11:    while (left >= start)
  12:    {
  13:      // sift down the node at index left to the proper place so that all
  14:      //   nodes below the left index are in heap order
  15:      //SiftDown(array, left, array.Length - 1);
  16:      SiftDown(array, offset, left, end);
  17:      left -= 1;
  18:    }
  19:   
  20:    // all nodes should now be in max-heap order
  21:   
  22:    while (right > start)
  23:    {
  24:      // swap the maximum value of the heap with the last element of the
  25:      //   heap
  26:      Swap(array, right, start);
  27:   
  28:      // decrease the size of the heap by one so that the previous max
  29:      //   value will stay in its proper placement
  30:      right -= 1;
  31:   
  32:      // put the heap back in max-heap order
  33:      SiftDown(array, offset, start, right);
  34:    }
  35:  }
  36:   
  37:  private void SiftDown (T[] array, int offset, int start, int end)
  38:  {
  39:    int root = start;
  40:    int child;
  41:   
  42:    // keep going while the root has at least one child
  43:    while (((root - offset) * 2 + 1) <= (end - offset))
  44:    {
  45:      // get the left child
  46:      child = ((root - offset) * 2 + 1) + offset;
  47:   
  48:      // if the child has a sibling and the child’s value is less than its
  49:      //   siblings
  50:      if (child < end && array[child].CompareTo(array[child + 1]) < 0)
  51:      {
  52:        // point to the right child instead
  53:        child += 1;
  54:      }
  55:      if (array[root].CompareTo(array[child]) < 0)
  56:      {
  57:        // out of max-heap order
  58:        Swap(array, root, child);
  59:   
  60:        // repeat to continue sifting down the child
  61:        root = child;
  62:      }
  63:      else
  64:      {
  65:        // all sifted
  66:        break;
  67:      }
  68:    }
  69:  }
  70:   
  71:  private void Swap (T[] array, int i, int k)
  72:  {
  73:    T swap = array[i];
  74:    array[i] = array[k];
  75:    array[k] = swap;
  76:  }

Posted in C#, Programming | 2 Comments »

.NET Platform Invoke (P/Invoke) Sample

February 12, 2008 – 10:03 am

Recently someone asked me to help them call an unmanaged C++ DLL from a C# application, whereupon I promptly pointed them to the MSDN documentation on P/Invoke. Unfortunately (as I later learned) the documentation is very descriptive if you’re trying to use a Windows DLL, but it doesn’t help you understand how to create the unmanaged C++ DLL in the first place. Here’s how you do it:

  1. In Visual C++ (I use 2008) create a new Win32 Project, and then choose “DLL” in the “Application Settings” page of the Create Project wizard that follows.
  2. If the project name I had chosen was “TestDll,” I would have a file named TestDll.cpp in my project. This is where we’ll put our functions to be called by C#. Open this file for editing.
  3. Add a function that performs the action you want. I will create a function (for demonstration purposes only) called AddNumbers that, obviously, adds two numbers and returns the result (the __declspec(dllexport) tells the C++ compiler to extern this function): 
    extern “C” __declspec(dllexport)int AddNumbers(int a, int b)
{
  return a + b;
}
  4. Compile this project.
  5. Create a C# application and extern the C++ DLL function as follows. This tells the C# compiler that this function will be available at runtime: 
    [DllImport(”TestDll.dll”)]
static extern int AddNumbers(int a, int b);
  6. Then you can just call AddNumbers from C# just as if it was another function in your C# project.

Posted in C#, Programming | No Comments »

C# Quicksort

December 10, 2007 – 8:43 pm

Here is a simple implementation of the Quicksort sorting algorithm in C#. This class uses generics so any type that implements IComparable can be sorted. This code is neither intended to be the most efficient Quicksort implementation, nor does it implement Median-of-Three and Insertion sort enhancements; it does, however, provide an easy-to-follow simple implementation of the algorithm. This will provide a solid foundation for the Introsort algorithm that will be presented later. Also, this method is a member of the Sorting class that I will present later, and the generic class T is defined in this context as any class that implements IComparable.

   1:  public void Quicksort (T[] array, int left, int right)
   2:  {
   3:    if (left >= right)
   4:    {
   5:      // done sorting
   6:      return;
   7:    }
   8:    else if (left == right - 1)
   9:    {
  10:      // two element list
  11:      if (array[left].CompareTo(array[right]) > 0)
  12:      {
  13:        // left is greater than the right — swap them
  14:        Swap(array, left, right);
  15:      }
  16:   
  17:      // done sorting
  18:      return;
  19:    }
  20:   
  21:    // since this method is recursive avoid placing these variables on the
  22:    //   stack until the last moment
  23:    int i = left;
  24:    int k = right;
  25:   
  26:    // choose a pivot and move it to the end of the list
  27:    int pivotIndex = (left + right) >> 1; // (left + right) / 2
  28:    T pivot = array[pivotIndex];
  29:    array[pivotIndex] = array[right];
  30:    array[right] = pivot;
  31:   
  32:    while (i < k)
  33:    {
  34:      // move the i index to the k until something is found that is
  35:      //  greater than the pivot
  36:      while ((array[i].CompareTo(pivot) <= 0) && (i < k))
  37:      {
  38:        i++;
  39:      }
  40:   
  41:      // move the k index to the i until something is found that is
  42:      //  less than the pivot
  43:      while ((pivot.CompareTo(array[k]) <= 0) && (i < k))
  44:      {
  45:        k–;
  46:      }
  47:   
  48:      if (i < k)
  49:      {
  50:        // swap i and k
  51:        Swap(array, i, k);
  52:      }
  53:    }
  54:   
  55:    // put the pivot back
  56:    array[right] = array[k];
  57:    array[k] = pivot;
  58:   
  59:    // sort the left side
  60:    Quicksort(array, left, i - 1);
  61:  
  62:    // sort the right side
  63:    Quicksort(array, k + 1, right);
  64:  }
  65:   
  66:  private void Swap (T[] array, int i, int k)
  67:  {
  68:    T swap = array[i];
  69:    array[i] = array[k];
  70:    array[k] = swap;
  71:  }

Posted in C#, Programming | No Comments »

Quicksort, Heapsort, and Introsort

December 5, 2007 – 10:21 am

Ever heard of the introspective sort, also known as the introsort algorithm? The Wikipedia page is lacking, but this paper by David Musser describing the algorithm describes it in all its beauty. Basically it is an algorithm that sorts a list of elements by using a combination of Quicksort (with median of 3 and insertion sort enhancements) and Heapsort; Quicksort is used until a certain number of recursions has occured, whereupon the heapsort takes over.

Over the next few days I will present C# implementations of the Quicksort, Heapsort, and Introsort algorithms. In the meantime, go read David Musser’s paper.

Posted in C#, Programming | 1 Comment »

Unbiased Shuffle Algorithm

November 29, 2007 – 3:29 pm

I have recently been fascinated by the mathematics of shuffling, or randomly reassigning values to different indices within an array of elements. Wikipedia has a good article about the Fisher-Yates shuffle, which, “properly implemented, … is unbiased, so that every permutation is equally likely.” Here is a C# implementation of the Fisher-Yates shuffle that runs in linear, or O(n), time:

private void Shuffle (ref string[] values)
{
  Random rand = new Random(); // used to generate random positive integers
  int n = values.Length;      // length of the array
  int r = 0;                  // swap index
  string swap = String.Empty; // copy of string to swap

  // iterate through each item in the array
  for (int i = 0; i < n; i++)
  {
    // get random index of an item to swap with the current item
    r = i + rand.Next(n - i);

    // swap items
    swap = values[r];
    values[r] = values[i];
    values[i] = swap;
  }
}

You’ll notice that I’m sending in the array of strings as a reference argument instead of making a copy of the array and returning a new shuffled copy as the return type (which would be extremely inefficient).

Posted in C#, Programming | 1 Comment »

Mac OS X Time Machine with Linux Server

November 29, 2007 – 7:28 am

Time Machine was one of those features that pushed me over the edge to buy the mac. The one thing that was a little disappointing is that it only works with a locally-connected drive (by default). This behavior, however, can be changed. I used Appletalk on my Linux box, but I’ve heard of people using Samba (SMB) and NFS. Here’s how to set it up using Appletalk:

  1. Install netatalk with ssh enabled on your Linux box (instructions for doing this on Ubuntu are found here).
  2. Create a new directory to use as your Time Machine vault.
    sudo mkdir /var/timemachine
  3. Edit /etc/netatalk/AppleVolumes.default to add your AFP network drive (man page for this file is found at this link). At the bottom you will find the entries that define the Appletalk mount point and the “friendly name”. Add the following line at the end of the file to “mount” your new timemachine directory:
    /var/timemachine/ "Time Machine"
  4. Now, back on the Mac, select Finder’s “Go->Connect To Server” menu option. Enter the Appletalk address of your Linux box. For example, if my Linux box was at IP address 192.168.1.2, I would use this connection string:
    afp://192.168.1.2
    If it prompts you for a username and password, use one that has read and write access to the /var/timemachine/ directory. I have found it easiest to just add a user to Linux that matches the username/password of a user on the Mac.
  5. Select “Time Machine” as the drive to mount.
  6. You need to tell Time Machine that it’s OK to use network drives for a backup volume by executing the following from a Mac Terminal shell:
    defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1
  7. Open Time Machine, select your new “Time Machine” network drive, and off you go.

Posted in Leopard, Ubuntu | 6 Comments »

Pherg.net is proudly powered by WordPress Entries (RSS) and Comments (RSS). Theme by Bob