정원영

정원영

항상 배우고 싶은 개발자입니다.

Category

(자료구조) 13-1 정렬 (퀵 정렬 - 분할 정복)

업데이트:
3 분 소요

자료 구조 - 정렬 1

1. 퀵 정렬

  • 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬

1) 수행 방법

  • 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킴
  • 기준 값 : 피봇(pivot)
  • 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 선택

2) 개요

  • 퀵 정렬은 다음 두가지 작업을 반복 수행

(1) 분할 (divide)

  • 정렬할 자료들을 기준 값을 중심으로 2개의 부분 집합으로 분할

(2) 정복 (conquer)

  • 부분 집합 원소들 중에서 기준 값보다 작은 원소들은 왼쪽 부분 집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로
    정렬
  • 부분 집합의 크기가 1 이하로 충분히 작지 않으면 순환 호출을 이용하여 다시 분할

3) 수행 방법

(1) 부분 집합으로 분할하기 위해 L과 R을 사용

  • 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시
  • 오른쪽 끝에서 왼쪽으로 움직이면서 피봇 보다 작은 원소를 찾아 R로 표시
  • L이 가리키는 원소와 R이 가리키는 원소를 서로 교환함

(2) L이 R이 만나게 되면

  • 피봇과 R의 원소를 서로 교환
  • 교환한 위치를 피봇의 위치로 확정함

(3) 피봇의 확정된 위치를 기준으로 잡음

  • 만들어진 새로운 왼쪽 부분 집합과 오른쪽 부분 집합에 대해서 퀵 정렬을 순환적으로 반복 수행함
  • 모든 부분 집합 크기가 1 이하가 되면 퀵 정렬을 종료

4) 수행 과정

  • 정렬 되지 않은 {69,10,30,2,16,8,31,22}의 자료들을 퀵 정렬 방법으로 정렬하는 과정
  • 원소의 개수가 8개이므로 네 번째 자리에 있는 원소 2를 첫 번째 피봇으로 선택하고 퀵 정렬 시작

(1) 원소 2를 피봇으로 선택하고 퀵 정렬 시작

alt

  • L이 오른쪽으로 이동하면서 피봇 보다 크거나 같은 원소를 찾음
  • R이 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾음
  • L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 됨
  • L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 2의 위치를 확정함

alt

(2) 피봇 2의 왼쪽 부분 집합은 공집합

  • 피봇 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않음
  • 오른쪽 부분 집합에 대해서 퀵 정렬 수행
  • 오른쪽 부분 집합의 원소가 7개 이므로 가운데 있는 원소 16을 피봇으로 선택

alt

  • L이 찾은 30과 R이 찾은 8을 서로 교환 함

alt

  • 현재 위치에서 L과 R의 작업을 반복함
  • L은 원소 69를 찾았지만, R은 피봇보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 됨
  • L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 16위치를 확정함

alt

(3) 원소 10을 피봇으로 선택하여 퀵 정렬 수행

  • 피봇 16의 왼쪽 부분 집합에서 원소 10을 피봇으로 선택하여 퀵 정렬 수행

alt

  • L의 원소 10과 R의 원소 8을 교환
  • L의 원소가 피봇이므로 피봇원소에 대한 자리교환이 발생한 것이므로 교환한 자리를 피봇 원소 10의 위치로 확정

alt

(4) 피봇 10의 확정된 위치에서의 왼쪽 부분 집합은 원소가 한개

  • 피봇 10이 확정된 위치에서의 왼쪽 부분 집합은 원소가 한개 이므로 퀵정렬 수행 하지 않음
  • 오른쪽 부분 집합은 공집합이므로 퀵 정렬 수행 않음
  • 이제 1단계의 피봇이었던 원소 16에 대한 오른쪽 부분 집합에 대해 퀵 정렬을 수행
  • 오른쪽 부분 집합의 원소가 4개이므로 두 번째 원소 30을 피봇으로 선택

alt

  • L이 찾은 69와 R이 찾은 22를 서로 교환

alt

  • 현재 위치에서 L과 R의 작업를 반복
  • L은 오른쪽으로 이동하면서 피봇 보다 크거나 같은 원소인 30을 찾음
  • R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾다가 못 찾고 원소 30에서 L과 만남
  • L과 R이 만났으므로 피봇과 교환
    • 이경우는 R의 원소가 피봇이므로 피봇에 대한 자리 교환이 발생한 것이므로 교환한 자리를 피봇의 자리로 확정

alt

(5) 피봇 30의 확정된 위치에서의 왼쪽 부분 집합의 원소가 한 개

  • 피봇 30의 확정된 위치에서의 왼쪽 부분 집합의 원소가 한 개 이므로 퀵정렬 수행 않음
  • 오른쪽 부분 집합에 대해서 퀵 정렬 수행
  • 오른쪽 부분 집합의 원소 2개 중에서 원소 31을 피봇으로 선택

alt

  • L은 오른쪽으로 이동하면서 원소 31을 찾음
  • R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾다가 못 찾은 채로 원소 31에서 L과 만남
  • L과 R이 만났으므로 피봇과 교환하는데 R의 원소가 피봇이므로 결국 제자리가 확정

alt

5) 퀵 정렬 알고리즘

  quickSort(a[], begin, end)
      if (m < n) then {

          p <- partition(a, begin, end);
          quickSort(a[], begin, p-1);
          quickSort(a[], p + 1, end);
      }
  end quickSort()
  • 파티션 분할 알고리즘
  partition(a[], begin, end)
      pivot <- (begin + end)/2;
      L <- begin;
      R <- end;
      while (L < R) do {
        while(a[L] < a[pivot] and L < R ) do L ++;
        while(a[R] >=a[pivot] and L < R ) do R --;

        if( L < R ) then {  // L의 원소와 R의 원소 교환

            temp <- a[L];
            a[L] <- a[R];
            a[R] <- temp;
        }
      }
      temp <- a[pivot];   // R의 원소와 피봇 원소 교환
      a[pivot] <- a[R];
      a[R] <- temp;
      return R;
  end partition()

(1) 메모리 사용 공간

  • n개의 원소에 대한 n개의 메모리 사용

(2) 연산시간

(2-1) 최선의 경우
  • 피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분 되는 경우가 반복되어
    수행 단계의 수가 최소가 되는 경우
(2-2) 최악의 경우
  • 피봇에 의해서 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가
    최대로 되는 경우
(2-3) 평균 시간 복잡도 : O(n log2 n)
  • 같은 시간 복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더빨리 실행되어 실행 시간 성능이
    좋은 정렬 방법

댓글남기기

참고