24/02/12 [버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 합병정렬, 힙정렬]

Radix Sort, Shell Sort, Tim Sort 를 제외한 정렬을 설명, 코드, 그림으로 정리했습니다. 

최대한 이해하기 쉽게 정리했으니깐 참고하실 분은 참고하셔도 좋을 것 같습니다.

 

1. 버블정렬 (AVG, WORST : O(n^2))

바로 옆에 붙은 두 인덱스를 서로 비교

오름차순 기준이라면 두 요소를 비교할 때 큰 요소를 뒤로, 작은 요소를 앞으로 배치

이렇게 배치하다보면 결국 한 번의 순환이 끝날 때에는 가장 큰 요소가 배열의 끝에 존재하게 됨 (끌고가는 식)

다음 순환부터는 요소의 갯수를 1개씩 줄이며 위 과정 반복

for(int i = 0 ; i < n - 1 ; i ++) {
    boolean change = false;
    for(int j = 0 ; j < n - 1 - i ; j ++){
        if(arr[j] > arr[j + 1]) {
            change = true;
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    if(change == false) break;
}

 

 

2. 선택정렬 (AVG, WORST : O(n^2))

처음 인덱스부터 마지막 인덱스까지 순환

만약 처음 인덱스보다 (가장) 작은 요소를 발견하면 해당 요소를 서로 교환

그리고 인덱스를 1 증가하여 다음 인덱스부터 마지막 인덱스까지 순환하며 위 과정 반복

for(int i = 0 ; i < n - 1 ; i ++) {
    int min_index = i;
    for(int j = i + 1 ; j < n ; j ++) {
        if(arr[min_index] > arr[j]) {
            min_index = j;
        }
    }
    int temp = arr[min_index];
    arr[min_index] = arr[i];
    arr[i] = temp;
}

3. 삽입정렬 (AVG, WORST : O(n^2))

Collections.sort() 가 사용하는 방식

최악의 경우 : 합병 정렬

최선의 경우 : 삽입 정렬

 

std 가 들어갈 자리를 찾기 위해 j-1 을 j 로 밀어내는 방식 (서로 교환하는게 아니라는 것에 주의)

std 바로 앞이 j 이고, j 바로 앞이 j-1 으로 생각하면 편함

 

조건 1) j=0 라면, j에 std 삽입

조건 2) std 왼쪽에 std 보다 작은 수가 위치한다면, j에 std 삽입

조건 3) std 왼쪽에 std 보다 작은 수가 위치하지 않다면, j-1 를 j 로 이동

for(int i = 1 ; i < n ; i ++) {
    int std = arr[i];
    for(int j = i ; j >= 0 ; j --) {
        if(j == 0) {
            arr[0] = std;
        }else if(arr[j - 1] <= std) {
            arr[j] = std;
            break;
        } else {
            arr[j] = arr[j - 1];
        }
    }
}

4. 퀵정렬 (AVG : O(nlogn), WORST : O(n^2))

Arrays.sort() 가 사용하는 방식

 

Pivot 을 정하고 

Left 가 Right 를 지나치지 않는 한,

Pivot 보다 큰 Left 를 발견할 때까지 Left 는 인덱스 하나씩 증가

Pivot 보다 작은 Right 를 발견할 때까지 Right 는 인덱스 하나씩 감소

Left, Right 가 멈춘 지점에서 Left, Right 서로 교환

만약 Left 가 Right 를 지나쳤다면 Pivot 을 기점으로 배열을 (논리적으로) 쪼개고 각 배열에 대해 위 과정을 반복

public static void quickSort(int Start, int End) {
    if(Start >= End) { return; }

    int pivot = arr[ ( Start + End ) / 2 ];
     int Left = Start;
    int Right = End;

    while(Left <= Right) {
        while(arr[Left] < pivot) Left ++;
        while(arr[Right] > pivot) Right --;

        if(Left <= Right) {
            int temp = arr[Right];
            arr[Right] = arr[Left];
            arr[Left] = temp;
            Left ++;
            Right --;
        }
    }

    if(Start < Right) quickSort(Start, Right);
    if(Left < End) quickSort(Left, End);
}

 

