[C++] 퀵정렬 (Quick Sort)

[퀵정렬]

선택정렬, 버블정렬, 삽입정렬에 비해서 굉장히 빠르다.

분할정복 알고리즘(배열의 원소들을 나누어서 계산)으로 평균속도가 O(N*logN)이다.

기준값(피벗)을 기준으로 큰 숫자와 작은 숫자를 반으로 나눈다음 정렬을 한 후 합친다.

[문제] 

3 7 8 1 5 9 6 10 2 4 를 순서대로 정렬하세요

(피벗값은 보통 맨앞에있는 숫자로 한다)

[풀이]

#include <stdio.h>

int number = 10;

int data[10] = { 1,10,5,8,7,6,4,3,2,9};

void quickSort(int* data, int start, int end) {

if (start >= end) {

return;

}

int key = start; //키는 첫번째 원소 

int i = start + 1;// i는 왼쪽에서 출발해서 증가

int j = end; //오른쪽에서 출발을 의미

int temp;

while (i <= j) { //엇갈릴 때까지 반복 왼쪽이 오른쪽보다 작을때 까지만 반복

//내림차순으로 하려면 밑에 두 while을 반대로 바꿔주면 된다

while (data[i] <= data[key]){ //키 값보다 큰 값을 만날때까지 반복

i++;

}

while (data[j] >= data[key] && j > start) {

j--;

}

if (i > j) { //엇갈린 상태면 키 값과 자리 교체

temp = data[j];

data[j] = data[key];

data[key] = temp;

}

else { //엇갈리지 않았다면 큰값과 작은값을 교체

temp = data[j];

data[j] = data[i];

data[i] = temp;

}

}

//똑같은 함수한에 똑같은 함수가 들어가는 재귀함수

quickSort(data, start, j - 1);

quickSort(data, j + 1, end);

}

int main(void) {

quickSort(data, 0, number - 1);

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

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

}

}

[문제점]

항상  O(N*logN)가 보장된 것은아니다.

특정 경우 o(n*n)이 될수도 있다. ( 이미 정렬이 되어있는 경우 분할적으로 나눌 수가 없다.)