에스알닷컴

퀵 정렬(Quick Sort)

• Divide and Conquer 알고리즘
• 하나의 문제를 작은 문제로 분할하여 해결해나가는 패러다임
• 재귀 알고리즘을 사용
• 안정적인 알고리즘은 아님

코드 설계

• Pivot이라는 값을 기준으로 파티셔닝(피벗을 선택하고 재정렬하는 프로세스)작업을 한다.

• Pivot을 기준으로 좌측에는 pivot보다 작은 값, 우측에는 보다 큰 값을 놓는다.

• Pivot을 기준으로 양쪽의 두 배열(세그먼트)들은 하위 문제로 놓고 재귀를 통해 다시 pivot 작업을 수행

• peudo-code

QuickSort(A, start, end) {
    if(start < end) {
        pIndex <- partition(A, start, end) // 파티션 작업 & pivot index 설정
        QuickSort(A, start, pIndex - 1) // 분할 작업
        QuickSort(A, pIndex + 1, end)
    }
}
partition(A, start, end) {
    pivot <- A[end]
    pIndex <- start
    for i <- start to end -1 {
        if (A[i] <= pivot) {
            swap(A[i], A[pIndex])
            pIndex <- pIndex + 1
        }
    }
    swap(A[pIndex], A[end])
    return pIndex
}

