퀵 정렬 (Quick sort)

퀵 정렬은 찰스 앤터니 리처드 호어 라는 분이 1959년에 개발한 정렬 알고리즘입니다.

이름처럼 웬만한 상황에서는 빠른 알고리즘이고 많이 사용되고 있습니다.

최선 & 평균 시간복잡도는 

최악 시간복잡도는 

입니다.

퀵 소트가 동작하는 방법을 단순하게 표현한다면 다음과 같습니다. (오름차순 기준)

1. 가운데 값을 정한다 (기준점 4)

           ▼

{2 3 1 6 4 8 5 7 9}

2. 값을 기준으로 작은건 왼쪽으로 큰건 오른쪽으로 보낸다.

        ▼

{2 3 1 4 6 8 5 7 9}

3. 가운데 값을 기준으로 구역을 나누고 구역마다 다시 가운데 값을 정한다. (기준점 3,5)

   ▼             ▼

{2 3 1} 4 {6 8 5 7 9}

4. 구역마다 1~ 3번을 다시 반복한다.

      ▼    ▼

{2 1 3} 4 {5 6 8 7 9}

5. 또 다시 구역을 나눠서 나눌 구역이 없을 때 까지 반복한다...

위의 과정을 구현한 소스코드는 이런모양 (출처 : 위키백과)

void quickSort(int arr[], int left, int right)//정렬할 배열,구역의 왼쪽,구역의 오른쪽
{
      int i = left, j = right;//i=왼쪽 ,j=오른쪽
      int pivot = arr[(left + right) / 2];//기준점은 구역의 중간
      int temp;
      do 
      {
        while (arr[i] < pivot)//왼쪽이 피벗보다 (어차피)작다면 스킵
            i++;
        while (arr[j] > pivot)//오른쪽이 피벗보다 (어차피)크다면 스킵
            j--;
        if (i<= j)//위에서 걸러지지 못한건 서로 교체
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
      } while (i<= j);//왼쪽이랑 오른쪽이랑 만날때까지 반복
 
    /* 구역나눠 재귀 */
    if (left < j)//왼쪽 구역
        quickSort(arr, left, j);
 
    if (i < right)//오른쪽 구역
        quickSort(arr, i, right);
}

이 소스코드가 위에 설명한거랑 조금 달라보일 수 있는데

조금 달라보여도 자세히 보면 위 설명과 크게 다르지는 않습니다.

저 소스를 더 분석하자면... 

1. 왼쪽(i) 오른쪽(j)과 가운데 값(피벗)이 있다.

 i          ▼         j

{2 3 1 6 4 8 5 7 9}

2. i, j가 피벗을 기준으로 제대로 된 위치에 있으면 스킵 

(이상황에서는 결국 j랑 피벗이랑 같은위치)

          i▼(j)

{2 3 1 6 4 8 5 7 9}

3. 제대로 된 위치가 아니면 i랑 j의 위치를 변경

{2 3 1 4 6 8 5 7 9}

4. 왼쪽부터 j까지 , i부터 오른쪽까지 구역나눠서 반복

{2 3 1 4} {6 8 5 7 9}

그리고 퀵소트의 원리를 보여주는 헝가리 민속 탭 떈쓰~ (겁나 흥겨움)

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC