퀵 정렬(Quick Sort)

퀵 정렬 (Quick Sort)

- 정의 : 2개의 부분문제로 분할하나 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘

- 문제점 : 정복 후 분할하는 특징이 있어 이 정렬을 수행하기 위해 다시 정렬(Sort)를 해주어야 하는 문제가 있다.

최악 경우 시간복잡도 : O(n^2)

최선 경우 시간복잡도 : 피봇과의 비교횟수 X 층수 = O(n) X log2n = O(nlog2n)

- 피봇 선정 방법

: 퀵 정렬의 불균형한 분할을 완화하기 위해 피봇 선정 방법이 생김

1) 랜덤

2) 세 숫자의 중앙값으로 선정하는 방법 : 가장 왼쪽, 중간, 가장 오른쪽 숫자 중에서 중앙값을 피봇으로 정한다.

ex) 가장 왼쪽 숫자 11, 중간 숫자 1, 가장 오른쪽 숫자 20이라고 할때 가장 중간에 가까운 11을 피봇으로 정한다.

(피봇 선정은 자유롭게 하지만, 2)의 방법이 가장 효율적이다.)

#include <iostream>

#include <time.h>

using namespace std;

void swap(int &a, int &b)

{

int tmp = a;

a = b;

b = tmp;

}

void quicksort(int A[], const int n)

{

int pivot = rand() % n;    // 랜덤으로 설정 ( 1)의 방법 )

int first = 0;

swap(A[pivot], A[first]);    // 피봇의 위치를 배열의 앞으로 옮김

int left = first + 1;        // 피봇을 제외한 모든 배열 검사

int right = n - 1;

// 피봇을 기준으로 피봇보다 작은것은 왼쪽, 큰것은 오른쪽으로 위치 변경

while (left <= right)

{

// 피봇보다 작을 때

if (A[left] < A[first])

{

left++;

continue;     // continue문을 넣어 if문을 실행한 후 다시 while문의 첫부분으로 돌아가도록 함

}

// 피봇보다 클 때

if (A[right] > A[first])

{

right--;

continue;

}

// 왼쪽 포인터가 오른쪽과 같거나 클때 while 종료

if (left >= right) break;

// 왼쪽에 피봇보다 작은 수, 오른쪽에 피봇보다 큰 수가 있을때 위치 변경

swap(A[left], A[right]);

}

  // 왼쪽의 마지막 위치와 피봇의 위치를 스왑

swap(A[first], A[left - 1]);

}

int main()

{

srand((unsigned)time(NULL));        // 실행할 때마다 다른 랜덤값이 나오게 함

const int n = 10;

int A[n] = {0, 2, 5, 9, 6, 3, 7, 8, 1, 4}; // n = 10

quicksort(A, n);

for (int i = 0; i < n; i++)

cout << A[i];

return 0;

}