QuickSort 구현

언제쯤 RB 트리 구현해보려나..-_- 책 진도가 안나간다.

code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/QuickSort.cs

namespace API.Util.Sort

{

    class QuickSort

    {

        public static List<T> Sort<T>(List<T> unsortList) where T : IComparable

        {

            Sort(ref unsortList, 0, unsortList.Count - 1);

            return unsortList;

        }

        private static void Swap<T>(ref List<T> unsortList, int indexA, int indexB)

        {

            var temp = unsortList[indexA];

            unsortList[indexA] = unsortList[indexB];

            unsortList[indexB] = temp;

        }

        private static List<T> Sort<T>(ref List<T> unsortList, int left, int right) where T : IComparable

        {

            var pivot = unsortList[(left + right) / 2];

            int l = left, r = right;

            while (l <= r)

            {

                while (unsortList[l].CompareTo(pivot) < 0)

                {

                    l++;

                }

                while (unsortList[r].CompareTo(pivot) > 0)

                {

                    r--;

                }

                if (l <= r)

                {

                    Swap(ref unsortList, l, r);

                    l++;

                    r--;

                }

            }

            if (left < r)

                Sort(ref unsortList, left, r);

            if (l < right)

                Sort(ref unsortList, l, right);

            return unsortList;

        }

    }

}