[알고리즘] 퀵 정렬(quick sort)

정렬을 배우기 시작했다. 버블정렬, 선택정렬, 삽입정렬, 기수정렬, 병합정렬 등 다양한 정렬을 배웠다. (병합정렬이 가장 어려웠음)

 

코딩테스트 오픈카톡방에서 고수들끼리 하는 퀵 소트를 배울 차례가 됐다. 아무리 읽어도 도~저히 이해가 안되는것이다.

 

그러던중 유튜브에서 좋은 알고리즘 해석영상을 찾고 바로 이해가 되었다.

https://www.youtube.com/watch?v=cWH49IKDIiI&ab_channel=%EC%BD%94%EB%94%A9%ED%95%98%EB%8A%94%EA%B1%B0%EB%8B%88 

 

내가 이해한 퀵소트는 다음 순서를 따른다.

 

1. pivot을잡는다. pivot이란 퀵소트에서 가장 중요한 개념으로, 쉽게말하면 기준을 잡는것이다. 위 영상과 코드트리에서는 배열 제일 마지막값을 pivot으로 선택했다.
2. 포인터를 두개를 사용해 배열의 앞에서 부터 탐색한다. 
   포인터 하나(i)는 배열의 첫 index-1상태에서 대기하고, 포인터 하나(j)는 첫 index부터 끝값 보다 하나 앞에까지 탐색한다.(끝값은 pivot이기 때문)
3. 배열을 탐색하며 만약 두번째 포인터가 가르키는 값(arr[j])이 pivot보다 작다면, 해당값은 배열내에서 pivot보다 왼쪽에 존재해야 하기 때문에 i값을 하나 증가시키고 arr[i]와 arr[j]를 swap한다.
4. i를 왜 -1에 놓고 하나 증가시킨다음에 그 값과 swap하는지에 대해서 설명하자면 pivot보다 작은값을 왼쪽부터 채우기 위해서다. 이 개념을 이해하고부터는 이해가 쉬웠다.
5. j가 탐색을끝내고 끝값 바로전까지 도달을 했을때, i가 가르키고 있는곳은 배열내에서 pivot보다 작은 마지막 값이다.
6. i+1과 pivot을 교체해 준다면? -> pivot을 기준으로 배열의 왼쪽은 pivot보다 작은값, 오른쪽은 pivot보다 큰 값으로 정렬된다.
7. 이 다음에는 재귀적 개념이 필요하다. 첫번째 메소드를 끝으로 pivot의 위치를 확정했다. 그 다음은 해당 메소드에
   (첫값, pivot-1), (pivot+1, 끝값)을 재귀하여 탐색한다!!

내 코드

import java.util.*;

public class Main {
    static int n;
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        //맨 처음 퀵소트를 실행한다. 처음부터 끝까지
        quickSort(0, n-1);
        for(int number : arr){
            System.out.print(number + " ");
        }
    }

    static void quickSort(int low, int high){
        //재귀의 종료 시점을 지정해준다. 
        if(low < high){
            int pivot = getPivot(low, high);
            quickSort(low, pivot-1);
            quickSort(pivot+1, high);
        }
    }

    static int getPivot(int low, int high){
        //맨 왼쪽값의 인덱스보다 하나 왼쪽으로 지정해준다.
        //그렇게 해야 맨 왼쪽부터 pivot보다 작은값을 채울 수 있다.
        int i = low-1;

        for(int j = low; j <= high-1; j++){
            //pivot보다 작다면?? i를 하나 증가시켜서 맨 왼쪽부터 해당값을 채운다.
            if(arr[j] < arr[high]){
                i++;
                swap(i, j);
            }
        }

        //i는 현재 pivot보다 작은 마지막값으로 더이상 pivot보다 작은 값이 없다.
        //그러므로 i+1과 pivot을 바꿔준다면 pivot을 기준으로 왼쪽에는 작은값, 오른쪽에는 큰값이 위치한다.
        swap(i+1, high);

        //현재 pivot의 위치를 return한다.
        return i+1;
    }

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

 

---

처음해봐서 조금 어려웠지만 금방 이해가 돼서 다행이다. 정렬은 참 머리가 복잡해진다. 시간복잡도도 이해가 잘 안되는데,, 해당 챕터는 여러번 반복숙달해야겠다.

 

 

나도 이제 퀵소트 할줄안다~