정렬, 퀵 정렬(Quick Sort)

학습목표
1. 분할 정복 방법에 대해서 학습
2. 퀵 정렬의 과정을 학습
3. 퀵 정렬의 예제를 학습
4. 퀵 정렬의 Java 언어 기반 구현
5. 퀵 정렬의 특징에 대해서 학습
6. 퀵 정렬의 시간복잡도에 대해서 학습

 

1. 퀵 정렬(Quick Sort)이란 무엇인가?

퀵 정렬은 리스트 안의 하나의 요소를 피벗(pivot)이라는 것을 정하여 피벗을 기준으로 왼쪽 부분 리스트, 오른쪽 부분 리스트로 분할하고 순환 호출을 이용하여 부분 리스트들을 정렬하는 알고리즘입니다.

 

퀵 정렬은 분할 정복(divide and conquer) 알고리즘의 하나로써, 평균적으로 매우 빠른 수행 속도를 가지는 정렬 방법입니다. 분할 정복 알고리즘이란 하나의 커다란 문제를 2개의 작은 문제로 분할(divide)하고 각각의 문제를 해결한 다음, 결과를 모아서 원래의 문제를 정복(conquer)하는 방법이다. 이러한 분할 정복 알고리즘은 대개 순환(recursion) 호출을 이용하여 구현할 수 있습니다.

 

2. 퀵 정렬의 수행 과정 요약

1. 퀵 정렬을 수행하기 위해서 리스트 안에 있는 요소 중 하나의 요소를 선택합니다. 이 요소를 피벗(pivot)이라 부릅니다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽으로 옮겨지고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨집니다. 이렇게 되면 피벗의 왼쪽은 피벗보다 작은 요소들이 위치하게 되고, 피벗의 오른쪽은 피벗보다 콘 요소들이 위치하게 됩니다.
3. 피벗을 제외한 왼쪽 리스트(피벗보다 작은 요소들)와 오른쪽 리스트(피벗보다 큰 요소들)을 다시 퀵 정렬을 수행합니다.
   • 부분(왼쪽, 오른쪽) 리스트에 대해서 퀵 정렬을 수행하는데 순환호출을 이용하여 정렬을 반복합니다.
   • 동일하게 부분 리스트에서도 다시 피벗을 결정하고 피벗을 기준으로 왼쪽 부분 리스트, 오른쪽 부분 리스트로 나누는 과정을 반복합니다.
4. 부분 리스트들이 분할(divide)이 불가능할때까지 반복합니다.
   • 분할 불가능 조건 : 리스트의 크기가 0 or 1

3. 퀵 정렬의 구체적인 개념

퀵 정렬은 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 병합하여 전체가 정렬된 리스트가 되게하는 방법입니다.

 

퀵 정렬은 분할 정복 방법을 사용합니다.

• 분할(divide) : 입력 리스트를 피벗을 기준으로 비균등하게 2개의 부분 리스트(왼쪽 리스트 : 피벗을 기준으로 피벗보다 작은 요소들, 오른쪽 리스트 : 피벗을 기준으로 피벗보다 큰 요소들)로 분할합니다.
• 정복(conquer) : 왼쪽, 오른쪽 부분 리스트를 정렬합니다. 이때 순환 호출을 이용하여 왼쪽 리스트, 오른쪽 리스트에 대해서 퀵 정렬을 순환 호출합니다.
• 결합(combine) : 정렬된 부분 리스트들(왼쪽, 오른쪽)을 하나의 리스트로 합병합니다.
• 순환 호출이 한번 진행 될때마다 최소 하나의 피벗은 최종적으로 위치가 정해집니다.(정렬완료)

 

4. 퀵 정렬 알고리즘의 예제

리스트 [5,1,3,8,9,4,2,7,10,6]을 오름차순 정렬한다고 가정합니다. 아래의 그림은 퀵 정렬에서 피벗을 기준으로 두 개의 부분 리스트로 나누는 과정입니다. (Java 언어 코드의 partition 메서드의 내용)

• 피벗 값을 입력 리스트의 첫번째 데이터로 이용합니다. (다른 임의의 값이어도 상관없습니다.)
• 2개의 인덱스 변수(low, high)를 이용해서 리스트를 두 개의 부분 리스트로 분할합니다.
• 1회전 : 피벗이 5인 경우
  1. low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗(5)보다 큰 데이터(8)을 찾으면 멈춥니다.
  2. high는 오른족에서 왼쪽으로 탐색해가다가 피벗(5)보다 작은 데이터(2)를 찾으면 멈춥니다.
  3. 만약 low가 high보다 작다면 low와 high가 가리키는 두 데이터를 교환합니다. (swap(low,high))
  4. 이 탐색-교환 과정은 low가 high보다 클때까지 반복합니다.
  5. 만약 low가 high보다 크다면 피벗과 high가 가리키는 두 데이터를 교환합니다. (swap(pivot, high))
  6. 기존 피벗의 값을 가지는 high 포인터의 위치는 정렬이 완료된 자리가 됩니다.
