퀵정렬

현재 정렬 알고리즘 중에 최고의 속도를 자랑하며 많이 쓰이는 정렬방식

Pivot을 기준으로 작은값은 앞(left), 큰 값은 뒤(Right)에 오도록 한다

재귀방식

 

시간복잡도 : O(n) = nlogn

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, 70 };

        static void Main(string[] args)
        {
            Console.WriteLine("============== 퀵정렬 ==============");
            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 first, int last)
        {
            if (first < last)
            {
                int pivotIndex = FuncPartition(first, last);

                // 분할 정복
                SortQuick(first, pivotIndex - 1);
                SortQuick(pivotIndex + 1, last);
            }
        }


        static int FuncPartition(int first, int last)
        {
            int low, high, pivot;

            pivot = data[last]; // 처음 피봇 기준은 맨 마지막 인덱스의 값

            low = first;
            high = last - 1;


            while (low <= high)
            {
                while (low <= high && data[low] < pivot) // 피봇을 기준으로 큰값이 나올때까지 반복 (왼쪽에서 오른쪽)
                    low++;

                while (low <= high && data[high] > pivot) // 피봇을 기준으로 작은값이 나올때까지 반복 (오른쪽에서 왼쪽) 
                    high--;

                if (low <= high) // 피봇을 기준으로 큰값의 인덱스가 작은값의 인덱스보다 낮다면 서로 자리를 바꿔줌
                {
                    Swap(data, low, high);
                }
            }

            Swap(data, low, last); // 마지막 인덱스의 변수와 low 인덱스의 위치를 바꿔준다

            Console.Write("정렬값(Pivot : " + pivot + ") - ");

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

            Console.WriteLine();

            return low;
        }

        static void Swap(int[] arrData, int value1, int value2)
        {
            int temp = arrData[value1];
            arrData[value1] = arrData[value2];
            arrData[value2] = temp;
        }
    }
}