퀵정렬

퀵정렬

  빠른정렬 알고리즘이며 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬기법이다.

  값을 서로 교체하는데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체원소를 나누는데에

  평균적으로 logN번이 소요되므로 평균적으로 θ(NlogN)의 시간복잡도를 갖는다.

  불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다.

  분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 자랑하는 정렬방법이다.

 

처리과정

  리스트 안에 있는 한 요소를 선택하는데 이렇게 고른 원소를 피벗이라고 한다.

  피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의

  오른쪽으로 옮겨 비균등한 크기로 분할한다.

  그리고 그렇게 분할된 부분리스트를 정렬한 다음 합하여 전체가 정렬된 리스트로 만들어주는 방법이다.

 

  5 4 3 2 9 6 7 1 10 8 의 순서로 값을 입력하고 퀵정렬로 처리한다고 했을 때

  제일 앞에 있는 5가 피벗이 된다. 피벗을 기준으로 다음 인덱스 방향으로 피벗보다 큰 값을 찾고

  제일 뒤에서부터 앞으로 오며 피벗보다 작은 값을 찾는다.

  그럼 큰 값으로는 9 작은값으로는 1이 선택되고 두 값의 위치를 바꿔준다.

 

  5 4 3 2 1 6 7 9 10 8

 

  이 과정을 반복해서 처리하는데 다음 큰 값과 작은 값은 1과 6이 된다.

  하지만 순서로 봤을 때 1과 6은 서로 교차하게 된다.

  뒤에서 앞으로 오며 값을 찾았을 때 1을 갖게 되고 앞에서 뒤로 가면서 6을 큰값으로 갖게 되기 때문이다.

  이렇게 교차되는 상황이 되었다면 작은 값을 피벗과 위치를 변경해준다.

 

  1 4 3 2 5 6 7 9 10 8

 

  이렇게 위치를 바꿔주면 피벗인 5를 기준으로 왼쪽은 작은값, 오른쪽은 큰 값으로 나눠지고 분할하게 되는것이다.

  

  1 4 3 2    5    6 7 9 10 8 이렇게 분할 된 리스트를 앞쪽리스트 따로 뒤쪽리스트 따로 퀵정렬을 수행하게 되고

  1 2 3 4    5    6 7 8 9 10 이렇게 완료 된다면 이대로 출력을 시켜주는 것이다.

 

코드 예제

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000

int a[SIZE];

int swap(int *a, int *b){
  int temp = *a;
  *a = *b;
  *b = temp;
}

void quickSort(int start, int end){
  if(start >= end) return;
  
  int key = start, i = start + 1, j = end, temp;
  
  while(i <= j){
    while(i <= end && a[i] <= a[key]) i++;
    //큰 값을 찾는다
    while(j > start && a[j] >= a[key]) j--;
    //작은값을 찾는다
    if(i > j) swap(&a[key], &a[j]);
    //작은값과 큰값이 엇갈린 상태라면
    else swap(&a[i], &a[j]);
    //작은값과 큰값이 엇갈리지 않은 상태라면
  }
  quickSort(start, j - 1);
  quickSort(j + 1, end);
}

int main(void){
  int n;
  scanf("%d", n);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
  quickSort(0, n - 1);
  
  for(int i = 0; i < n; i++) printf("%d ", a[i]);
  system("pause");
  return 0;
}

  값의 개수를 n에 입력하고 n개의 값을 a배열에 입력한다.

  입력이 끝난 후 quickSort의 start에는 0을 end에는 n - 1을 넣어준다.

  end가 n - 1이어야 하는 이유는 n은 값의 총 개수 즉. 배열의 크기인건데 end는 인덱스로서 사용해야 하고

  인덱스는 1이 아닌 0부터 시작하기 때문에 1을 빼서 넘겨줘야 한다.

  처리과정의 예시대로 예를 들자면

  end에는 9가 들어가게 될것이고 key = 0, i = 1, j = 9가 된다.

 

  i는 j보다 작기 때문에 반복문을 실행하고

  첫 반복문에서는 i(1) <= end(9) && a[i](4) <= a[key](5) 이런 상태이고 조건이 만족하기 때문에

  i을 증가시켜준다. 주석처리한것을 보면 큰 값을 찾는 부분이기 때문에 i번째의 값이 피벗인 key번째의 값보다 작다면

  i를 증가시켜서 다음 값을 확인함으로써 큰값을 찾아 나간다.

 

  아래 반복문 역시 j(9) > start(0) && a[j](8) >= a[key](5) 가 성립하므로 j를 감소시키는데

  작은 값을 찾아야 하므로 j번째 값이 key번째 값보다 크다면 j를 감소시켜 배열의 뒤에서 앞으로 가며 찾는것이다.

 

  조건문의 경우 i가 j보다 크다는 것은 작은값과 큰 값이 서로 엇갈렸다는 건데

  5 4 3 2 1 6 7 9 10 8  엇갈린 이 예시에서 보자면 i는 큰값이기 때문에 5가 되고 j는 작은값이기 때문에 4가 된다.

  즉, i가 더 크다는 것은 값이 엇갈린 상태라는 것이고 그래서 작은값과 피벗값의 위치를 바꾸기 위해

  a[key]와 a[j]를 넘겨서 위치를 바꿔준다.

 

  else의 경우 엇갈리지 않았다는 것이므로 두 값의 위치만 바꿔주면 되기 때문에 a[i] 와 a[j]만 넘겨서 위치를 

  변경해준다.

 

  제일 외부에 있는 반복문이 끝나고 나면 피벗을 기준으로 작은값 큰값이 나누어졌다는 의미가 된다.

  즉, if문에서 else로 가지않고 조건이 만족해서 swap함수를 처리했다면 외부 반복문도 false가 되므로

  재귀적으로 처리하여 피벗 기준 양쪽 리스트를 다시 재정렬 해주게 된다.

 

 

  퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 O(N^2)다. 실제로 정렬을 함에 있어서는 퀵 정렬을 직접 구현하지

  않고 C++의 algorithm라이브러리를 사용한다고 한다. Algorithm 라이브러리의 sort()함수는 퀵 정렬을 기반으로 하되

  O(NlogN)을 보장한다.

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직