• 2회전 : 피벗(1회전의 왼쪽 부분리스트의 첫번째 데이터)이 4인 경우
  • 위와 동일한 방법으로 반복합니다.
• 3회전 : 피벗(1회전의 오른쪽 부분리스트의 첫번째 데이터)이 9인 경우
  • 위와 동일한 방법으로 반복합니다.

 

5. 퀵 정렬 알고리즘 Java 기반 구현

import java.util.Arrays;

public class QuickSort<E> {
	private static int partition(int[] arr, int left, int right)
	{
		int pivot;
		int low, high;
		
		low = left+1;
		high = right;
		pivot = arr[left];	// 정렬할 리스트의 가장 왼쪽 데이터를 pivot으로 선택 (임으의 값을 pivot으로 선택함)
	
		while(low<high)
		{
			// pivot보다 큰 값을 찾을때까지 low를 증가
			while(low<=right && arr[low]<pivot)
			{
				low++;
			}
			
			// pivot보다 작은 값을 찾을때까지 high를 감소
			while(high>=left && arr[high]>pivot)
			{
				high--;
			}
			
			// 위의 두 low와 high를 이동하였음에도 low가 high보다 작은 경우
			// arr[low]와 arr[high] 값 교환 수행
			if(low<high)
			{
				swap(arr, low, high);
			}
		}
		
		// low가 high와 겹치거나 오른쪽(큰 경우)에 있는 경우
		// arr[left]와 arr[high]를 값 교환
		swap(arr, left, high);
		
		// pivot의 위치인 high를 반환 (high의 위치는 정렬이 완료됨)
		return high;
	}
	
	private static void swap(int[] arr, int low, int high) 
	{
		int temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
	}

	public static void sort(int[] arr, int left, int right)
	{
		// 정렬할 범위가 2개 이상인 경우
		if(left<right)
		{
			// pivot을 설정하여 정렬할 배열을 분할
			int pivot = partition(arr, left, right);
			
			// pivot은 제외한 2개의 부분 리스트를 대상으로 순환 호출
			sort(arr, left, pivot-1);	// pivot의 왼쪽을 정렬 (정복)
			sort(arr, pivot+1, right);	// pivot의 오른쪽을 정렬 (정복)
		}
	}
	
	public static void main(String[] args)
	{
		int[] arr = {5,1,3,8,9,4,2,7,10,6};
		System.out.println(Arrays.toString(arr));
		sort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
}

Output
[5,1,3,8,9,4,2,7,10,6]
[1,2,3,4,5,6,7,8,9,10]

 

6. 퀵 정렬 알고리즘의 특징

장점

• 속도가 빠릅니다. 시간복잡도가 O(n log₂n)을 가집니다.
• 추가 메모리 공간을 필요로 하지 않습니다. O(log₂n)만큼의 메모리 공간을 필요로 합니다.

단점

• 이미 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 걸리게 됩니다. 시간복잡도로 O(n²)이 소요됩니다.

이미 정렬된 리스트에 대해서 수행시간이 오래 걸리는 것을 방지하기 위하여 피벗을 선택시 기존 리스트의 첫번째 요소를 피벗으로 정하는 것이 아닌 리스트에서 중간값(medium)을 피벗으로 선택하는 방법도 존재합니다.

 

7. 퀵 정렬의 시간복잡도

퀵 정렬의 최선과 평균의 경우 퀵정렬의 순환호출의 횟수 * 각 순환호출 단계의 비교연산의 결과로 계산됩니다. 순환호출의 횟수는 데이터가 절반씩 줄어들므로 log₂n번입니다. 각 순환호출 단계에서는 전체 리스트의 레코드를 전부 비교해야므로 평균 n번 정도가 걸리게 됩니다.

 

퀵 정렬 최선 or 평균의 경우 = 순환 호출의 횟수(log₂n) * 각 순환 호출 단계의 비교연산(n) = n log₂n

 

퀵 정렬의 최악의 경우는 이미 데이터가 정렬되어 있는 경우입니다. 이때 퀵 정렬의 순환호출은 n번 발생합니다. 그리고 최선과 평균의 경우와 마찬가지로 각 순환호출 단게에서는 전체 리스트의 레코드를 전부 비교해야 하므로 평균 n번정도 걸리게 됩니다.

 

퀵 정렬 최악의 경우 = 순환 호출의 횟수(n) * 각 순환 호출 단계의 비교 연산(n) = n²

 

• Worst Case : O(n²)
• Average Case : 𝜣(n log₂n)
• Best Case : Ω (n log₂n)

 

References

source code : https://github.com/yonghwankim-dev/DataStruct
[알고리즘] 퀵 정렬(Quick Sort)이란
[부스트코스] 자바로 구현하고 배우는 자료구조