코드 구현

    /**
     * 1. pivot 설정
     * 2. partition 작업
     * 3. 분할 정복
     * @param A
     * @param start
     * @param end
     */
    private void quickSort(int[] A, int start, int end) {
        if (start < end) {
            int pIndex = partition(A, start, end);
            quickSort(A, start, pIndex - 1);
            quickSort(A, pIndex + 1, end);
        }
    }
    /**
     * 파티션 나누기
     * @param A
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] A, int start, int end) {
        int pivot = A[end];
        int pIndex = start;

        for (int i = start; i < end; i++) {
            if (A[i] <= pivot) {
                // pivot 값보다 작거나 같은 경우 swap
                int tmp = A[i];
                A[i] = A[pIndex];
                A[pIndex] = tmp;

                pIndex++;
            }
        }
        // pivot 값을 센터로 이동
        int tmp = A[pIndex];
        A[pIndex] = A[end];
        A[end] = tmp;

        return pIndex;
    }

• 과정 출력

Pivot( 4 ) 값 설정 후 파티션 나누기: 
7    2    1    6    8    5    3    4    
2    7    1    6    8    5    3    4    
2    1    7    6    8    5    3    4    
2    1    3    6    8    5    7    4    
파티션 과정 완료 후 Pivot(4) 이동
2    1    3    4    8    5    7    6    

Pivot( 3 ) 값 설정 후 파티션 나누기: 
2    1    3    4    8    5    7    6    
2    1    3    4    8    5    7    6    
2    1    3    4    8    5    7    6    
파티션 과정 완료 후 Pivot(3) 이동
2    1    3    4    8    5    7    6    

Pivot( 1 ) 값 설정 후 파티션 나누기: 
2    1    3    4    8    5    7    6    
파티션 과정 완료 후 Pivot(1) 이동
1    2    3    4    8    5    7    6    

Pivot( 6 ) 값 설정 후 파티션 나누기: 
1    2    3    4    8    5    7    6    
1    2    3    4    5    8    7    6    
파티션 과정 완료 후 Pivot(6) 이동
1    2    3    4    5    6    7    8    

Pivot( 8 ) 값 설정 후 파티션 나누기: 
1    2    3    4    5    6    7    8    
1    2    3    4    5    6    7    8    
파티션 과정 완료 후 Pivot(8) 이동
1    2    3    4    5    6    7    8    

분석

• 복잡도 분석
  • Best & Average case O(nlogn)
  • Worst case O(n^2)
• O(n^2) 임에도 적절하게 빠른 정렬

병합정렬(Merge Sort)

• 선택, 버블, 삽입 정렬보다 빠른 알고리즘
• Divide and Conquer 전략을 활용하는 알고리즘
• 분할 할 때, 배열이 절반으로 줄어들어 시간 복잡도는 O(logN)
• 합병 할 때, 모든 값을 비교해야 하기 때문에 시간 복잡도는 O(N)
• 두 개의 배열을 병합할 때 병합 결과를 담을 배열이 추가적으로 필요 (Space complexity: Not in-place)
• 최악의 경우 O(nlogn)인 알고리즘
• 재귀에 대한 이해가 있어야 한다.

코드 설계

• 하나의 큰 문제를 두 개의 작은 문제로 분할
• 더 이상 나눌 수 없을 때 병합
• 병합 시 정렬을 하면서 병합하여 정렬을 완성

0: 2 4 1 6 8 5 3 7

1: 2 4 1 6        8 5 3 7

2: 2 4        ||        1 6        ||        8 5        ||        3 7

3: 2    ||    4    ||    1    ||    6    ||    8    ||    5    ||    3    ||    7

4: 2 4        ||        1 6        ||        5 8     ||        3 7

5: 1 2 4 6        ||        3 5 7 8

6: 1 2 3 4 5 6 7 8

• pseudo-code

Merge(L, R, A) {
    nL <- length(L)
    nR <- length(R)
    i <- 0, j <- 0, k <- 0
    while(i < nL && j < nR) {
        if( L[i] <= R[j] ) {
            A[k] <- L[i]
            i <- i + 1
        } else {
            A[k] <- R[j]
            j <- j + 1
        }
        k <- k + 1
    }
    while(i < nL) {
        A[k] <- L[i]
        i <- i + 1
        k <- k + 1
    }
    while(j < nR) {
        A[k] <- R[j]
        j <- j + 1
        k <- k + 1
    }
}    
MergeSort(A) {    
    n <- length(A)
    // 기저조건: 더 이상 나눌 수 없는 배열의 길이인 경우
    if (n < 2) return
    mid <- n / 2

    left <- array.size(mid)
    right <- array.size(n - mid)

    for i <- 0 to mid - 1
        left[i] <- A[i]
    for i <- mid to n - 1
        right[i - mid] <- A[i]

    MergeSort(left)
    MergeSort(right)
    Merge(left, right, A)    
}

코드 구현

    public void mergeSort(int[] A) {
        int n = A.length;
        if (n < 2) return; // 배열의 요소가 1개인 경우 리턴

        int mid = n / 2; // 배열의 중간 요소

        int[] left = new int[mid]; // 좌측 배열
        int[] right = new int[n - mid]; // 우측 배열

        for (int i = 0; i < mid; i++) {
            left[i] = A[i];
        }
        for (int i = mid; i < n; i++) {
            right[i - mid] = A[i];
        }
        mergeSort(left);
        mergeSort(right);
        merge(left, right, A);
    }

    private void merge(int[] L, int[] R, int[] A) {
        int nL = L.length;
        int nR = R.length;

        int i = 0 , j = 0 , k = 0;

        while(i < nL && j < nR) {
            if(L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }
        while(i < nL) { // L 배열에 A에 넣지 않은 여분이 있는 경우 
            A[k] = L[i];
            i++;
            k++;
        }
        while(j < nR) { // R 배열에 A에 넣지 않은 여분이 있는 경우 
            A[k] = R[j];
            j++;
            k++;
        }
        // 과정 출력
    }

• 과정 출력 (병합되는 과정에 출력)

2    4    
1    6    
1    2    4    6    
5    8    
3    7    
3    5    7    8    
1    2    3    4    5    6    7    8    

분석

• 복잡도 분석
  • 순환 호출의 깊이: k = logN
  • 각 합병 단계의 비교 연산: 최대 N번
  • 순환 호출의 깊이 만큼 합병 단계 * 각 합병 단계의 비교연산: O(N * logN)
• 공간 복잡도
  • 공간의 소비는 목록의 요소의 수에 비례한다.

삽입정렬(Insertion Sort)

• 임의 값을 적절한 자리에 삽입하여 정렬하는 방식

코드 설계

• 배열의 가장 왼쪽부터 정렬한다는 기준을 잡기
• 변경 전 값을 기준 값과 비교하여 적절한 위치로 변경

코드 구현

    private int[] insertionSort(int[] A, int n) {
        int[] ret;

        for(int i = 1 ; i < n ; i++) {
            int value = A[i]; // 배열의 두 번째 값을 기준으로 시작
            int hole = i;

            while(hole > 0 && (A[hole-1] > value)) { // A[0] > A[1] 부터 비교하기를 시작
                // 과정 출력 not swap
                A[hole] = A[hole - 1];
                hole--;

            }
            A[hole] = value;
            // 과정 출력 swap
        }

        ret = A;
        return ret;
    }

• 과정

1:    2    7    4    1    5    3    : 1    

2:    2    7    4    1    5    3    : 2    
2:    2    4    7    1    5    3    : 1    

3:    2    4    7    1    5    3    : 3    
3:    2    4    7    7    5    3    : 2    
3:    2    4    4    7    5    3    : 1    
3:    1    2    4    7    5    3    : 0    

4:    1    2    4    7    5    3    : 4    
4:    1    2    4    5    7    3    : 3    

5:    1    2    4    5    7    3    : 5    
5:    1    2    4    5    7    7    : 4    
5:    1    2    4    5    5    7    : 3    
5:    1    2    3    4    5    7    : 2    

• 결과 확인

    int[] A = {2, 7, 4, 1, 5, 3};
    int[] except = {1, 2, 3, 4, 5, 7};
    int n = A.length;

    @Test
    public void testInsert() {
        assertThat(insertionSort(A, n), is(except));
    }

분석

• 복잡도 분석
  • Bast-Case O(n)
  • Average-Case O(n^2)
  • Worst-Case O(n^2)
• 삽입 정렬은 선택정렬, 버블정렬보다 효율적인 알고리즘이다.
• 직관적인 알고리즘

버블 정렬

코드 설계

• 배열의 왼쪽에서 오른쪽으로 여러번 스캔
• 스캔 시 인접한 배열의 값과 비교하여 인덱스가 큰 배열의 요소 값보다 인덱스 값이 작은 배열의 요소의 값이 클 경우 위치를 바꾼다.

* 2, 7, 4, 1, 5, 3
1차 -> 2, 4, 1, 5, 3, 7
2차 -> 2, 1, 4, 3, 5, 7
3차 -> 1, 2, 3, 4, 5, 7

// pseudo-code
BubbleSort(A, n) {
    for k <- 1 to n-1 {
        for i <- 0 to n-2 {
            if( A[i] > A[i+1]) {
                swap(A[i], A[i+1])
            }
        }
    }
}

// pseudo-code
BubbleSort(A, n) {
    for k <- 1 to n-1 {
        flag <- 0
        for i <- 0 to n-k {
            if( A[i] > A[i+1]) {
                swap(A[i], A[i+1])
                flag <- 1
            }
        }
        if (flag == 0) break
    }
}

코드 구현

public int[] bubbleSort(int[] A, int n) {
    int[] ret;

    for(int k = 1 ; k < n ; k++) { // 1 ~ n - 1 까지 
        for(int i = 0 ; i < n - 1 ; i++) { // 0부터 n - 2 까지
            if(A[i] > A[i+1]) {

                int tmp = A[i];
                A[i] = A[i+1];
                A[i+1] = tmp;
                // 과정 출력
            }
        }
    }

    ret = A;
    return ret;
}

• 과정

0:     2    7    4    1    5    3    
1:     2    4    7    1    5    3    
2:     2    4    1    7    5    3    
3:     2    4    1    5    7    3    
4:     2    4    1    5    3    7    

0:     2    4    1    5    3    7    
1:     2    1    4    5    3    7    
2:     2    1    4    5    3    7    
3:     2    1    4    3    5    7    
4:     2    1    4    3    5    7    

0:     1    2    4    3    5    7    
1:     1    2    4    3    5    7    
2:     1    2    3    4    5    7    
3:     1    2    3    4    5    7    
4:     1    2    3    4    5    7    

0:     1    2    3    4    5    7    
1:     1    2    3    4    5    7    
2:     1    2    3    4    5    7    
3:     1    2    3    4    5    7    
4:     1    2    3    4    5    7    

0:     1    2    3    4    5    7    
1:     1    2    3    4    5    7    
2:     1    2    3    4    5    7    
3:     1    2    3    4    5    7    
4:     1    2    3    4    5    7    

• swap이 없는 경우 loop에서 벗어나는 flag 설정

    public int[] bubbleSort1(int[] A, int n) {
        int[] ret;
        boolean flag = false;

        for(int k = 1 ; k < n ; k++) { // 1 ~ n - 1 까지 
            flag = false;

            for(int i = 0 ; i < n - k ; i++) { // 0부터 n - k 까지
                if(A[i] > A[i+1]) {

                    int tmp = A[i];
                    A[i] = A[i+1];
                    A[i+1] = tmp;

                    flag = true;
                    // 과정 출력
                }
            }
            if(!flag) break;

        }

        ret = A;
        return ret;
    }

• 과정

1:     2    4    7    1    5    3    
2:     2    4    1    7    5    3    
3:     2    4    1    5    7    3    
4:     2    4    1    5    3    7    

1:     2    1    4    5    3    7    
3:     2    1    4    3    5    7    

0:     1    2    4    3    5    7    
2:     1    2    3    4    5    7

• 결과 확인 테스트

    int[] A = {2, 7, 4, 1, 5, 3};
    int n = A.length;

    @Test
    public void testBubble() {
        int[] except = {1, 2, 3, 4, 5, 7};
        assertThat(bubbleSort(A, n), is(except));
    }

    @Test
    public void testBubble1() {
        int[] except = {1, 2, 3, 4, 5, 7};
        assertThat(bubbleSort1(A, n), is(except));
    }

분석

• 복잡도 분석
  • Bast-Case O(n)
  • Average-Case O(n^2)
  • Worst-Case O(n^2)
• 선택 정렬만큼 우수하지만 마찬가지로 느린 정렬 방식

선택 정렬

• 가장 간단한 정렬 알고리즘
• 가장 직관적인 알고리즘

코드 설계하기

• 목표: 가장 작은 값을 선택하여 자리 바꾸기
  1. 모든 카드를 A에 보관하기
  2. 가장 작은 값의 카드를 선택하여 B에 보관
  3. 2를 반복

// pseudo-code
SelectionSort(A, n) {
    for i <- to n-2 {
        min <- i
        for j <- i+1 to n-1 {
            if(A[j] < A[min]) {
                min <- j
            }
        }
        tmp <- A[i]
        A[i] <- A[min]
        A[min] <- tmp
    }
}

코드 구현

    /**
     * 선택 정렬
     * @param A 정수로 이루어진 배열
     * @param n 배열의 길이
     * @return
     */
    private int[] selectionSort(int[] A, int n) {
        int[] ret;

        for (int i = 0; i < n - 1; i++) { // 0 ~ n-2 까지 반복 (배열의 마지막 전까지)
            int min = i;
            for (int j = i + 1; j < n; j++) { // 1 ~ n-1 까지 반복 (배열의 마지막 까지)
                if (A[j] < A[min]) {
                    min = j;
                }
            }
            int tmp = A[i];
            A[i] = A[min];
            A[min] = tmp;
        }

        ret = A;
        return ret;
    }

• 과정

0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    

0:     1    7    4    2    5    3    swap
1:     1    7    4    2    5    3    
1:     1    7    4    2    5    3    
1:     1    7    4    2    5    3    
1:     1    7    4    2    5    3    

1:     1    2    4    7    5    3    swap
2:     1    2    4    7    5    3    
2:     1    2    4    7    5    3    
2:     1    2    4    7    5    3    

2:     1    2    3    7    5    4    swap
3:     1    2    3    7    5    4    
3:     1    2    3    7    5    4    

3:     1    2    3    4    5    7    swap
4:     1    2    3    4    5    7    

4:     1    2    3    4    5    7    

분석

• 복잡성 분석
  • O(n^2)
• 선택정렬은 느린 알고리즘에 속함