Prosto

퀵 정렬(Quick Sort) - C언어/자료구조 본문

Programing/C Programing

퀵 정렬(Quick Sort) - C언어/자료구조

Prosto 2016.10.26 14:04


'빠르게 정렬하는 방법으로 가장 많이 사용되는 퀵정렬'


퀵 정렬은 빠른 정렬이나 퀵 소트(Quick Sort)라고도 부릅니다.



퀵 정렬(Qucik Sort)는 데이터를 정렬하는 방법 중 하나입니다.

 데이터를 분할(Divide)하고 분할된 부분 별로 이동하는 정복(Conquer) 과정을 반복하여 거쳐 정렬하는 방법입니다.


(지금까지의 정렬들과 달리 조금은 복잡합니다만 보고, 직접 해보며 이해할 수 있을 겁니다.)


성능을 Big O로 표기한다면

average, best = O(n log n)이고, worst = O(n^2)입니다.

 일반적으로는 O(n log n)의 성능을 내주지만,

 피봇(중심점이) 항상 최솟값이나 최댓값으로 잡힌다면 최악의 성능인 O(n^2)이 나옵니다.


참고로 지금까지 했던 (선택, 삽입, 버블)정렬들은 일반적으로 O(n^2)의 성능입니다.

위의 정렬들과 비교하면 비교적 빠르지만, 최악의 경우는 똑같으 성능을 냅니다.

그렇기 때문에 일반적으로 퀵소트를 사용할 땐 피봇 선택에 대한 예외 처리를 더 해주고 사용합니다.






퀵 정렬(Quick Sort)을 할 때는

분할(Divide), 정복(Conquer)의 용어와

피봇(Pivot), L, R이 무엇인지 이해하고 있어야 합니다.


하나씩 정리를 먼저 해볼까요?


분할(Divide) : 정렬할 자료들을 기준 값(Pivot)을 중심으로 좌, 우 2개의 부분집합으로 나누는 것을 말합니다.

정복(Conquer) : 부분집합의 원소들 중에서 기준 값보다 작은 원소들은 외쪽, 큰 원소들은 오른쪽 부분집합으로 정렬하는 과정입니다.


부분집합의 크기가 더 이상 나눌 수 없을 때까지(부분집합의 원소가 1개 이하) 분할, 정복 과정이 반복됩니다.


피봇(Pivot) : 기준 값 (일반적으로 전체 원소 중 가운데에 위치한 원소)

L : 왼쪽에서 오른쪽으로 움직이며 피봇 이상인 원소를 찾아 L로 지정.

R : 오른쪽에서 왼쪽으로 움직이며 피봇보다 작은 원소를 찾아 R로 지정.

(R은 L과 만나면 더 이상 왼쪽으로 이동하지 않음.)


이걸 기준으로 아래의 데이터를 정렬하는 과정의 그림을 보시면 됩니다.

 

 



이렇게 8개의 데이터(배열)을 가지고 퀵 정렬(Quick Sort)를 진행해보겠습니다.



가장 먼저 L을 가장 왼쪽인 12, R을 가장 오른쪽인 6을 가리키고,

Pivot(피봇)은 가운데인 2를 가리킵니다.

(0+7)/2 = 3.5(정수 3)이니 3번째 배열입니다.

(배열 번호는 0 1 2 3 4 5 6 7 .. 순으로 보시면 됩니다.)



L은 12로 Pivot(2) 이상이기 때문에 그대로지만,

R은 Pivot(2)보다 작은 값을 못 찾아 R까지 왔죠?


그러면 L과 Pivot의 값이 서로 바뀌고,

Pivot(2)은 옮겨진 위치 그대로 완료됩니다.

(값 = 2, 위치 = 0)



그리고 Pivot인 2 기준으로 왼쪽 집합 정렬을 시도하지만,

왼쪽은 공집합으로 정렬 대상이 없기 때문에 정렬하지 않고,


Pivot의 우측 집합(9 3 12 7 5 10 6)을 대상으로 퀵 정렬을 시작합니다.



이번엔 가장 왼쪽 L이 9, 가장 오른쪽 R이 6이겠죠?

그리고 중심 값인 Pivot은

(1+7)/2 = 4번째입니다. (Pivot의 값은 7)

(마찬가지로 배열 번호니 다섯 번째죠)


바로 L(9)은 Pivot(7) 이상이고, R(6)은 7 미만이네요.

바로 서로 교환해주고 또 진행합니다.



L은 아까와 마찬가지로 7 이상의 값을 찾아가다가 12에서 멈췄고,

R은 7보다 작은 값을 찾아가다가 5에서 멈췄습니다.


그대로 둘의 값을 바꿔줍니다.




그리고 한 칸씩 또 전진했더니

L은 7 이상의 값인 Pivot(7)을 만나 멈추고,

R은 7 미만의 값은 아니지만 L과 같은 위치니 멈춥니다.

(실제로 소스에서는 약간 다르게 사용하지만, 이렇게 설명하는 게 맞는 것 같습니다.)


그렇게 현재 Pivot인 7의 위치가 확정되었습니다. 



다음으로 Pivot이었던 7 기준으로 왼쪽 집합(6 3 5)을 퀵 정렬 합니다.

지금까지와 같이 L, R, Pivot이 설정되었죠?