5. 합병정렬 (AVG, WORST : O(nlogn))

Collections.sort() 가 사용하는 방식

최악의 경우 : 합병 정렬

최선의 경우 : 삽입 정렬

 

일단 배열을 인덱스 단위별로 논리적으로 다 쪼갬 (검정박스 단계까지)

논리적으로 쪼개진 배열을 합병하며 정렬함

 

정렬 기준은 아래와 같음

p(=left) 가 mid 를 넘어가지 않는 한,

q(=mid+1) 이 right 를 넘어가지 않는 한,

반복하는데,

조건 1) arr[p] (왼쪽 요소)가 arr[q] (오른쪽 요소)보다 작거나 같다면, 임시 배열 temp 에 arr[p] (왼쪽 요소) 넣고 p, idx 1씩 증가

조건 2) arr[p] (왼쪽 요소)가 arr[q] (오른쪽 요소)보다 크다면, 임시배열 temp 에 arr[q] (오른쪽 요소) 넣고 q, idx 1씩 증가

 

반복문이 끝났다면, mid, mid+1 을 기점으로 각각 왼쪽 또는 오른쪽 정렬이 끝났다는 의미인데, 정렬이 끝난 상태는 둘 중 하나이다.

조건 3) 왼쪽 인덱스 p(=left) 가 mid 를 넘어갔다면, 오른쪽 인덱스 q 부터 right 까지 순서대로 temp 에 저장

조건 4) 왼쪽 인덱스 p(=left) 가 mid 를 넘어가지 못했다면, 왼쪽 인덱스 p 부터 mid 까지 순서대로 temp 에 저장

 

4. temp 요소를 arr 에 옮기기 

public class MergeSort {

    public static int[] arr;
    public static int[] temp;

    public static void main(String[] args) {
        arr = new int[]{3,4,1,5,2,8,7,6};
        temp = new int[arr.length];

        mergeSort(0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }


    private static void mergeSort(int left, int right) {
        if (left < right) {
            //절반 나눠서 반절씩
            int mid = (left + right) / 2;        //중앙 인덱스
            mergeSort(left, mid);                //왼쪽 분할
            mergeSort(mid + 1, right);      //오른쪽 분할

            int p = left;       // 왼쪽배열 시작 인덱스
            int q = mid + 1;    // 오른쪽배열 시작 인덱스

            int idx = p;        // 임시배열 시작인덱스

            while (p <= mid && q <= right) {
                if (arr[p] <= arr[q]) { //왼쪽이 더 작을때
                    temp[idx++] = arr[p++]; //왼쪽 값 넣어주기
                }
                else { //오른쪽이 더 작을때
                    temp[idx++] = arr[q++]; //오른쪽 값 넣어주기
                }
            }

            if (p > mid) { // 왼쪽이 다 정렬된 경우 (p가 mid를 넘어간 경우)
                for (int i = q; i <= right; i++) {
                    temp[idx++] = arr[i]; // 오른쪽(q~right)을 idx에 삽입
                }
            } else { // 오른쪽이 다 정렬된 경우 (p가 mid를 넘어가지 않은 경우) * 이 때의 q는 out of range
                for (int i = p; i <= mid; i++) {
                    temp[idx++] = arr[i]; // 왼쪽(p~mid)을 idx에 삽입
                }
            }

            //임시배열 temp에 있는값 원래 arr배열에 넣어주기
            for (int i = left; i <= right; i++) {
                arr[i] = temp[i];
            }
        }
    }
}

6. 힙정렬 (AVG, WORST : O(nlogn))

노드는 이진트리 모양으로, 배열과는 다른 모양이지만

힙정렬에서는 이진트리 모양을 배열로 다루기 때문에

노드를 배열의 각 요소라고 생각하면 된다.

 

1. 최대힙 만들기 * 이 때 최대힙 만들 때 아래에서 위로 진행

 

가장 마지막 부모 노드부터 시작하는데,

