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

C# & VB.NET2008. 12. 26. 22:22

[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

'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

Posted by kkongchi

TAG Bubble Sort, c#, Comb Sort, sort

Trackback 1 Comment 4

댓글을 달아 주세요

망고

퀵소트와의 비교가 기대되는데요 ^^
2008.12.29 23:24 [ ADDR : EDIT/ DEL : REPLY ]
- kkongchi
  
  넵. 다음에 퀵소트와 비교를 한번 해보도록 하겠습니다. 방문 감사합니다. ^^
  2008.12.30 02:11 신고 [ ADDR : EDIT/ DEL ]
exedra

Comb Sort라...
자세히 읽지는 않았지만, 재밌네요.
처음 들어보는 알고리즘이라 차근차근 봐야겠습니다.

다시 보니 약간의 실수를 하셨네요.
test 데이타를 BubbleSort를 통해 이미 정렬한 후에, 정렬된 데이타를 CombSort로 보내셨네요. ^^;;
2009.01.13 02:07 [ ADDR : EDIT/ DEL : REPLY ]
- kkongchi
  
  이건 약간의 실수가 아니네요 -_-;;;; 죄송합니다. 수정해야겠는데요...ㅜ.ㅜ 지적해주셔서 감사합니다.
  2009.01.14 23:50 신고 [ ADDR : EDIT/ DEL ]