퀵(quick) 정렬(C/C++ 구현, 시간 복잡도)

1. 퀵 정렬

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

마땅히 찾아봐도 뭔가 정의?? 같은것은 없다

내 해석 : 피벗을 기준으로 작은 것은 왼쪽 큰것은 오른쪽으로 정렬하며 정렬된 배열을 재귀적으로 정렬하는 알고리즘

출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

 

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

1. 피벗 선택( 제일 앞 원소)

2. 피벗 보다 작은 것은 왼쪽, 큰것은 오른쪽으로 이동

3. 왼쪽 인덱스를 가르치는 것과 오른쪽 인덱스를 가르치는 포인터가 교차하면 피벗과 오른쪽 포인터를 교환

4. 아닐 경우, 왼쪽 인덱스와 오른쪽 인덱스를 교환

5. 피벗 기준으로 왼쪽과 오른쪽으로 재귀적으로 정렬

6. 시작 위치가 같거나, 엇갈리면 종료

 

시간 복잡도

평균적

1. 재귀적으로 분할하는 logn

2. 정렬하는데 n

O(nlogn)

최악의 경우(정렬이 되있는 경우)

1. 분할하는데 n(트리 경우로 받을 때, 한쪽으로만 깊이가 깊은 트리)

2. 다시 정렬하는데 n

O(n^2)

 

 

1. n까지 counting 하는데 n

2. 숫자 더해주는데 n

3. 다시 정렬하는데 n

O(n)

 

소스 코드

#include <iostream>

using namespace std;

int arr[10] = { 23,123,324234,12312,2123,24,456,56,123,564 };
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void quick_sort(int list[],int left,int right)
{
	if (left >= right)
		return;
	int pivot = left;
	int start = left + 1;
	int end = right;
	while (start<=end)
	{
		while (list[pivot] >= list[start] && start <= right)
			start++;
		while (list[pivot] <= list[end] && end > left)
			end--;
		if (start > end)
		{
			swap(list[pivot], list[end]);
		}
		else
			swap(list[start], list[end]);
	}
	quick_sort(list, left, end - 1);
	quick_sort(list, end + 1, right);

}
int main()
{
	quick_sort(arr,0,9);
	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	return 0;
}