Java) 정렬 알고리즘 : 버블, 선택, 병합, 퀵 차이와 원리 이해하기

[알고리즘]

Bubble Sort(버블 정렬)

: 인접한 뒤 원소를 비교해 큰 값을 뒤로 보냄

: 데이터의 크기 순서를 여러 번 반복적으로 비교하여 큰 값을 뒤로 이동

Sorting Target: [7, 4, 5, 2, 9, 1, 3]

Step 1: Compare 7 ↔ 4 → [4, 7, 5, 2, 9, 1, 3]
Step 2: Compare 7 ↔ 5 → [4, 5, 7, 2, 9, 1, 3]
Step 3: Compare 7 ↔ 2 → [4, 5, 2, 7, 9, 1, 3]
Step 4: Compare 7 ↔ 9 → No Change → [4, 5, 2, 7, 9, 1, 3]
Step 5: Compare 9 ↔ 1 → [4, 5, 2, 7, 1, 9, 3]
Step 6: Compare 9 ↔ 3 → [4, 5, 2, 7, 1, 3, 9] (9 is sorted)
                  ...
                  ...
                  ...
Final Output: [1, 2, 3, 4, 5, 7, 9]

: 위처럼 인접한 뒤 원소와 비교해 큰 값을 뒤로 보낸다.

: 배열이 완전히 정렬될 때까지 비교를 계속 진행한다.

코드로 이해하기

static void bubbleSort(int[] arr){
    for(int i = 0; i < arr.length; i++){
        for(int j = 0; j < arr.length - 1; j++){
            if(arr[j] > arr[j+1]){
            // arr[3]인덱스가 arr[3+1]인덱스와 비교해서
            // arr[3]인덱스가 더 크면 swap를 통해 자리 바꾸기
                swap(arr, j, j+1);
                // TestUtil.swap인데 import에서 *으로 바꿔서 저렇게 가능
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

: 버블 정렬은 간단하게 이해가 가능

: 인덱스 j(현재 위치)가 j+1(다음 위치)한 인덱스보다 숫자가 크면 자리를 바꿈

: 가장 큰 값이 마지막 자리에 배치될 것이기 때문에 -1을 하여서 굳이 마지막까지 순회하지 않는다.

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

: swap은 이렇게 했음

좀 더 효율적인 버블 정렬

static void bubbleSort2(int[] arr){
        for(int i = 1; i <= arr.length; i++){
            boolean notChanged = true;

            for(int j = 0; j < arr.length - i; j++){
            // - i를 하면 어차피 잴 큰값이 잴 마지막으로 쌓이는 구조이기 때문에
            // 매번 마지막 끝까지 순회할 필요가 없음
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j+1); // TestUtil.swap인데 import에서 *으로 바꿔서 저렇게 가능
                    notChanged = false;
                    // 스왑이 일어날 때 마다 false 저장
                    // 스왑이 일어나지 않으면 정렬이 완료되었으므로 밑에 if문 돌고 종료
                }
            }
            if(notChanged) break;
        }
        System.out.println(Arrays.toString(arr));
    }

"arr.length - i"를 하는 이유 : 스왑이 진행되면 잴 큰 숫자가 잴 뒤에 쌓이는 구조라서 더 이상 비교할 필요 X

ex) [3, 5, 4, 8]에서 8은 정렬이 완료되었으므로, 다음 루프에서는 마지막 값을 제외하고 비교

notChanged : 스왑 발생 여부(스왑이 한 번도 발생하지 않으면, 배열이 이미 정렬된 상태이므로 외부 루프 종료)

요건 그냥 호출하는 방법

public static void main(String[] args) {
        int[] arr = createIntArray(10);
        //int[] arr2 = createIntArray(10);
        // createIntArray는 물론 위부에서 랜덤 숫자를 생성해서 받아줌

        bubbleSort(arr);
        //bubbleSort2(arr2);
    }

---

Selection Sort(선택 정렬)

: 매번 최소값(or 최대값)을 찾아 정렬되지 않은 부분의 맨 앞(or 맨 뒤)으로 이동

Sorting Target: [7, 4, 5, 2, 9, 1, 3]

Step 1: Find Min (1) → Swap with 7 → [1, 4, 5, 2, 9, 7, 3]
Step 2: Find Min (2) → Swap with 4 → [1, 2, 5, 4, 9, 7, 3]
Step 3: Find Min (3) → Swap with 5 → [1, 2, 3, 4, 9, 7, 5]
Step 4: Find Min (4) → No Swap Needed → [1, 2, 3, 4, 9, 7, 5]
Step 5: Find Min (5) → Swap with 9 → [1, 2, 3, 4, 5, 7, 9]
Step 6: Find Min (7) → No Swap Needed → [1, 2, 3, 4, 5, 7, 9]

Final Output: [1, 2, 3, 4, 5, 7, 9]

: step마다 최소값을 찾은 후 정렬되지 않은 부분의 맨 앞에 정렬한다.

코드로 이해하기

static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length; i++){
        int min = min(arr, i);  // i 이후의 가장 작은 값의 인덱스를 찾음
        swap(arr, i, min);      // 현재 위치 i와 가장 작은 값의 위치를 교환
    }
}
static int min(int[] arr, int point){
    int min = point; // 기준 위치를 초기 최소값으로 설정

    for(int i = point + 1; i < arr.length; i++){ // 기준 이후의 배열 탐색
        if(arr[min] > arr[i]){  // arr[min]보다 arr[i]가 더 작으면 해당 i 값이 최소값으로 갱신
            min = i;
        }
    }
    return min;
}

