[Algorithm] 퀵 정렬

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 퀵 정렬

정의

- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나

- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터 (Pivot)로 설정한다

방식

1. 피벗의 값을 설정한다 (대부분 첫 번째 데이터를 기준으로 함)

2. 왼쪽에서부터 피벗보다 큰 데이터를 고르고, 오른쪽에서부터는 피벗보다 작은 데이터를 고른다

3. 위치가 엇갈리는 경우 (왼쪽과 오른쪽으로 접근하다가 왼쪽에서 선택한 값이 오른쪽이 되고, 오른쪽에서 선택한 값이 왼쪽이 되는 경우) 피벗과 작은 데이터의 위치를 서로 변경한다

4. 분할 완료 후 다시 반으로 나눈 데이터들에 대해 퀵 정렬을 수행해준다

 

- 재귀적으로 수행됨

- 정렬을 위한 범위가 점점 좁아지는 형태로 동작

시간 복잡도

- O(NlogN)

- 최악의 경우 O(N^2)의 시간 복잡도를 가진다

- ex) 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열인 경우

- 라이브러리에서는 NlogN의 시간 복잡도를 보장한다

public class Main {
	public static void quickSort(int[] arr, int start, int end) {
    	if (start >= end) return; // 원소가 한 개인 경우 종료
        int pivot = start; // 피벗을 첫 번째 원소로 설정
        int left = start + 1;
        int right = end;
        while (left <= right) {
        	// 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) left++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
            	int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            }
            // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            else {
            	int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        // 재귀 함수
        quickSort(arr, start, right)-1;
        quickSort(arr, right+1, end);
    }
    
    public static void main(String[] args) {
    	int n=10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        
        quickSort(arr, 0, n-1);
    }
}