[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 빠른 정렬 (quick sort)

빠른 정렬 (quick sort)

 

 

지난 시간 합병 정렬에 대해 배웠다.

https://rookie-programmer.tistory.com/54

[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 합병 정렬 (merge sort)

 

 

이번 시간에는 빠른 정렬(quick sort)에 대해 배운다.

강의에서는 pivot을 맨 오른쪽 값으로 정했지만, pivot 값을 정하는 여러 가지 방법이 있다.

 

 

퀵 정렬은 합병 정렬과 마찬가지로 분할정복법(Divide and Conquer)을 사용한다.

퀵 정렬의 핵심은 기준이 되는 값 pivot을 정해 pivot 보다 작은 데이터, pivot 보다 큰 데이터로 나누는 것이다.

해당 수업에서는 pivot 값을 배열의 맨 오른쪽 값으로 매번 설정해주며, 이 동작을 반복하다 보면 값들이 오름차순으로 정렬된다.

partition 함수는 pivot 값을 기준으로 좌, 우로 자기보다 작은 값, 큰 값을 나열하고

pivot 값을 두 집단의 경계가 되는 곳으로 옮겼을 때의 pivot값의 위치를 반환한다.

반환한 pivot 위치 값을 기준으로 나눠진 좌, 우 배열에 대해 이 과정을 반복한다.

 

 

 

 

 

partition 하는 과정 ⭐⭐⭐⭐⭐

지금 검사하려는 값이 x(pivot 값)보다 크다면 다음 값으로 넘어가고 (i기준으로 오른쪽 값들은 모두 x보다 큰 값들이기 때문에 단순히 j+1으로 다음 배열로 넘어가는 것이 x의 오른쪽에 두는 것이 됨)

검사하려는 값이 x보다 작다면 i를 1 증가시켜, i 위치에 있는 값과 j 위치에 있는 값을 바꿔준다.

i+1 위치는 x보다 작은 값들 중 가장 오른쪽 값이 될 것이고, 원래 i+1에 있던 값은 j 위치에 오면서 'x보다 큰 값'이라는 사실이 유지된다.

n-1개의 데이터에 대해 정렬이 끝나면 pivot 값을 두 개의 partitioin 사이에 넣어준다.

 

 

x보다 작은 값, x보다 큰 값으로 나눈 후 x의 위치를 찾아주는 과정까지 나타낸 그림

 

 

 

 

partition 함수의 동작을 i, j값을 하나씩 옮겨가며 이해해보자.

위 그림의 마지막에서 pivot 값 15를 기준으로 0~i까지는 작은 값, i+1~j-1까지는 큰 값으로 모두 나뉜 것을 볼 수 있다.

이때 pivot 값은 이 두 집단의 사이, 즉 i+1 위치에 넣어줌으로써 알맞은 pivot 위치를 찾아줄 수 있다.

 

 

 

 

 

 

 

Partition의 sudo code

 

 

 

 

* 퀵 정렬의 시간복잡도

최악의 경우 : O(n^2)

 

 

최선의 경우 : O(n logn)

 

 

평균의 경우 : O(n logn)

 

 

* 퀵 정렬 자바 코드 ( quick sort java code )

import java.util.Arrays;

public class sort {
    public static void quickSort(int[] a, int p, int r) {
        if(p<r) {
            int q = partition(a, p, r);
            System.out.println(Arrays.toString(a));
            quickSort(a, p, q-1);
            quickSort(a, q+1, r);

        }
    }
    public static int partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p-1;
        for (int j = p; j < r; j++) {
            if(a[j] < x) {
                i++;
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        int tmp = a[i+1];
        a[i+1] = a[r];
        a[r] = tmp;

        return i+1;
    }

    public static void main(String[] args) {
        int[] a = new int[]{4, 9, 2, 6, 8, 5, 7, 1, 3};
        quickSort(a, 0, a.length-1);
    }
}

결과