Quick Sort 퀵 정렬 (C++)

Quick Sort 퀵 정렬 (C++)

---

Counting Sort란?

기준 데이터(Pivot)을 설정하고 그 기준 보다 큰 데이터와 작은 데이터의 위치를 바꾸어가며 정렬하는 알고리즘

분할 정복 기법을 활용한다

불안정 정렬

순서

1. 피봇의 위치를 설정한다.

2. 분할 : 피봇을 토대로 데이터를 정렬해나간다. 정렬이 끝나면 피봇의 앞은 피봇보다 작은 값들이,
    피봇의 뒤는 피봇보다 큰 값들이 오게된다. 

3. 2의 과정으로 쪼개진 영역에 대해 재귀적으로 다시 정렬을 수행한다.

이를 애니메이션으로 나타내면 다음과 같다.

시간복잡도

평균 시간 복잡도 : O(NlogN)

이미 정렬이 되어있는 상태일 때 최악의 경우가 되며, 이 때의 시간 복잡도는 O(N^2)

Code

#include<iostream>
using namespace std;

void swap(int arr[], int a, int b) {
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

void quick_sort(int arr[], int start, int end) {
	// 원소가 1개인 경우 종료
	if (start >= end) return;
	// pivot은 start위치로 잡는다.
	int pivot = start;
	int L = start + 1;
	int R = end;
	// 분할 과정을 수행한다.
	while (L <= R) {
		// 피봇보다 큰 데이터를 왼쪽에서부터 찾는다.
		while (L <= end && arr[L] <= arr[pivot]) ++L;
		// 피봇보다 작은 데이터를 찾는다
		while (R > start && arr[R] >= arr[pivot]) --R;
		// 엇갈렸다면 피봇 교체
		if (L > R) swap(arr, R, pivot);
		else swap(arr, L, R); // L, R 데이터 교체
	}
	// 분할 과정이 끝나면 나누어진 부분에 대해서 재귀적으로 다시 수행
	quick_sort(arr, start, R - 1);
	quick_sort(arr, R + 1, end);
}


int main(void) {
	int arr[10] = { 2,6,8,1,4,9,5,3,7,10 };
	int N = 10;
	quick_sort(arr, 0, N-1);
	cout << "정렬 후 : ";
	for (int i = 0; i < N; ++i) {
		cout << arr[i] << ' ';
	}
	cout << endl;
	return 0;
}

---

 

cpdm