[정렬 알고리즘] 4. 퀵정렬(Quick Sort)

[정렬 알고리즘]

1. 선택 정렬

2. 버블 정렬

3. 병합 정렬

4. 퀵정렬

5. 힙정렬

6. Counting Sort

_________________________________

🔎퀵 정렬이란?

일정한 기준으로 '기준 원소(pivot)'을 잡아서 그 원소의 오른쪽에는 그 원소보다 작은 원소들을, 왼쪽에는 큰 원소들을 배치하는 일을 반복하는 정렬 방식.

성능이 좋다. 시간도 적게 걸리고, merge sort와 공간복잡도 notation은 같지만 임시 배열이 필요하지 않기 때문에 크기가 큰 배열에서 더 유리하다.

 

_______________________________________

🔎퀵 정렬 알고리즘

1. 배열의 길이가 0보다 큰 경우, 기준 원소를 잡아서 그 원소의 오른쪽에는 해당 원소보다 작은 원소를, 왼쪽에는 큰 원소를 배치한다. 배열 길이 0이면 아무것도 수행하지 않음(Base case).

• 배치 하는 방법
  • 1. pivot을 배열 끝으로 보낸다.(애초에 pivot을 마지막 원소로 잡아도 된다.)
  • 2. 배열의 첫번째 원소 전에 i, 그 다음에 j라는 레퍼런스 인덱스를 둔다.
  • 3. j를 1씩 더해 가면서 pivot과 비교한다. 만약 j가 pivot보다 작으면 i값을 하나 증가시킨 뒤 i의 원소와 swap한다.
  • 4. 3을 반복하다가 j가 끝에서 두번째 원소를 가리키게 되면(pivot만 확인을 안한상태) pivot과 i+1의 원소를 교환한다.

2. 배치가 완료된 배열을 기준 원소 기준으로 반씩 나눠 다시 1의 과정에 넣는다.

 

 

📌 필요한 함수

1. partition 함수(중요) : 기준원소를 잡고 양옆으로 작은 원소/큰 원소를 나누는 함수(위 소개한 과정의 1번을 수행)

2. quicksort 함수 : partition함수를 호출한 뒤 결과 pivot의 위치를 기준으로 배열의 반씩 재귀호출

 

<partition 함수>

partition(A[], p, r){
	//A배열이 p~q까지 정렬되어 있고, q+1~r까지 정렬되어 있음

	pivotElement <- A[r];
	i<- p-1;
    
    for(j<-p to r-1){
    	if(A[j]<=pivotElement)
        	then A[++i] <-> A[j];
    }
    
    A[i+1] <-> A[r];
    return i+1;
}

 

 

<quicksort 함수>

quickSort(A[], p, r){
	//A배열이 p~q까지 정렬되어 있고, q+1~r까지 정렬되어 있음
    if(p<r) then{
    q <- partition(A[], p, r)
    quickSort(A[], p, q-1);
    quickSort(A[], q+1, r);
    }
}

 

___________________________

 

🔎복잡도 분석

📌 시간복잡도

$\Theta(nlogn)$

 

: $T(n) = 2/n \sum_{k=0}^{r-1}T(k) +\Theta(n)$

$\Theta(n)$은 partition 할 때 걸리는 시간이고, $\sum_{k=0}^{r-1}T(k)$은 모든 pivot이 (k+1)번째 작은 원소일 확률이 다 같다고 했을 때(첫번째 작은 원소면 0:n-1 이렇게 나누어진다)의 재귀호출을 평균낸 결과이다.(Best : $2T(n/2)$ Worst : $T(n-1)$)

이걸 수학적 귀납법을 사용하면 저렇게 정리된다는것을 증명할 수 있다.(log때문에 중간에 흡수가 있다)

 

 

📌 공간복잡도

$O(n)$

call stack이 가장 많이 쌓일 때가 n개 쌓일 때고, 최소로 쌓일 때가 logn개 쌓일 때이다. 그리고 입출력에 n이 사용된다.

_________________________________

🔎장단점

장점

1. $O(nlogn)$ 알고리즘 중, 실제 수행 속도가 가장 빠르다. 

 

단점

1. 최악의 경우(피벗을 최댓값이나 최솟값으로 설정한 경우) $O(n^2)$ 시간이 걸린다.

2. 불안정 정렬이다.

 

+) 내장함수는 Merge sort, Quick Sort, Heap Sort 중 어떤 것을 사용할까?

 크기에 따라 Quick Sort와 Insertion Sort, Counting Sort를 적절히 사용한다. Merge Sort는 배열 복사 시간 때문에 Quick Sort보다 훨씬 느리다. 특히 JAVA가 배열 복사에 시간이 오래 걸리기 때문에, JAVA의 Arrays.sort()는 크기에 따라 위 세개를 섞어 사용한다고 알고 있다. 자세한 건 모르겠고 대략적으로 아래와 같을 것이다.

1. 크기가 작은 경우 : Insertion Sort. 데이터 이동이 많아 작은 크기 배열에서 강하다.

2. 크기가 큰 경우 : Quick Sort. JAVA에서는 pivot 두개로 하기 때문에 엄청 빠르다고 함.

 

+) 논란이 많아 보이지만 Heap Sort는 nlogn 중에서 제일 느리다고 한다.(아래 링크 참고) 

+) 아무래도 불필요한 swap보다는 캐시 메모리에 미스가 많다는 이야기가 맞는거 같기도 하고 이러네요

 

https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort

Quicksort vs heapsort