'sort'에 해당되는 글 1건

  1. 2008.12.26 [Article]Bubble Sort, Comb Sort Sample in C# 4
C# & VB.NET2008. 12. 26. 22:22

 

* 아래 덧글에서 보실 수 있듯이, 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했을 때 결과는 이렇습니다.

BubblevsComb

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

 

Tistory 태그: ,,,
Posted by kkongchi