8-5) 퀵 정렬 - 퀵 정렬이란, worst case, 코드 구현

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

 

퀵 정렬 (quick sort)

정렬 알고리즘 중 하나인 퀵 정렬은 중심점 - 피벗(Pivot Point)을 임의로 고른 후 이 중심점보다 작은 수를 한 쪽으로 분류하고 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법이다. 매우 빠른 수행 속도를 가지는 정렬 방식이다.

퀵 정렬은 in-place 정렬로 추가로 메모리 공간을 필요로하지 않으며 중복 숫자의 순서를 보장할 수 없는 불안정 정렬이다.

 

 

퀵 정렬 과정(순서)

1) 피벗(pivot)을 선택한다. (주로 리스트의 중간에 있는 숫자 혹은 마지막에 있는 숫자 - 중간 값일 확률이 높음)

2) 마지막 요소와 피벗의 위치를 바꿔 피벗을 리스트의 가장 끝으로 보낸다.

3) 2개의 카운터를 사용하여 리스트의 처음부터 탐색한다.

  - 첫 번째 카운터에는 피벗보다 큰 숫자의 위치를 저장, 두 번째 카운터에는 현재 탐색하고 있는 위치를 저장

4) 탐색하며 피벗보다 작은 숫자를 발견하면 첫 번째 카운터의 숫자 위치와 바꿔준다.

5) 3, 4 과정을 반복하면 피벗보다 큰 수와 피벗보다 작은 수가 나눠진다.

6) 다시 피벗을 선택하여 앞의 과정을 반복

 

 

피벗의 왼쪽에 있는 숫자들은 오른쪽에 있는 숫자들과 비교할 필요가 없으므로, 평균적인 경우에 퀵 정렬의 시간 복잡도는 O(n logn)이 된다.

 

퀵 정렬: Worst case

최소지점을 계속해서 피벗으로 지정할 경우

 

앞에서 보았듯 퀵 정렬은 평균적인 상황에서 전체 데이터의 반씩만 비교해나가기 때문에 O(n logn)의 시간 복잡도를 갖는다. 

퀵 정렬의 Worst case는 계속해서 최소인 지점을 피벗 포인트로 지정할 경우로, (n-1) + (n-2) + (n-3) + (n-4) .... 의 대소 비교를 거치게 된다. 즉, 최악의 경우 퀵 정렬의 시간 복잡도는 O(n^2)이다.

 

 

퀵 정렬 :  코드

public class QuickSort <E> {
	E[] array;
	// 제너릭 생성자
	public E[] sort(E[] array) {
		this.array = array;
		quicksort(0, array.length - 1);
		return array;
	}
	// 위치를 바꿔주는 함수
	public void swap(int from, int to) {
		E tmp = array[from];
		array[from] = array[to];
		array[to] = tmp;
	}
	// 퀵 정렬
	public void quicksort(int from, int to) { // from, to: 정렬해야 할 배열의 범위
		// 정렬 종료
		if (from >= to) return;		// 리스트에 요소가 하나 존재: 이미 정렬됨
		// value: 중심점(Pivot Point)으로 배열의 마지막에 있는 숫자를 선택
		E value = array[to];
		// 중심점보다 큰 값을 가리킬 카운터를 가장 앞으로 지정
		int counter = from;
		// 피벗의 바로 앞까지 탐색
		for (int i=from; i < to; i++) {
			// 중심점보다 작은 값을 발견하면 중심점보다 큰 값(counter)과 SWAP
			if (((Comparable<E>) array[i].compareTo(value) <= 0) {
				swap(i, counter);
				counter++;
			}
		}
		// 중심점이 중간에 오게 SWAP
  		swap(counter, to);
		// 피벗으로 나뉜 배열의 왼쪽과 오른쪽을 정렬
        // 카운터의 위치는 맞는 자리이므로 더 이상 옮길 필요X
		quicksort(from, counter - 1);
		quicksort(counter + 1, to);

}