[Article]Bubble Sort, Comb Sort Sample in C#

 

* 아래 덧글에서 보실 수 있듯이, exedra님 지적 때문에 일부 소스와 비교 데이터가 수정되었습니다. (2008-01-14)

 

회사 솔루션 코드 중에 VB로 된 Comb Sort 코드가 있길래, C#으로 재 작성해보았습니다.

그러면서 가장 기본적인 Bubble Sort와 성능 차이가 얼마나 되나 비교도 해 봤습니다.

Comb Sort의 내용에 대해서는 Wikipedia의 Comb_sort 항목을 참조하시면 됩니다.

 

코드는 아래와 같습니다.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortingSample {     class Program     {         static void Main(string[] args)         {             int dataCount = Convert.ToInt32 (args[0]);             string[] BubbleUnsorted = new string[dataCount];             string[] CombUnsorted = new string[dataCount];             string[] BubbleSorted = new string[dataCount];             string[] CombSorted = new string[dataCount];             Random RandObj = new Random();             for (int idx = 0; idx < dataCount; idx++)             {                 BubbleUnsorted[idx] = RandObj.Next().ToString();                 CombUnsorted[idx] = RandObj.Next().ToString();             }             BubbleSorted = BubbleSort(BubbleUnsorted);             CombSorted = CombSort(CombUnsorted);         }                  public static string[] BubbleSort(string[] unsorted)         {                         bool swap;             long begin = System.DateTime.Now.Ticks;             do             {                 swap = false;                 for (int i = 1; i < unsorted.Length; i++)                 {                     if (Convert.ToInt64(unsorted[i - 1]) > Convert.ToInt64(unsorted[i]))                     {                         string tmp = unsorted[i - 1];                         unsorted[i - 1] = unsorted[i];                         unsorted[i] = tmp;                         swap = true;                     }                               }                              } while (swap);             long end = System.DateTime.Now.Ticks;             long duration = (end - begin)/10000;             Console.WriteLine("Bubble Sort Data Count " + Convert.ToString(unsorted.Length) + " " + duration.ToString() + " milliseconds elapsed");             return unsorted;         }                  public static string[] CombSort(string[] unsorted)         {             int gap = unsorted.Length;             int swap;             long begin = System.DateTime.Now.Ticks;             do             {                 if (gap > 1)                 {                                          gap = (gap * 10) / 13;                     if (gap == 9 || gap == 10)                     {                         gap = 11;                     }                 }                 swap = 0;                 for (int i = 0; i + gap <= unsorted.Length-1; i++)                 {                     if (Convert.ToInt64(unsorted[i]) > Convert.ToInt64(unsorted[i+gap]))                     {                         string tmp = unsorted[i];                         unsorted[i] = unsorted[i+gap];                         unsorted[i+gap] = tmp;                         swap = 1;                     }                                   }             } while (gap > 1 || swap == 1);             long end = System.DateTime.Now.Ticks;             long duration = (end - begin) / 10000;             Console.WriteLine("Comb Sort Data Count " + Convert.ToString(unsorted.Length) + " " + duration.ToString() + " milliseconds elapsed");             return unsorted;         }     } } Colorized by: CarlosAg.CodeColorizer

 

1000건을 Sorting했을 때 결과는 이렇습니다.

차이가 매우 크다는 것을 보실 수 있습니다. Comb Sort가 꽤 빠른 Sorting 알고리즘이라는 것을 알 수가 있습니다. 다음 번에 기회가 나면, .NET의 기본 Sort 알고리즘인 Quick Sort와 한 번 비교해보도록 하겠습니다.

 

Tistory 태그: C#,Sort,Comb Sort,Bubble Sort