[알고리즘] 퀵정렬

안녕하세요 ki입니다.

오늘 공부 내용은 퀵정렬입니다.

지난 글에서는 시간복잡도에 대해 알아보았습니다.

그중 O(n log n)인 퀵정렬을 공부를 해봤습니다.

2024.06.12 - [MIG/알고리즘] - [알고리즘] 시간 복잡도를 알아보자

[알고리즘] 시간 복잡도를 알아보자

 

QuickSort

• 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘
• 평균적으로 매우 빠르고, 실제로 많이 사용되는 정렬 알고리즘

 

시간 복잡도

평균적으로 O(n log n)이지만 최악의 경우 O(n^2)의 시간복잡도를 가집니다

 

 

퀵정렬 과정

1. 피벗 선택 : 배열에 중간 값을 선택하여 피벗 값을 선택
2. 파티션분할 : 선택한 피벗을 기준으로 왼쪽( 피벗보다 작은 값) 오른쪽 (피벗보단 큰 값)으로 파티션 분할
3. 정렬 : 분할한 파티션끼리 정렬 

유투브 엔지니어 대한민국 퀵정렬에 대해 알아보고 자바로 구현하기 중 (https://youtu.be/7BDzle2n47c?si=Xv5CScgjQM7ARaUz)

 

 

최악의 경우 O(n^2)가 되는 경우

피벗을 정하는 과정에서 선택된 값이 가장 큰 값이나 가장 작은 값이 연속적으로 선택될 경우 발생

 

 

 

https://yongdanielliang.github.io/animation/web/QuickSortNew.html

Quick Sort Animation by Y. Daniel Liang

(위 사이트는 퀵정렬에 과정을 이해 할 수 있도록 테스트가 가능합니다.!)

 

자바코드로 구현하기

ublic class Main {

    private static void quickSort(int[] arr){
        quickSort(arr, 0, arr.length-1);
    }
    private static void quickSort(int[] arr,int start, int end){
        int part2 = partition(arr, start, end);
        // 왼쪽 파티션
        // 왼쪽 파티션 시작점 보다 1개 이상 차이 나야 정렬
        // 시작점 <오른쪽 파티션 시작점 -1 (바로전)
        if(start < part2 -1){
            // quickSort ( 배열 , 시작 , 오른쪽 파티션 시작점 -1 (바로전) )
            quickSort(arr, start,part2-1);
        }
        // 오른쪽 파티션
        // 오른쪽 파티션 시작점 보다 마지막 배열 보다 작은 경우 정렬
        if (part2 < end){
            quickSort(arr, part2, end);
        }
    }

    private static int partition(int[] arr, int start, int end) {
        // pivot은 배열의 중간값이라서 시작점 + 끝점 /2 로 계산
        int pivot = arr[(start + end)/2];
        // 시작점이 끝지점보다 작거나 같은 동안만 실행
        while (start <=end){
            // 시작점 -> pivot 보다 작으면 한칸씩 이동 but 크면 자리에서 멈춤
            while (arr[start] < pivot) start++;
            // 끝점 -> pivot 보다 크면 한칸씩 이동 but 크면 자리에서 멈춤
            while (arr[end] > pivot) end--;
            // 시작점이 끝지점보다 작거나 같은지 확인
            if(start <= end){
                // true면 스왑
                swap(arr,start,end);
                // 스왑 후 이동
                start++;
                end--;
            }
        }
        // 새로 나눌 오른쪽 파티션에 첫번쨰 인댁스가 start에 입력됨
        return start;
    }
	
    // 자리 바꾸기
    private static void swap(int[] arr, int start, int end) {
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }
    
    // 출력
    private static void printArray(int[] arr){
        for(int data : arr){
            System.out.print(data + ",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int [] arr = {3,9,4,7,5,0,1,6,8,2};
        printArray(arr);
        quickSort(arr);
        printArray(arr);
    }
}

 

 

 

참고

https://www.youtube.com/watch?v=7BDzle2n47c&t=418s

https://commons.wikimedia.org/wiki/File:Quicksort-example.gif

File:Quicksort-example.gif - Wikimedia Commons