[Algorithm] 정렬 - 퀵 정렬(Quick Sort)

안녕하세요. J4J입니다.

 

이번 포스팅은 정렬 알고리즘 중 퀵 정렬에 대해 적어보는 시간을 가져보려고 합니다.

 

 

퀵 정렬이란?

 

퀵 정렬은 분할 정복법(Divide and Conquer)이 사용되는 정렬 방법으로 pivot이라는 리스트 안의 한 원소를 기준으로 좌측에는 pivot보다 작은 원소, 우측에는 pivot보다 큰 원소로 분할시켜 정렬하는 방식을 사용합니다.

 

예를 들어 길이가 5인 배열에 원소 값이 {3, 1, 15, 11, 7}이 저장되어 있다면 정렬되는 방식은 다음과 같습니다.

 

1-1. 정복 단계를 거치며 pivot 값을 구합니다.

1-2. pivot값은 7이 되며 pivot을 기준으로 작은 원소인 {3, 1}, 큰 원소인 {11, 15}로 분할시킵니다.

 

2-1. {3, 1} 배열에 정복 단계를 거치며 pivot 값을 구합니다.

2-2. pivot 값은 1이 되며 pivot을 기준으로 작은 원소는 없고 큰 원소인 {3}로 분할시킵니다.

 

3-1. {11, 15} 배열에 정복 단계를 거치며 pivot 값을 구합니다.

3-2. pivot 값은 15가 되며 pivot을 기준으로 작은 원소인 {11}로 분할시키고 큰 원소는 없습니다.

 

4-1. {3}과 {11}은 더 이상 분할/정복 단계를 거치지 않습니다.

 

 

구현 코드 (Java)

 

package sorting;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int intArray[] = new int[]{3, 1, 15, 11, 7};
		
		quickSort(0, intArray.length-1, intArray); // 퀵 정렬
		
		System.out.println(Arrays.toString(intArray)); // [1, 3, 7, 11, 15]
	}
	
	public static void quickSort(int left, int right, int[] array) {
		if(left >= right) { // 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같다면 정렬 종료
			return;
		}
		
		int pivot = partition(left, right, array); // 정렬하며 pivot 위치 구하기
		quickSort(left, pivot-1, array); // 왼쪽 인덱스부터 pivot 전 까지 나누기
		quickSort(pivot+1, right, array); // pivot 이후부터 오른쪽 인덱스 까지 나누기
	}
	
	public static int partition(int left, int right, int[] array) {
		int pivot = left-1; // 초기 pivot 위치 저장
		
		for(int i=left; i<right; i++) {
			if(array[right] > array[i]) { // end값보다 작다면 pivot과 현재 인덱스 위치 변경
				int temp = array[++pivot];
				array[pivot] = array[i];
				array[i] = temp;
			}
		}
		
		int temp = array[++pivot]; // pivot과 end 위치 변경
		array[pivot] = array[right];
		array[right] = temp;
		
		return pivot;
	}
}

 

퀵 정렬 순서

 

 

특징

 

• 재귀 함수에 대한 이해가 필요하는 등의 이유로 구현이 어려운 편입니다.
• 불안정 정렬(unstable sort)입니다. (정렬 전과 후를 비교했을 때 동일 값들끼리 순서가 변경될 수 있습니다.)
• 제자리 정렬(in-place sort)입니다. (값이 담겨있는 것을 제외하고는 추가적인 공간을 사용하지 않습니다.)
• 정복(결합)한 뒤 분할시키는 분할 정복법(Divide and Conquer)을 사용합니다.
• 분할할 때 원소의 개수를 균등하게 분할하지 않습니다.
• 시간 복잡도가 O(NlogN)입니다.

 

시간 복잡도가 O(NlogN)인 이유는 분할할 때 logN만큼의 시간이 소비되고 정복할 때 N만큼의 시간이 소비되어 O(NlogN) 만큼의 시간 복잡도가 걸립니다.

 

 

정리

 

● 퀵 정렬은 pivot을 기준으로 분할/정복을 통해 정렬하는 방식

● O(NlogN)의 빠른 시간 복잡도를 가짐

● 구현이 어려운 편

● 분할할 때 균등 분할하지 않음

● 정렬 알고리즘 중 속도가 빠른편에 속해 시간을 고려하며 구현해야 될 때 많이 사용됨

 

 

 

이상으로 퀵 정렬에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.