선택 정렬, 버블 정렬, 삽입 정렬의 한계
: O(N*N)은 데이터 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다.
2^10 = 1,000
2^20 = 1,000,000
log(2)N = (N이 1,000,000일 때) 20
퀵 정렬(Quick Sort)
: 대표적인 분할 정복 알고리즘으로 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 후 배열을 반으로 나누는 정렬 알고리즘
분할 정복
: 배열을 분할해서 계산하는 알고리즘
퀵 정렬(Quick Sort) Sequence
기준값 = 피벗(Pivot)
왼쪽에서 오른쪽으로 이동하면서 Pivot 보다 큰 값 하나 선택
오른 쪽에서 왼쪽으로 이동하면서 Pivot보다 작은 값 하나 선택
작은 값의 index < 큰 값의 index: Pivot과 작은 값 교환
작은 값의 index > 큰 값의 index: 작은 값과 큰 값 교환
Code
#include <iostream>
using namespace std;
int number = 10;
int Data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
void quickSort_up(int *data, int start, int end){
// start: 정렬을 수행하는 부분집합의 첫 번째 원소
// end: 정렬을 수행하는 부분집합의 마지막 원소
// 원소가 1개인 경우
if(start >= end){
return;
}
int key = start; // pivot
int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
int tmp;
// 엇갈리는 경우 while 탈출
while(i <= j){
// i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
while(data[i] <= data[key]){
i++;
}
// j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
// index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
while(data[j] >= data[key] && j > start){
j--;
}
// 엇갈린 경우 pivot값과 현재 data 변경
if(i > j){
tmp = data[j];
data[j] = data[key];
data[key] = tmp;
}
// 엇갈리지 않은 경우 i와 j index의 data 변경
else{
tmp = data[j];
data[j] = data[i];
data[i] = tmp;
}
}
// 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
quickSort_up(data, start, j-1); // 왼쪽 data
quickSort_up(data, j+1, end); // 오른쪽 data
}
void quickSort_down(int *data, int start, int end){
// start: 정렬을 수행하는 부분집합의 첫 번째 원소
// end: 정렬을 수행하는 부분집합의 마지막 원소
// 원소가 1개인 경우
if(start >= end){
return;
}
int key = start; // pivot
int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
int tmp;
// 엇갈리는 경우 while 탈출
while(i <= j){
// i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
while(data[i] >= data[key]){
i++;
}
// j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
// index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
while(data[j] <= data[key] && j > start){
j--;
}
// 엇갈린 경우 pivot값과 현재 data 변경
if(i > j){
tmp = data[j];
data[j] = data[key];
data[key] = tmp;
}
// 엇갈리지 않은 경우 i와 j index의 data 변경
else{
tmp = data[j];
data[j] = data[i];
data[i] = tmp;
}
}
// 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
quickSort_down(data, start, j-1); // 왼쪽 data
quickSort_down(data, j+1, end); // 오른쪽 data
}
int main(void){
quickSort_up(Data, 0, number-1); // 오름차순
for(int i=0;i<10;i++){
cout << Data[i] << " ";
}
cout << endl;
quickSort_down(Data, 0, number-1); // 내림차순
for(int i=0;i<10;i++){
cout << Data[i] << " ";
}
return 0;
}출력
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
만약 아래 배열을 정렬한다면?
선택 정렬의 시간 복잡도: N^2 = 100
퀵 정렬의 시간 복잡도:
1 2 3 4 5 => 5 * 5 = 25
6 7 8 9 10 => 5 * 5 = 25
-> 25 + 25 = 50
∴ O(NlogN)의 시간복잡도를 갖는 알고리즘을 이용하면 100만개 정도의 데이터는 어렵지 않게 정렬이 가능하다.
시간복잡도
평균 : N*logN
최악의 경우: N^2
만약 이미 오름차순 정렬되어있는 배열을 퀵정렬을 이용해 오름차순 정렬한다면?
=> 분할 정복의 이점을 사용하지 못하고 있으므로, 이런 경우에는 insertion sort를 사용하는 게 효율적이다.
'Algorithm' 카테고리의 다른 글
| [Algorithm] 병합 정렬(Merge Sort) (0) | 2023.04.08 |
|---|---|
| [Algorithm] 기초 정렬 문제 (0) | 2023.04.08 |
| [Algorithm] 삽입 정렬(Insertion Sort) (0) | 2023.04.03 |
| [Algorithm] 버블 정렬(Bubble Sort) (0) | 2023.04.02 |
| [Algorithm] 선택 정렬(Selection Sort) (0) | 2023.04.02 |