    (1) 부모 노드 요소보다 더 (가장) 큰 자식 노드 요소가 있다면, 요소끼리 스왑하고 largestIdx, parentIdx 를 자식 노드 인덱스로 변경

        (2) 요소끼리 스왑했으므로 요소 대소 비교 다시 해야하므로 (1) 로 돌아가서 진행

    (3) 부모 노드 요소보다 더 큰 자식 노드 요소가 없다면, while 종료

(4) 만약 변경된 parentIdx 가 while 조건을 만족하지 못한다면 while 종료 

 

두번째 마지막 부모 노드, 세번째 마지막 부모 노드, ... 루트 노드까지 이어서 진행하며 모든 서브트리(삼각형)를 확인할 때까지 위 과정 반복

 

2. 정렬(스왑 후 최대힙 만들기) * 이 때 최대힙 만들 때 위에서 아래로 진행

루트 노드부터 시작하는데,

루트 노드의 요소와 마지막 노드의 요소를 스왑

마지막 노드의 요소가 가장 큰 수로 스왑되었으므로 해당 요소를 빼내어 배열 가장 마지막에 저장 (정렬)

 

이후 1 과정((1), (2), (3), (4))을 똑같이 반복하고

두번째 부모 노드, 세번째 부모 노드 ... 마지막 노드까지 이어서 진행하며 모든 서브트리(삼각형)를 확인할 때까지 위 과정 반복

public class HeapSort {

    static int[] arr = new int[]{3,7,8,4,2,5};

    public static void main(String[] args) {
        heapSort(arr, arr.length);
        Arrays.stream(arr).forEach(i -> System.out.print(i));
    }

    private static void heapSort(int[] arr, int size) {

        if(size < 2) {
            return;
        }

        // 가장 마지막 요소의 부모 인덱스
        // size - 1 : 가장 마지막 노드
        int parentIdx = getParent(size - 1);

        // 전체적으로 최대힙 만들기
        for(int i = parentIdx; i >= 0; i--) {
            heapify(arr, i, size - 1); // 이 때 heapify 는 아래에서 위로
        }

        // 정렬
        // size - 1 : 가장 마지막 노드
        for(int i = size - 1; i > 0; i--) {
            // 첫 노드를 마지막 노드로 대체하는 것으로 heapify 준비
            swap(arr, 0, i);
            // 대체된 첫 노드를 제외하는 의미로 i-1로 lastIdx 파라미터 설정하고 heapify 시작
            heapify(arr, 0, i - 1); // 이 때 heapify 는 위에서 아래로
        }
    }

    private static int getParent(int child) {
        return (child - 1) / 2;
    }

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

    // 하나의 삼각형에 대해서만 최대힙 만들기
    private static void heapify(int[] a, int parentIdx, int lastIdx) {

        int leftChildIdx;
        int rightChildIdx;
        int largestIdx;

        while((parentIdx * 2) + 1 <= lastIdx) {
            leftChildIdx = (parentIdx * 2) + 1;
            rightChildIdx = (parentIdx * 2) + 2;
            largestIdx = parentIdx;

            // 부모 노드(a[largestIdx])와 왼쪽 자식 노드를 비교
            if (a[leftChildIdx] > a[largestIdx]) {
                largestIdx = leftChildIdx;
            }

            // 부모 노드(a[largestIdx])와 오른족 자식 노드를 비교
            if (rightChildIdx <= lastIdx && a[rightChildIdx] > a[largestIdx]) {
                largestIdx = rightChildIdx;
            }

            // 부모 노드(a[largestIdx])가 변경이 감지되었다면
            if (largestIdx != parentIdx) {
                // 배열에도 실제로 변경 반영
                swap(a, parentIdx, largestIdx);
                // 자식 노드 largestIdx 를 부모 노드 parentIdx 에 대입시켰으므로 largestIdx 를 새로운 부모 노드로 설정하여 최대힙 다시 만들기
                parentIdx = largestIdx;
            }
            else {
                return;
            }
        }
    }
}