22.02.08_퀵소트

 

• 찰스 앤터니 리처드 호어가 개발
  • 불안정 정렬에 속함
  • 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속함
• 분할 정복 알고리즘의 하나로 , 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬
  • 머지소트와 달리 퀵정렬은 리스트를 비균등하게 분할

0. 방식

• 리스트 안에 있는 한 요소 선택 이것을 피벗이라고 함
• 피벗 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로
  • 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 이동
• 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트 다시 정렬
  • 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복
  • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정 반복
• 부분 리스트들이 더 이상 분할이 불가능 할 때까지 반복
  • 리스트의 크기가 0이나 1이 될때 까지 반복

1.소스코드

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

namespace QuickAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 1, 0, 2, 4, 3 };
            for (int i = 0; i < arr.Length; i++)
             Console.Write (arr[i]+ " ");
            Console.WriteLine();
            quickSort(arr, 0, arr.Length - 1);

            for (int i = 0; i < arr.Length; i++)
                Console.Write(arr[i]+" ");


        }

        public static int pivoting (int []arr, int left, int right)
        {
            int l = left+1;
            int r = right;
            int pivote = left;
            while (l<=r)
            {
                while (l <= r && arr[l] < arr[pivote]) l++;
                while (l <= r && arr[pivote] < arr[r]) r--;

                if (l < r)
                {
                    int temp1 = arr[l];
                    arr[l] = arr[r];
                    arr[r] = temp1;
                }
            }
            int temp = arr[r];
            arr[r] = arr[pivote];
            arr[pivote] = temp;
            return pivote;
        }

       public static void quickSort(int[] arr, int left, int right)
        {
            if(left<right)
            {
                var pivote = pivoting(arr, left, right);
                quickSort(arr, left, pivote - 1);
                quickSort(arr, pivote + 1, right);
            }
        }

    }
}

2.테스트코드

[Fact]
        public void QuickSortTest()
        {
            int[] arr = {5, 1, 4, 3, 2, 0};
            Quick quick = new Quick();
            quick.Sort(arr,0,arr.Length-1);

            var expectResult = new int[] { 0, 1, 2, 3, 4, 5 };

            Assert.Equal(expectResult, arr);
        }