노팅 - 정렬 종류와 구현(퀵정렬)

1. ToDo

- 그냥 문득 내용을 공부하면서 정리하고 싶어진 정렬 알고리즘

2. 종류

• 선택 정렬

• 삽입 정렬

• 버블 정렬

• 합병 정렬

• 퀵 정렬

3. 개념설명

• 글로 끄적..
  
  병합정렬은 안정적인 정렬이라고 표현을 하면 이번 항목에서의 퀵정렬은 불안정한 정렬이라고 볼 수 있다. 시간 복잡도는 O(n^2)의 복잡도를 가지고 재귀함수를 이용한 알고리즘이다. 기준이 되는 타겟을 Pivot이라고 부르고 Pivot을 기본으로 크면 오른쪽, 작으면 왼쪽으로 이동한다.
  

• 그림으로 쓱삭..
  
  이전과 같이 그림으로 최대한~ 간단히 설명해 보겠다.
  
  
  
  * 1, 2, 3번의 과정을 반복하고 3번의 과정이 끝난 후 Pivot은 바뀐다.

4. 코드로 투닥투닥.. (C#)

static void Main(string[] args)
{
    int[] array = { 7, 5, 4, 3, 8, 9, 10, 2, 6, 1 };

    QuickSort(array, 0, array.Count() - 1);

    Console.WriteLine();

    foreach (int item in array)
    {
        Console.Write(item);
    }
}

public static void QuickSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(array, left, right);

        if (pivot > 1) QuickSort(array, left, pivot - 1);

        if (pivot + 1 < right) QuickSort(array, pivot + 1, right);
    }
}

public static int Partition(int[] array, int left, int right)
{
    int pivot = array[left];

    while (true)
    {
        while (array[left] < pivot) left++;

        while (array[right] > pivot) right--;

        if(left < right)
        {
            int temp = array[right];
            array[right] = array[left];
            array[left] = temp;
        }
        else
        {
            return right;
        }
    }
}