[Article]Bubble Sort vs Comb Sort vs Quick Sort 성능 비교

지난 번 Comb Sort를 소개했던 포스팅에서 말씀 드렸듯이, Bubble Sort, Comb Sort, 그리고 닷넷의 기본 소팅 알고리즘인 Quick Sort의 성능을 비교해보았습니다.

테스트 소스는 지난 번 소스에 Quick Sort를 호출하는 부분을 추가한 것 뿐입니다. 그리고 Quick Sort도 따로 구현한 것이 아니라 닷넷의 System.Array.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[] QuickUnsorted = new string[dataCount];             string[] BubbleSorted = new string[dataCount];             string[] CombSorted = new string[dataCount];             string[] QuickSorted = new string[dataCount];             Random RandObj = new Random();             for (int idx = 0; idx < dataCount; idx++)             {                 BubbleUnsorted[idx] = RandObj.Next().ToString();                 CombUnsorted[idx] = RandObj.Next().ToString();                 QuickUnsorted[idx] = RandObj.Next().ToString();             }             BubbleSorted = BubbleSort(BubbleUnsorted);             CombSorted = CombSort(CombUnsorted);             QuickSorted = QuickSort(QuickUnsorted);         }         public static string[] QuickSort(string[] unsorted)         {             long begin = System.DateTime.Now.Ticks;                          System.Array.Sort(unsorted);             long end = System.DateTime.Now.Ticks;             long duration = (end - begin)/10000;             Console.WriteLine("Quick Sort Data Count " + Convert.ToString(unsorted.Length) + " " + duration.ToString() + " milliseconds elapsed");             return unsorted;         }         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

 

배열의 개수를 파라미터로 넘길 수 있도록 코딩 했습니다. 그래서 테스트는 10개, 100개, 1000개 이렇게 10배씩 늘려나가는 방식으로 진행했고, 3번 해서 그 평균을 구했습니다. 결과는 이렇습니다. (단위는 millisecond 즉, 100분의 1초입니다)

	Bubble Sort	Comb Sort	Quick Sort
10	5	0	2
100	11	1	2
1000	804	18	5
10000	83904	282	42

확실히 Bubble Sort는 매우 매우 느립니다. ^^;; 그리고 Comb Sort는 100개 이하에서는 오히려 Quick Sort보다도 빠른데, 1000개 정도부터는 Quick Sort의 상대가 되질 않네요.

그래서 따로 Comb Sort 와 Quick Sort 만을 따로 비교를 해보았습니다. 이 두 가지 Sorting은 100000개와 1000000개도 테스트할 수 있었습니다. (Bubble Sort로는 도저히 이 숫자는 할 수가 없더군요)

 

	Comb Sort	Quick Sort
10	0	2
100	1	2
1000	18	5
10000	282	42
100000	3831	526
1000000	49382	6418

그래도 빠르다고 생각했던 Comb Sort도 100000개 이상부터는 Quick Sort와 비교가 불가능한 성능을 보여줍니다. 정말 Quick Sort가 짱 이네요 ^^

 

Quick Sort에 대해서 자세히 알고 싶은 분들은 Wikipedia의 Quick Sort 항목을 참조하시길 바랍니다. 오른 편에 있는 그림이 정말 Quick Sort의 모든 것을 보여주네요.

그리고 Reflector로 당연히 닷넷의 소스도 확인할 수가 있습니다. 아래 그림과 소스처럼 말이죠. ^^

internal SorterObjectArray(object[] keys, object[] items, IComparer comparer) {     if (comparer == null)     {         comparer = Comparer.Default;     }     this.keys = keys;     this.items = items;     this.comparer = comparer; } internal void SwapIfGreaterWithItems(int a, int b) {     if (a != b)     {         try         {             if (this.comparer.Compare(this.keys[a], this.keys[b]) > 0)             {                 object obj2 = this.keys[a];                 this.keys[a] = this.keys[b];                 this.keys[b] = obj2;                 if (this.items != null)                 {                     object obj3 = this.items[a];                     this.items[a] = this.items[b];                     this.items[b] = obj3;                 }             }         }         catch (IndexOutOfRangeException)         {             throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", new object[] { this.keys[b], this.keys[b].GetType().Name, this.comparer }));         }         catch (Exception exception)         {             throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), exception);         }     } } internal void QuickSort(int left, int right) {     do     {         int low = left;         int hi = right;         int median = Array.GetMedian(low, hi);         this.SwapIfGreaterWithItems(low, median);         this.SwapIfGreaterWithItems(low, hi);         this.SwapIfGreaterWithItems(median, hi);         object y = this.keys[median];         do         {             try             {                 while (this.comparer.Compare(this.keys[low], y) < 0)                 {                     low++;                 }                 while (this.comparer.Compare(y, this.keys[hi]) < 0)                 {                     hi--;                 }             }             catch (IndexOutOfRangeException)             {                 throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", new object[] { y, y.GetType().Name, this.comparer }));             }             catch (Exception exception)             {                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), exception);             }             catch             {                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"));             }             if (low > hi)             {                 break;             }             if (low < hi)             {                 object obj3 = this.keys[low];                 this.keys[low] = this.keys[hi];                 this.keys[hi] = obj3;                 if (this.items != null)                 {                     object obj4 = this.items[low];                     this.items[low] = this.items[hi];                     this.items[hi] = obj4;                 }             }             low++;             hi--;         }         while (low <= hi);         if ((hi - left) <= (right - low))         {             if (left < hi)             {                 this.QuickSort(left, hi);             }             left = low;         }         else         {             if (low < right)             {                 this.QuickSort(low, right);             }             right = hi;         }     }     while (left < right); }}

 

Tistory 태그: C#,프로그래밍,소팅 알고리즘,Bubble Sort,Comb Sort,Quick Sort