C언어 QuickSort 예시로 살펴보기

오늘은 C언어에서 QuickSort가 어떻게 진행이 되는지 알아보겠습니다.

예시 데이터는 간단하게 arr = [3, 1, 4, 2, 7]로 하겠습니다.

첫번째, quicksort에서 필요한 것은 left, pivot, right 값입니다. 위 배열을 기준으로 생각했을 때

left는 배열의 가장 좌측 값을 임시 저장해두기 위한 변수이고, 

right는 배열의 가장 우측 값을 임시 저장해두기 위한 변수입니다. 

(재귀호출이 되면서 값이 변할 수 있습니다.)

pivot 값은 보통 중앙값으로 많이 설정을 합니다.

그러면 초기값을 정리해보면 left = 0, right = 4, pivot = (left+right)/2 = 2 가 되겠죠?

이 상태로 시작을 했다면 left의 값을 L에 대입하고, right의 값을 R에 대입을 합니다.

현재 L = 0, R = 4, pivot = 2 입니다.

위 세 값이 가지고 있는 것은 배열의 인덱스 값이기 때문에 arr에 대응하는 값을 찾아보면

arr[L] = 3, arr[R] = 7, arr[pivot] = 4입니다.

arr = [3, 1, 4, 2, 7]

quick를 진행하기 위해서는 arr[L]이 arr[pivot]의 값보다 작다면 L 값을 1씩 증가시킵니다.

그러면 첫번째 while loop에서는 L은 2가 됩니다.

그리고 arr[R]이 arr[pivot]의 값보다 크다면 R 값을 1씩 감소시킵니다.

그러면 첫번째 while loop에서 R은 3이 됩니다.

L이 R보다 작거나 같고, 둘이 같은 값이 아니기 때문에 두 인덱스가 가리키는 값을 서로 swap하고

L은 1을 증가시키고 R은 1을 감소시킵니다.

그 결과 arr = [3, 1, 2, 4, 7]이 됩니다. L=3, R=2가 되구요. (left = 0, right = 4)

-- 첫번째 재귀호출 --

left의 값이 R보다 작기 때문에 quicksort를 재귀호출 합니다.

재귀호출 된 quicksort에서 left = 0, right = 2가 됩니다. pivot 은 1이 되겠죠?

L은 0, R은 2가 됩니다.

현재 배열 arr = [3, 1, 2, 4, 7]에서 

이전과 같이 arr[L]이 arr[pivot]의 값보다 작다면 L 값을 1씩 증가시킵니다.

그리고 arr[R]이 arr[pivot]의 값보다 크다면 R 값을 1씩 감소시킵니다.

그 결과 L은 0이 되고, R은 1이 됩니다.

이제 L과 R이 가리키고 있는 값을 서로 swap 합니다. 

그러면 이번엔 arr = [1, 3, 2, 4, 7]이 됩니다.

그리고 L = 1 R = 0이 됩니다. (left = 0, right = 2)

left = 0 의 값이 R = 0값과 같기 때문에 left와 R을 사용하는 quicksort는 호출되지 않습니다.

L = 1 의 값이 right = 2보다 작기 때문에 L과 right를 사용하는 quicksort가 재귀호출됩니다.

-- 두번째 재귀호출 --

재귀호출 된 quicksort에서 left = 1, right = 2이 됩니다. 각 값을 L = 1과 R = 2에 저장합니다.

pivot은 1이 되겠죠? (1+2)/2 = 1.5 (소수점 버림) => 1

arr = [1, 3, 2, 4, 7]

이전과 같이 arr[L]이 arr[pivot]의 값보다 작다면 L 값을 1씩 증가시킵니다.

그리고 arr[R]이 arr[pivot]의 값보다 크다면 R 값을 1씩 감소시킵니다.

그 결과 L은 1이 되고, R은 2가 됩니다.

두 개의 값을 swap 합니다. 

그 결과 배열은 이렇게 되겠네요. arr = [1, 2, 3, 4, 7]

이후 L은 2가 되고 R은 1이 됩니다. (left = 1, right = 2)

left = 1 의 값이 R = 1값과 같기 때문에 left와 R을 사용하는 quicksort는 호출되지 않습니다.

