퀵 정렬(Quick Sort)

퀵정렬은 기준원소를 잡고

기준원소보다 작은 값은

왼쪽으로 

기준원소보다 큰 값은 오른쪽으로 정렬하는 방법이다

따라서 start, end, pivot의 인덱스가 필요하다

 

 

 

 

 

 

 

 

알고리즘 예제는

이걸 따른다

기준원소는 첫번쨰,마지막,가운데 어느것을해도 상관은 없다

보통 첫번째 원소를 기준으로 잡고

i=left+1, j=right으로 설정해

i와 j 가 start~end를 돌며

i에서 pivot보다 큰값이 나오면 stop

j에서 pivot 보다 큰값이 나오면 stop

그리고 arr[i]와 arr[j]를 swap해준다

 

i가 j를 넘었을때 stop하고

pivot과 j를 변경해준다

더 이상 swap해주지않고

 j를 return해 끝내준다

quicksort(start, j-1)   //pivot기준 왼쪽 다시 퀵소트

quicksort(j+1, end)  //pivot 기준 오른쪽 다시 퀵소트

해주면 정렬이 된다

 

 

 

 

c++코드

#include <iostream>
#define SIZE 1000001
using namespace std;

int arr[SIZE];

void quicksort(int, int);
int partition(int, int);

int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	quicksort(0, n - 1);

	for (int i = 0; i < n; i++) {
		cout << arr[i]<<"\n";
	}

	return 0;
}

void quicksort(int start, int end) {
	if (start >= end)		//재귀과정에서 start가 더 커지면 종료
		return;

	int pivot = arr[start];	//피봇은 첫번째요소로 설정

	pivot=partition(start, end);	//분할 후 피봇이 이동했으므로 다시 받음
	quicksort(start, pivot - 1);	//왼쪽 분할 정렬
	quicksort(pivot + 1, end);		//오른쪽 분할 정렬
}

int partition(int start, int end) {
	int pivot = arr[start];
	int i = start + 1, j = end, temp;

	while (i <= j) {

		while (i <= end && arr[i] < pivot) 	//pivot보다 큰값찾을때까지 i증가
			i++;
		
		while (j > start && arr[j] > pivot) 	//pivot보다 작은 값 찾을때까지 j증가
			j--;
		
		if (i < j) {	//작은값을 왼쪽으로 큰값을 오른쪽으로 swap
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}

		else {	//i가 j를 넘었을때 pivot과 j를 변경
			temp = arr[j];
			arr[j] = arr[start];
			arr[start] = temp;
		}

	}


	return j;		//pivot의 위치
	
}

원래 partition을 굳이 안나눠도 되긴하는데

내가 본 강의자료에선 나누길래 일단 나눠봤다

 

백준 2751에 제출해봤지만

시간초과가 뜬다

퀵정렬은 평균 O(nlogn)이지만

최악의 경우 O(n^2)이라 통과가안되는듯하다

 

merge sort가 짱이네