[알고리즘] 퀵 정렬 | Quick Sort | C++코드 해석

병합정렬(Merge Sort)과 함께 기본 정렬알고리즘인 퀵정렬.

병합정렬이 수열을 반으로 쪼개가며 정렬했다면,

퀵정렬은 기준을 두고 기준보다 작은값들, 기준보다 큰값들로 쪼개가며 정렬한다.

 

병합정렬은 따로 정렬해둔 값을 저장해둘 메모리공간이 필요했다면

퀵정렬은 따로 메모리공간이 필요하지 않다.

 

하지만 병합정렬은 언제나 시간복잡도가 일정한 반면

퀵정렬은 잡히는 기준에 따라 시간복잡도가 O(n^2)까지 올라갈수있다고한다. 

 

코드는 이러하다.

	#include <iostream>
	using namespace std;
	void swap(int& a, int& b){ // pivot을 int&으로 선언해야하는 이유. 그렇지않으면 값만 복사하기때문에 실제 값이 변하지 않는다.
	int t=a; a=b; b=t;
	}
	void partition(int* A, int low, int high){
	if(low>=high) return;
	int& pivot=A[high]; //가장 오른쪽에 있는 수를 pivot으로 설정
	int i=low-1, j=low; //i는 pivot이 들어갈 자리를 정해주는 포인터역할, j는 값 비교를 위한 포인터역할
	for(; j<high; j++){
	if(A[j]<pivot){
	swap(A[++i],A[j]);
	}
	}
	swap(A[++i],pivot);
	partition(A, low, i-1);
	partition(A,i+1,high);
	}
	int main(){
	int N;
	cin>>N; // 수열의 길이
	int* A= new int[N];
	for(int i=0; i<N; i++){
	cin>>A[i];
	}
	partition(A,0,N-1);
	for(int i=0; i<N; i++){
	cout<<A[i]<<" ";
	}
	}

view raw QuickSort.cpp hosted with ❤ by GitHub

pivot이 기준 값이 되고

i가 pivot의 자리를 찾아준 다고 생각하면된다.

이해하기 쉽게 예시를들어 그림으로 설명해보자면 이런식이다.