* 아래 덧글에서 보실 수 있듯이, 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와 한 번 비교해보도록 하겠습니다.
이올린에 북마크하기
이올린에 추천하기'C# & VB.NET' 카테고리의 다른 글
| [Article]Bubble Sort vs Comb Sort vs Quick Sort 성능 비교 (4) | 2009/01/19 |
|---|---|
| [Article]Bubble Sort, Comb Sort Sample in C# (4) | 2008/12/26 |
| [Article].NET 1.1에서는 HttpException Class가 Serializable하지 않다. (0) | 2008/03/13 |
| [Tip]메서드에서의 기본적인 Argument Validation (0) | 2008/03/09 |
| [Tip]VB.NET, C# Escape 문자 (0) | 2007/10/17 |
| [Tip]현재 메소드의 호출자 정보를 알고 싶을 때... (4) | 2007/02/26 |
Trackback Address :: http://lazydeveloper.net/trackback/2567083
- Tracked from Lazy Developer 2009/01/19 00:26 삭제
Subject: [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..