외부 반복문 :  i가 정렬된 부분과 정렬되지 않은 부분의 경계 역할이라고 보면 됨

: i가 증가할수록 배열의 앞부분은 정렬되고, 뒷부분은 정렬되지 않은 상태

내부 반복문 : 기준 위치보다 다음 위치를 탐색해 끝까지 순회

: 현재 최소값 arrr[min]보다 더 작은 값을 찾으면 해당 값을 min을 해당 위치의 인덱스로 갱신

: 기준 위치 이후에서 가장 작은 값의 인덱스를 반환

요건 그냥 호출하는 방법

public static void main(String[] args) {
    int[] arr = createIntArray(10);

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

---

Merge Sort(병합 정렬)

: 리스트를 반으로 나눈 뒤 각각 정렬 후 병합

: 분할 정복 기법을 사용해 리스트를 재귀적으로 반으로 나누고, 각각 정렬 후 병합

Sorting Target: [7, 4, 5, 2, 9, 1, 3]

Step 1: Divide → [7, 4, 5] [2, 9, 1, 3]
Step 2: Divide → [7] [4, 5] [2, 9] [1, 3]
Step 3: Divide → [7] [4] [5] [2] [9] [1] [3]
Step 4: Merge → [4, 5] [7] [2, 9] [1, 3]
Step 5: Merge → [4, 5, 7] [1, 2, 3, 9]
Step 6: Merge → [1, 2, 3, 4, 5, 7, 9]

Final Output: [1, 2, 3, 4, 5, 7, 9]

: Divide가 분할하는 단계

: Merge가 병합하는 단계

: 보면 분할 단계에서 배열의 원소를 한 개가 될 때까지 분할한다.

코드로 이해하기

static void merge(){
        int[] a = {13, 15, 22, 101};
        int[] b = {10, 12, 21, 55, 210, 300};
        int[] res = new int[a.length + b.length];

        int p1 = 0, p2 = 0, idx = 0;
        // p1 : a의 현재 위치, p2 : b의 현재 위치, idx : 현재 값을 저장할 위치

        while(p1 < a.length && p2 < b.length){
            if(a[p1] < b[p2]){     // 두 값을 비교 후 작은 값은 res[idx]에 넣음
                res[idx] = a[p1];
                p1++;
            } else {
                res[idx] = b[p2];
                p2++;
            }
            idx++;
        }
        while(p1 < a.length){      // b 요소를 모두 처리했는데 a가 남아있을 때
            res[idx] = a[p1];      // a를 res[idx] 배열에 추가
            p1++;
            idx++;
        }
        while(p2 < b.length){      // a 요소를 모두 처리했는데 b가 남아있을 때
            res[idx] = b[p2];      // b를 res[idx] 배열에 추가
            p2++;
            idx++;
        }
        System.out.println(Arrays.toString(res));
    }

: 해당 부분은 Merge(병합) 부분만 구현한 예시(정렬이 끝난 두 배열을 하나의 배열로 합친 것)

: 잴 위에 while문은 a, b의 인덱스 요소를 하나씩 비교하여 더 작은 값을 res 배열에 넣음

: 그 후 요소가 남아있을 경우 각각의 while문을 통해 배열에 추가

p1 < a.length && p2 < b.length : "<=" 해당 조건이 아니기 때문에 배열 끝에 도달하면 조건문 탈출

재귀함수를 통해 분할 후 병합하는 방법

static int[] mergeSort(int[] arr){
    int n = arr.length;
    if(n <= 1) return arr;  // 기저 조건(배열의 크기가 1 이하일 경우 배열 반환)
    // 배열의 길이가 1 이하이면 이미 정렬된 상태이기에 반환

    int mid = n/2;  // 중간을 기준으로 배열을 두 부분으로 나눔
    int[] arr1 = mergeSort(Arrays.copyOfRange(arr, 0, mid));
    // 배열 arr의 0번 인덱스부터 mid-1(중간 전)까지 부분 배열 생성
    // 보면 나눈 후 mergeSort를 또 호출(재귀 호출)
    // 그리고 위에 if문을 통해 1개 이하가 아니기 때문에 다시 분할 후 호출
    // 1개가 될 때까지 반복

    int[] arr2 = mergeSort(Arrays.copyOfRange(arr, mid, n));
    // 배열 arr의 중간부터 끝까지 부분 배열 생성

    return merge2(arr1, arr2);
    // arr1과 arr2은 더 이상 분할할 수 없을 때까지 진행한 결과
    // 그 결과를 병합하면서 정렬하기 위해 merge2로 리턴
}

: 재귀적으로 배열을 분할 후 분할된 배열을 정렬하며 병합

: 기저 조건과 재귀 호출 역할을 이해하면 쉽게 코드 흐름 파악 가능

: 나누는 과정에서 자신을 계속 호출하여 1개 이하가 될 때까지 자신을 호출

: 그 후 나눠지는 값이 없을 때 첫 번째 if문을 통해 값이 merge2로 리턴 됨

static int[] merge2(int[] a, int[] b){
    int[] res = new int[a.length + b.length];
    int p1 = 0, p2 = 0, idx = 0;

    while(p1 < a.length && p2 < b.length){
        if(a[p1] < b[p2]){
            res[idx] = a[p1++];
        } else {
            res[idx] = b[p2++];
        }
        idx++;
    }
    while(p1 < a.length){
        res[idx++] = a[p1++];
    }
    while(p2 < b.length){
        res[idx++] = b[p2++];
    }
    return res;
}

: 매개변수를 받아서 Merge Sort 하는 방법

: 연산하는 방법은 merge() 함수랑 똑같음

요건 그냥 호출하는 방법

public static void main(String[] args) {
    merge();

    int[] arr = mergeSort(createIntArray(10));
    System.out.println(Arrays.toString(arr));
}

---

Quick Sort(퀵 정렬)

: 분할 정보 기법을 사용해 피벗(기준 원소를 정함)을 기준으로 데이터를 두 부분으로 나눔

: 작은 값은 왼쪽, 큰 값은 오른쪽에 위치하며, 재귀적으로 분할과 병합을 반복

Sorting Target: [7, 4, 5, 2, 9, 1, 3], Pivot = 7

Step 1: Partition → [4, 5, 2, 1, 3] 7 [9]
Step 2: [4, 5, 2, 1, 3] → Pivot = 4 → [2, 1, 3] 4 [5]
Step 3: [2, 1, 3] → Pivot = 2 → [1] 2 [3]
Step 4: Merge → [1, 2, 3, 4, 5, 7, 9]

Final Output: [1, 2, 3, 4, 5, 7, 9]

: 7을 피벗으로 설정하고, 7을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 나눈다.

: 4를 피벗으로 설정하고, 4를 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 나눈다.

: 이를 정렬이 될때까지 반복

Sorting Target: [7, 4, 5, 2, 9, 1, 3], Pivot = 5

Step 1: Partition → [4, 2, 1, 3] 5 [7, 9]
Step 2: [4, 2, 1, 3] → Pivot = 4 → [2, 1, 3] 4 []
Step 3: [2, 1, 3] → Pivot = 2 → [1] 2 [3]
Step 4: Merge → [1, 2, 3, 4] 5 [7, 9]
Step 5: [7, 9] → Pivot = 7 → [] 7 [9]

Final Output: [1, 2, 3, 4, 5, 7, 9]

: 피벗을 기준으로 나눈 후 왼쪽과 오른쪽 모두 정렬해야할 요소가 있는 경우

: 왼쪽을 먼저 정렬 후 오른쪽 정렬

코드로 이해하기

static int partition(int[] arr, int first, int last){

    int pivotElement = arr[first];  // 배열의 첫 번째 요소를 기준으로 선택
    int p1 = first + 1;             // 기준보다 큰 값을 찾음(왼쪽 -> 오른쪽)
    int p2 = last;                  // 기준보다 작은 값을 찾음(왼쪽 <- 오른쪽)

    while(p1 <= p2){    // 이건 배열 끝까지 돌아야 하니 둔 조건
        while(p1 <= last && arr[p1] < pivotElement){
            p1++;       // arr[p1]이 기준보다 작으면 p1 1증가
        }               // 왼쪽에서 출발하여 기준보다 큰 값을 찾을 때까지 p1 증가
                        // 따로 저장하지 않고 p1의 위치에 유지

        while(p2 >= last && arr[p2] > pivotElement){
            p2--;       // arr[p2]이 기준보다 크면 p2 1다운
        }               // 오른쪽에서 출발하여 기준보다 작은 값을 찾을 때까지 p2 감소
                        // 따로 저장하지 않고 p2 위치에 유지

        if(p1 <= p2){   // p1이 p2보다 작거나 같으면 서로 교환
            TestUtil.swap(arr, p1++, p2--);
        }               // p1이 기준 값보다 큰 값에서 멈추고,
                        // p2가 기준 값보다 작은 값에서 멈춘 상태에서 교환
    }
    TestUtil.swap(arr, first, p2);  // pivot을 올바른 위치로 이동시키는 과정
            // p2r가 pivot 위치인 이유는 p2가 멈춘 위치는 pivot보다 작은 값들 중 가장 오른쪽 값
            // 즉, pivot 왼쪽에는 작거나 같은 값들 / 오른쪽에는 큰 값들 위치
    return p2;  // return pivot point
}

: 피벗을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 나누는 작업

static void quickSort(int[] arr, int first, int last){
    if(first <= last){
        int pivot = partition(arr, first, last);
        quickSort(arr, first, pivot - 1); // 왼쪽 부분 정렬
        quickSort(arr, first + 1, last);  // 오른쪽 부분 정렬
    }
}

: 왼쪽 부분(pivot보다 작은 값)과 오른쪽 부분 (pivot보다 큰 값) 정렬

이해하기가 어려워서 코드 추가 설명

int[] arr = {5, 3, 8, 4, 2, 7, 1, 10};

기준 값(pivot) : 5

 

초기 상태

Index	0	1	2	3	4	5	6	7
값	5	3	8	4	2	7	1	10
포인터	P	p1						p2

pivotElement : 5

p1 : 1, p2 : 7

 

p1 이동 :

arr[1] : 3(작음) -> p1++

arr[2] : 8(큼) -> 멈춤(p1 : 2)

 

p2 이동 :

arr[7] : 10(큼) -> p2--

arr[6] : 1 (작음) -> 멈춤(p2 : 6)

 

p1과 p2 교환(계속 반복)

Index	0	1	2	3	4	5	6	7
값	5	3	1	4	2	7	8	10
포인터	P		p1				p2

arr[2] : 8 <-> arr[6] : 1 교환

p1++, p2-- -> p1 : 3(인덱스 번호), p2 : 5 (인덱스 번호)

: 이러식으로 p1과 p2과 기준보다 큰 값과 작은 값을 찾아서 자리를 바꾸면,

: 기준보다 작은 값은 왼쪽에 큰 값은 오른쪽에 모임

마지막에 TestUtil.swap(arr, first, p2);를 하는 이유는?

: partition()을 실행하면, p1과 p2가 움직이며 pivot보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 이동

: 하지만, pivot 자체는 아직 처음 위치(first)에 있음!

Index	0	1	2	3	4	5	6	7
값	5	3	1	4	2	7	8	10
포인터	P				p2
-	-	-	-	-	-	-	-	-
이동 후 값	2	3	1	4	5	7	8	10
이동 후 포인터					P

: pivot(5)가 정렬된 위치인 4번 인덱스로 가야한다.

: 이제 여기서 quickSrot() 호출하면,

각각의 부분 배열( arr[first] ~ arr[pivot - 1], arr[pivot + 1] ~ arr[last] )이 재귀적으로 정렬된다.

요건 그냥 호출하는 방법

public static void main(String[] args) {
        int[] arr = TestUtil.createIntArray(100);

        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }