Commits

Anonymous committed b26f42e

Added the first version of the Comb sort in C#.

  • Participants
  • Parent commits 09d0043

Comments (0)

Files changed (4)

File 03-CombSort/CombSort-CSharp/CombSort-CSharp.csproj

+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="3.5" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProductVersion>9.0.30729</ProductVersion>
+    <SchemaVersion>2.0</SchemaVersion>
+    <ProjectGuid>{1720AE6B-C6A4-4501-A478-F4AC47FB724F}</ProjectGuid>
+    <OutputType>Exe</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>CombSort_CSharp</RootNamespace>
+    <AssemblyName>CombSort-CSharp</AssemblyName>
+    <TargetFrameworkVersion>v3.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core">
+      <RequiredTargetFramework>3.5</RequiredTargetFramework>
+    </Reference>
+    <Reference Include="System.Xml.Linq">
+      <RequiredTargetFramework>3.5</RequiredTargetFramework>
+    </Reference>
+    <Reference Include="System.Data.DataSetExtensions">
+      <RequiredTargetFramework>3.5</RequiredTargetFramework>
+    </Reference>
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Program.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+  </ItemGroup>
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>

File 03-CombSort/CombSort-CSharp/Program.cs

+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace CombSort_CSharp
+{
+
+    // Code for the Comb Sort implementation that accompanies the Comb Sort
+    // article that can be found at
+    // http://rant.blackapache.net/2008/09/14/sorting-algorithms-the-comb-sort
+    // Make sure you check out the article for details on the algorithm, the
+    // magic numbers and the optimisations.
+    class Program
+    {
+        /// <summary>
+        /// This is a "magic number" which is the recommended shrink factor
+        /// for the comb sort.
+        /// </summary>
+        private const double SHRINK_FACTOR = 1.3;
+
+        /// <summary>
+        /// Program entry point.
+        /// </summary>
+        /// <param name="args">Command line arguments.</param>
+        static void Main(string[] args)
+        {
+            int[] dataSet = new int[] { 33, 98, 74, 13, 55, 20, 77, 45, 64, 83 };
+
+            Display(dataSet);
+            CombSort(dataSet);
+            Display(dataSet);
+        }
+
+        /// <summary>
+        /// The implementation of the standard comb sort algorithm which sorts
+        /// an array of integers.
+        /// </summary>
+        /// <param name="dataSet">Reference to the dataset that is to be soroted.</param>
+        static void CombSort(int[] dataSet)
+        {
+            // start by using the length/size of the set as the gap.
+            int gap = dataSet.Length;
+
+            // loop indefinately.
+            while (true)
+            {
+                // update the gap value so that it shrinks
+                // towards 1.
+                if (gap > 1)
+                {
+                    gap = (int)((double)gap / SHRINK_FACTOR);
+                }
+
+                // do the comb sort with the current gap
+                bool swapped = false;
+                for (int i = 0; i + gap < dataSet.Length; ++i)
+                {
+                    if (dataSet[i] > dataSet[i + gap])
+                    {
+                        Swap(dataSet, i, i + gap);
+                        swapped = true;
+                    }
+                }
+
+                // if we're down to a gap of 1, and we haven't swapped
+                // anything, then we're sorted.
+                if (gap == 1 && !swapped)
+                {
+                    break;
+                }
+            }
+        }
+
+        /// <summary>
+        /// Special optimised version of the Comb Sort.
+        /// </summary>
+        /// <param name="dataSet">Data set to be sorted.</param>
+        /// <remarks>This version contains a "fix" which, when dealing
+        /// with datasets larger than 11 in size, will result in a more
+        /// optimal solution.</remarks>
+        static void CombSort11(int[] dataSet)
+        {
+            int gap = dataSet.Length;
+
+            while (true)
+            {
+                // update the gap value so that it shrinks
+                // towards 1.
+                if (gap > 1)
+                {
+                    gap = (int)((double)gap / SHRINK_FACTOR);
+                    
+                    // special case: hard code gap to 11 when
+                    // appropriate for optimal performance
+                    if (gap == 9 || gap == 10)
+                    {
+                        gap = 11;
+                    }
+                }
+
+                // do the comb sort with the current gap
+                bool swapped = false;
+                for (int i = 0; i + gap < dataSet.Length; ++i)
+                {
+                    if (dataSet[i] > dataSet[i + gap])
+                    {
+                        Swap(dataSet, i, i + gap);
+                        swapped = true;
+                    }
+                }
+
+                // if we're down to a gap of 1, and we haven't swapped
+                // anything, then we're sorted.
+                if (gap == 1 && !swapped)
+                {
+                    break;
+                }
+            }
+        }
+
+        /// <summary>
+        /// Generic helper swap method.
+        /// </summary>
+        /// <typeparam name="T">The type contained in the array.</typeparam>
+        /// <param name="dataSet">Reference to the array of type T.</param>
+        /// <param name="i">One of the indexes to swap.</param>
+        /// <param name="j">One of the indexes to swap.</param>
+        /// <remarks>Items and index i and j are swapped.</remarks>
+        static void Swap<T>(T[] dataSet, int i, int j)
+        {
+            T temp = dataSet[i];
+            dataSet[i] = dataSet[j];
+            dataSet[j] = temp;
+        }
+
+        /// <summary>
+        /// Helper display method.
+        /// </summary>
+        /// <typeparam name="T">Type to display.</typeparam>
+        /// <param name="a">Array of type T to be displayed.</param>
+        static void Display<T>(T[] a)
+        {
+            foreach (T t in a)
+            {
+                Console.Write(" " + t.ToString());
+            }
+            Console.WriteLine();
+        } 
+    }
+}

File 03-CombSort/CombSort-CSharp/Properties/AssemblyInfo.cs

+using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("CombSort-CSharp")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("")]
+[assembly: AssemblyProduct("CombSort-CSharp")]
+[assembly: AssemblyCopyright("Copyright ©  2008")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("e71e5e50-ff4c-46b0-a959-320be49b4684")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]

File 03-CombSort/CombSort.sln

+
+Microsoft Visual Studio Solution File, Format Version 10.00
+# Visual Studio 2008
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "CombSort-CSharp", "CombSort-CSharp\CombSort-CSharp.csproj", "{1720AE6B-C6A4-4501-A478-F4AC47FB724F}"
+EndProject
+Global
+	GlobalSection(SolutionConfigurationPlatforms) = preSolution
+		Debug|Any CPU = Debug|Any CPU
+		Release|Any CPU = Release|Any CPU
+	EndGlobalSection
+	GlobalSection(ProjectConfigurationPlatforms) = postSolution
+		{1720AE6B-C6A4-4501-A478-F4AC47FB724F}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{1720AE6B-C6A4-4501-A478-F4AC47FB724F}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{1720AE6B-C6A4-4501-A478-F4AC47FB724F}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{1720AE6B-C6A4-4501-A478-F4AC47FB724F}.Release|Any CPU.Build.0 = Release|Any CPU
+	EndGlobalSection
+	GlobalSection(SolutionProperties) = preSolution
+		HideSolutionNode = FALSE
+	EndGlobalSection
+EndGlobal