プログラミングでアイデアを具現化したい

あらゆるものを具現化するためにプログラミングを始めました。主にC#

クイックソート


独習C# 第3版より

https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif
引用元:wikipedia

再帰を使うことでクイックソートを実装することが可能となります。
クイックソートは現在利用できる汎用的なソートアルゴリズムの中で
最も優れたものと言われています。

  class Program {
        static void Main(string[] args) {
            char[] a = { '7', '6', '5', '4', '3', '2', '1' };
            int i;
            Console.WriteLine("元々の配列順");
            for (i = 0; i < a.Length; i++)
                Console.Write(a[i]);
            Console.WriteLine();

            //クイックソートする
            Quicksort.QSort(a);
            Console.WriteLine("ソート後の配列順");
            for (i = 0; i < a.Length; i++)
                Console.Write(a[i]);
            Console.WriteLine();
        }
    }
    class Quicksort {
        //クイックソートの本体を呼ぶための開始部分
        public static void QSort(char[] items) {
            qs(items, 0, items.Length - 1);
        }

        //文字配列のクイックソートの再帰呼び出しバージョン
        static void qs(char[] items,int left,int right) {
            int i, j;
            char x, y;
            i = left; j = right;
            x = items[(left + right) / 2];

            do {
                while ((items[i] < x) & (i < right)) i++;
                while ((x < items[j]) & (j > left)) j--;
                if (i <= j) {
                    y = items[i];
                    items[i] = items[j];
                    items[j] = y;
                    i++; j--;
                }
            } while (i <= j);
            if (left < j) qs(items, left, j);
            if (i < right) qs(items, i, right);
        }
    }

実行結果
f:id:tos5511:20160103161035j:plain


直近の人気記事
tos5511.hatenablog.com