うろ覚えのクイックソートを思い出しながら書いてみた

急に思い立って、C#でクイックソートを実装してみた。

トライ

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var sample = new List<int>() { 3, 12, 4, 0, -3, 2, 8, 1, 1000, -21 };

            var result = Program.QuickSort(sample);

            foreach (var item in result)
            {
                Console.Write(item + " ");
            }
            Console.ReadKey();

        }

        private static IEnumerable<int> QuickSort(IEnumerable<int> array)
        {
            if (array.Count() == 0)
            {
                return array;
            }
            else
            {
                int border = array.First();

                var left = new List<int>();
                var right = new List<int>();

                foreach (var item in array.Skip(1))
                {
                    if (item < border)
                        left.Add(item);
                    else
                        right.Add(item);
                }

                return QuickSort(left)
                    .Concat(new List<int>() { border })
                    .Concat(QuickSort(right));
            }
        }
    }
}

LINQの部分は、もっとシンプルに性能のよいものが書けそうな気がする。まあ、とりあえずはこれで。

後で調べたところ、こんな記事を発見 => 「neue cc - C# Linqでクイックソート」。LINQを極めると、こんなスマートに書けるという例。

クイックソートは書けるべきか

定番のアルゴリズムを実装するたびに思うことがある。こうした有名なアルゴリズムは、すぐ書けるようにひと通り覚えておくべきか。それとも、いちいち覚えずとも調べて書ければそれでいい、ぐらいに考えればよいのか。
個人的には、汎用的なアルゴリズムの"デザイン"を体に染み込ませることが一番大事だと思っている。上記のクイックソートの例で言うと、これは再帰アルゴリズムの定番の書き方*1になっている。個々のアルゴリズムを覚えていてもいなくても、それらの共通の"デザイン"を体で身につけることは無駄にならないと思う。

*1:func(x) { if (停止条件を満たす) then return 0; else return x + func (x-1);} のように、再帰的定義をそのまま実装した書き方。