C# 정렬 알고리즘 - 퀵정렬(Quick sort)

• 퀵정렬(Quick sort)이란?

퀵정렬은 피봇을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.

 

1. 분할 정복 알고리즘

2. 일반적으로 빠른 알고리즘

 

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

namespace quicksort
{
    class Program
    {

        static int[] data = { 25, 15, 60, 45, 10, 20, 5, 30 };
        static void Main(string[] args)
        {
            Console.WriteLine("퀵정렬");

            Console.Write("시작값 : ");

            for(int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i].ToString() + ", ");
            }

            Console.WriteLine();

            SortQuick(0, data.Length - 1);

            Console.Write("정렬값 : ");

            for(int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i].ToString() + ", ");
            }

            Console.WriteLine();
        }
        static void SortQuick(int nFirst, int nLast)
        {
            if(nFirst < nLast)
            {
                int pivotIndex = FuncPartition(nFirst, nLast);

                //분할 정복
                SortQuick(nFirst, pivotIndex - 1);
                SortQuick(pivotIndex + 1, nLast);
            }
        }

        static int FuncPartition(int nFirst, int nLast)
        {
            int nLow, nHigh, nPivot;

            //양의 값 여기에서는 마지막 값
            nPivot = data[nLast];

            nLow = nFirst;
            nHigh = nLast - 1;

            while(nLow <= nHigh)
            {
                while (data[nLow] < nPivot)
                    nLow++;

                while (data[nHigh] > nPivot)
                    nHigh--;

                if(nLow <= nHigh)
                {
                    Swap(data, nLow, nHigh);
                }
            }

            Swap(data, nLow, nLast);

            return nLow;
        }

        static void Swap(int[] nArrData, int nValue1, int nValue2)
        {
            int nTemp = nArrData[nValue1];
            nArrData[nValue1] = nArrData[nValue2];
            nArrData[nValue2] = nTemp;
        }
    }
}

 

 

• 퀵정렬의 특징

- 속도가 빠르다

- 정렬된 리스트에 대해서는 수행시간이 더 오래 걸린다.