Pivot은 다시 쓰지만,

(1번째+3번째)/2 = 2번째로 선택된 겁니다.

(0 -> 1 -> 2번째니 값은 3)



L은 3이상이지만,

R은 3 미만 숫자가 없어

5 -> 3을 거쳐 L(6)과 만났습니다.


L과 R이 만났으니 Pivot과 교환합니다.

(현재 상태와 같이 L(피봇보다 큰 값)은 값을 찾았지만,

R은 못 찾고 L(피봇보다 큰 값)까지 갔다는 것은 

L로 이동하는 동안 피봇보다 작은 숫자는 없었다(현재 집합의 가장 작은 숫자가 Pivot이다)

이야기가 되어 L과 Pivot을 바꿔준 겁니다.(L은 Pivot보다 크니 우측으로 가는 것도 맞죠.) )


(피봇 기준 우측에서 이 상황이 벌어졌다면 반대 의미로 똑같이 해석되겠죠.)



이번에도 왼쪽은 공집합이니 진행할 필요가 없고,

우측은 2개의 원소가 있으니 퀵 정렬을 진행해야겠죠?



2번째(6)가 L, 3번째(5)가 R이 되었고,

Pivot으로는 2번째(6)가 되었습니다.( (2+3)/2 = 2 )


L은 피봇(6) 이상, R은 피봇(6) 미만이죠.

조건 만족하니 교환해줍니다.



확정된 왼쪽 집합의 원소가 하나 밖에 없고,

우측은 공집합이기 때문에 더 이상 진행할 수 없습니다.


(현재 왼쪽 부분은 완전히 정렬이 됐죠?)


그리고 아까 7기준으로 왼쪽으로 갔었는데,

이번에는 오른쪽 집합을 이어서 정렬합니다.


L(12)은 Pivot(10) 이상이고, R(9)는 Pivot(10) 미만이니 교환해줍니다.



마지막으로 Pivot과 L R이 만났습니다. 끝이겠죠?




이렇게 퀵 정렬(Quick Sort)를 배열로 살펴봤습니다.


지금 여기서 L은 이상, R은 미만을 기준으로 처리했지만,

L이 초과, R이 이하여도 퀵 정렬 처리가 되겠죠?

(결과적으로 소스 범위 지정이 조금 바뀌겠지만요.)



이제 실제 C언어로 만들어볼까요?





그럼 이번에는 C 언어를 사용하여 퀵 정렬을 해볼까요?

(퀵 정렬은 직접 구현해보면 좋겠지만,

 직접 구현하지 못 해도 소스를 보고 이해한다면 충분할 것 같습니다.

 필요할 때 알고리즘을 참고하여 만들어도 좋을 테니까요.)

 

 

출력 결과 예를 보고

프로그램의 소스를 작성해보세요.

 

(출력 결과 예1)

 

단순히 정렬 전, 후만 출력한 결과입니다.

이렇게 보면 어떤 단계에 걸쳐 정렬이 됐는지 잘 모르겠죠.


(출력 결과 예2 - 어떻게 동작하는지 확인하는 의미에서 출력 부분을 추가했습니다.)

 

그럼 소스를 확인해볼까요?

(참고로, 소스는 위 내용 설명 부분과 차이가 약간 있지만,

Quick Sort로 정렬하는 로직은 동일합니다.)

[퀵 정렬 하는 방식에 약간 차이가 있지만요.

위에서 그림으로 대략적인 구조를 이해했다면

소스로 확실하게 어떻게 작동하는지 확인하셨으면 좋겠네요.]

 

이미지로 보기엔 한계가 있겠죠?

(이해에 도움이 되도록 주석도 많이 달아뒀습니다.)


복사 가능한 소스로 보도록 합시다.

(실제 실행도 해보고 확인해보세요. main부터 차근차근 따라가며 보셔야겠죠?)

 

Source.c

#include<stdio.h>
//Prosto
void QuickSort(int arr[], int left, int right) {
  int L = left, R = right;
  int temp;
  int pivot = arr[(left + right) / 2]; //피봇 위치(중앙)의 값을 받음.

  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 한 칸 더 진행.

   
      for (int i = 0; i < 10; 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[10] = { 10, 6, 7, 9, 3, 4, 2, 1, 5, 8 };
  //int data[10] = { 10, 6, 7, 2, 9, 1, 8, 3, 5, 4 };
  //int data[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
  int data[10] = { 2, 9, 4, 18, 5, 1, 7, 8, 15, 12 };

  //랜덤한 위치라고 생각.

  printf(" --정렬 전 순서--\n"); //정렬하기 전 상태 출력.
  for (int i = 0; i < 10; i++) {
    printf("%d ", data[i]);
  }
  printf("\n\n");

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

  printf(" --정렬 후 순서--\n"); //정렬한 후 상태 출력.
  for (int i = 0; i < 10; i++) {
    printf("%d ", data[i]);
  }
  printf("\n");
  return 0;
}

(소스 수정했습니다.) 

 

이전 소스 - (사용 X)

 

퀵 정렬 이해에 도움이 됐나요?

 

 

(추가로 메일로 오류 부분 지적해주신 '우동혁'님 감사합니다. [요즘 정신이 없어 수정하는데 오래걸렸네요...] )


 

 

궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )

 

4 Comments
댓글쓰기 폼