'소팅 알고리즘'에 해당되는 글 1건

  1. 2009.01.19 [Article]Bubble Sort vs Comb Sort vs Quick Sort 성능 비교 (4)
C# & VB.NET2009. 1. 19. 00:20

지난 번 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에 대해서 자세히 알고 싶은 분들은 WikipediaQuick 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);
}}

 

Posted by kkongchi

댓글을 달아 주세요

  1. 아. 흥미롭게 잘 봤습니다. 결론은 퀵소트인가요 하... 다른 특별한 조건이 필요할때 아니면 그냥 퀵소트 가야겠군요. ^^

    2009.01.20 23:40 [ ADDR : EDIT/ DEL : REPLY ]
    • 100만개에서 50초와 6초라면 게임이 안 되는 것이죠.. 닷넷에서 왜 퀵소트가 기본 소팅 알고리즘인지 확실히 납득되는 순간이었습니다. ^^;;

      2009.01.20 23:54 신고 [ ADDR : EDIT/ DEL ]
  2. 소팅 알고리즘을 얘기할 때 time complexity를 얘기하는데요, 버블 소트의 경우 O(n^2) 의 time complexity를 가집니다. 대신 quick sort는 O(nlogn)의 time complexity를 가지죠. 여기서 n은 소팅하기위한 데이타 갯수 입니다. 여러 특수한 상황에 맞춘 몇몇 알고리즘의 경우 O(n)의 time complexity를 가지기도 하지만, 범용의 sorting 알고리즘 중에서 단연 최고의 성능을 보여주는 녀석이 바로 quick sort입니다.
    참고로 merge sort도 O(nlogn)의 time complexity를 가지는데요, 실제 수행시간을 보면 오히려 quick sort보다 더 빠릅니다. 대신 space complexity가 O(n)이라 quick sort보다 메모리를 더 많이 필요로 합니다.
    대신 quick sort의 경우 median을 잘못 잡으면 (아주 재수가 없는 경우) time complexity가 O(n^2)가 될 수도 있습니다. 그래서 median을 잘 잡아야 하는데, median-of-median 혹은 median-of-3 같은 기법들이 이용됩니다.

    마지막으로 O(nlogn)의 complexity를 가지는 소팅 알고리즘들은 recursion을 이용해서 구현되는 경우가 많은데요, 이 경우 input 개수가 적으면 오히려 버블 소트나 쉘 소트보다 느릴 수도 있습니다. 그래서 보통 input이 특정 개수 이하 (10개 정도?)인 경우에는 버블소트를 이용하도록 구현하는 경우도 많습니다.

    에효~ 알고리즘 얘기만 나오면 이렇게 참지 못하고 ... ㅡ.ㅡ;; 긴 댓글 죄송합니다.

    2009.01.21 00:33 [ ADDR : EDIT/ DEL : REPLY ]
    • ㅎㅎ 긴 댓글 감사합니다. 댓글을 보니 merge sort에 대해서도 흥미가 생기네요. 그것도 한번 구현해서 비교해봐야겠습니다.^^

      2009.01.21 00:50 신고 [ ADDR : EDIT/ DEL ]