L = 2 의 값이 right = 2값과 같기 때문에 L과 right를 사용하는 quicksort가 재귀호출되지 않습니다.

-- 세번째 재귀호출 --

이미 정렬이 완료되었지만, 이전에 남아있던 (3, 4) 재귀호출로 가보겠습니다. 

left = 3 right = 4 pivot = 3입니다.

left 값은 그대로일 것이고, R 값은 3이됩니다.

쉽게 생각해보면, left는 pivot보다 작을 경우에만 값이 증가하도록 되어 있기 때문에

현재 pivot과 가리키는 값이 같아서 값이 변하지 않습니다.

right은 pivot보다 값이 클 경우에만 값이 증가하도록 되어 있는데, 현재 바로 다음 인덱스 값을

가지고 있습니다. 그렇기 때문에 1 감소할 수 밖에 없겠죠?

그러면 L=3 R =3이기 때문에 swap은 일어나지 않습니다. 

이후 L=4가 되고 R=2가 됩니다. (left = 3, right = 4)

left = 3 의 값이 R = 2값보다 작기 때문에 left와 R을 사용하는 quicksort는 호출되지 않습니다.

L = 4 의 값이 right = 4값과 같기 때문에 L과 right를 사용하는 quicksort가 재귀호출되지 않습니다.

더이상 재귀함수를 호출할 조건이 만족되지 않기 때문에 quicksort 함수는 이렇게 끝나게 됩니다.

c언어 소스코드를 기준으로 설명드렸는데 다소 이해가 되지 않을 수 있습니다.

그럴 경우에는 손으로 한 과정씩 직접 써가면서 연습해보시기 바라겠습니다.

* 참고: C언어 Quicksort 예시 코드

void QuickSort(int arr[], int left, int right){

  int L = left, R = right;

  int temp;

  int pivot = arr[(left+right)/2]; // pivot 위치(중앙)의 값을 받는다.

  printf("L: %d / pivot : %d / R: %d\n", L, (left + right)/2, R); // 데이터 확인

  // 아래의 while문을 통해서 pivot 기준으로 좌, 우로 partition 분할

  while( L <= R ){

    // pivot 값이 중간이고, 비교 대상인 arr[L], arr[R]은

    // pivot과 비교해서 중간 지점을 넘어가면 종료로 볼 수 있다.

    while(arr[L] < pivot){ // left부터 증가하며 pivot 이상의 값을 찾는다.

      L++;

    }

    while(arr[R] > pivot){ // right부터 감소하며 pivot 이하의 값을 찾는다.

      R--;

    }

    // L, R 모두 최대 pivot 위치까지 이동한다.

    if(L <= R){ // 현재 L이 R 이하면 (이미 L > R은 정리된 상태임.)

      if(L != R){ // 같지 않은 경우에

        temp = arr[L];

        arr[L] = arr[R];

        arr[R] = temp;

      } // L과 R이 같다면 swap은 필요 없고, 한 칸씩 진행하면 된다.

      L++; R--; // 그리고 L,R 한 칸 더 진행

      printf("확인 : ");

      for(int i=0; i < 5; i++){ // 데이터 확인하는 부분

        printf("%d ", arr[i]);

      }

      printf("\n");

    }

  }

  printf("\n");

  // 조건을 확인해서 재귀함수를 사용한다.

  printf("QuickSort 재귀 호출 확인(만족 시 호출)\n1. left: %d < R : %d \n2. right: %d > L : %d\n\n", left, R, right, L); // 데이터 확인하는 부분

  if(left < R)

    QuickSort(arr, left, R);

  if(L < right)

    QuickSort(arr, L, right);

}

int main(void){

  int data[5] = { 3, 1, 4, 2, 7 };

  printf(" -- 정렬 전 순서 -- \n"); // 정렬하기 전의 상태를 출력한다.

  for(int i=0; i < 5; i++){

    printf("%d ", data[i]);

  }

  printf("\n\n");

  QuickSort(data, 0, 4); // 9 = 10-1

  printf(" -- 정렬 후 순서 -- \n"); // 정렬하기 전의 상태를 출력한다.

  for(int i=0; i < 5; i++){

    printf("%d ", data[i]);

  }

  printf("\n");

  return 0;

}