퀵 정렬 (Quick Sort)

특징

• 임의의 기준 값(pivot)을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식
• O(n^2) - pivot이 최소값 또는 최대값으로 지정되는 최악의 경우
• pivot 정하는 방법
  1) 중간에 있는 값
  2) 왼쪽 끝에 값
  3) 오른쪽 끝에 값
  4) 위에 3개 값을 뽑은 후 크기가 중간인 값

정렬 과정

• 왼쪽 i는 pivot보다 큰 값을 찾고, 오른쪽 j는 pivot보다 작은 값을 찾는다
• i와 j가 만나면 종료하고, 그 만난 위치의 값과 pivot값을 교체한다.
  
• 교체된 이전의 pivot값을 고정해놓고, 그 값을 기준으로 나눠서 다시 이전의 과정을 반복한다
  

소스코드

// 퀵 정렬

import java.util.Arrays;

public class Main3 {

    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        
        // 분할
        int pivot = partition(arr, left, right);
        
        // 기준값 중심으로 좌우 재귀 호출
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    //정렬을 실행하고 고정된 pivot을 반환해주는 메소드
    public static int partition(int[] arr, int left, int right) {
        // 가장 좌측 값을 기준값으로 설정
        // 이외에 기준 값은 배열에서 중간에 있는 값을 고르거나, 임의의 수를 3개 선정 후 중앙 값을 고르는 등의 방법이 있음
        int pivot = arr[left];
        int i = left;
        int j = right;

        while(i < j) {  //i와 j가 만나기 전까지
            while (arr[j] > pivot && i < j) {   //arr[j]가 pivot보다 작은 값을 찾을 때까지 탐색
                j--;
            }

            while(arr[i] <= pivot && i < j) {   //arr[i]가 pivot보다 큰 값을 찾을 때까지 탐색
                i++;
            }

            swap(arr, i, j);    //위의 과정에서 각각 찾는 값이 나오면 교체
        }
        swap(arr, left, i); //i와 j가 만났으면 pivot과 i값을 교체

        return i;   //pivot과 교체된 값을 반환
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("퀵 정렬: " + Arrays.toString(arr));
    }
}