[자료구조 및 알고리즘] Ch06. 정렬(sort)

January 20, 2023

정렬(sort)

🔊 패스트캠퍼스 "한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online." 강의를 보고 공부하면서 정리한 노트 게시물입니다.

Ch06-01. 이진 탐색 (Binary Search)

오름차순 정렬되어 있는 리스트 내에서 특정 값의 인덱스를 찾는 알고리즘
빠른 속도
- 시간 복잡도 $O(logN)$
- $(N = 100)$ vs $(logN = 6.64)$
정렬된 리스트에서만 사용 가능

구현

main > java > sort > BinarySearch.java

package sort;

public class BinarySearch {

    public int search(int[] arr, int target) { // arr은 이미 정렬되어있음이 보장되어있는 array 데이터 집합
        // 1. 데이터의 중간 인덱스 값을 찾는다.
        // 2. 중간 인덱스 위치를 기준으로 arr 을 절반으로 나눈다.
        // 3. 나눠진 절반의 리스트에서 target 값을 찾는다.

        int l = 0; // left
        int r = arr.length - 1; // right

        int m;
        // left가 right보다 작을 때까지만 수행,
        while (l <= r) { // l이 r보다 커진다는 것은 사실상 모든 arr의 데이터를 다 봤다는 의미
            // 중간 인덱스 찾기
            m = l + ((r - l) / 2);  // overflow exception 막기 위해 이렇게 구함... 이렇게 하면, 똑같이 l과 r의 중간 인덱스가 나오지만 overflow exception 방지
            // (l + r) / 2 를 해서 중간 인덱스를 구할 수도 있겠지만, int는 2**-31 ~ 2**31-1의 값까지만 저장이 가능
            // 그렇기 때문에, 각각 l과 r의 범위가 int안에 있다 하더라도 이 숫자의 합이 int의 범위가 발생하면 overflow exception 발생

            if (arr[m] == target) { // arr[m]이 우리가 찾고자 하는 타겟 값과 동일하다면,
                return m;
            }
            // target 값이 아닌 경우는 2가지 케이스 존재
            if (arr[m] < target) {  // target 값이 더 큰 경우
                l = m + 1; // m을 기준으로 오른쪽에 있는 값들만 보면 되므로 l의 인덱스는 m + 1
            } else {    // target 값이 더 작은 경우
                r = m - 1; // m을 기준으로 해서 arr의 왼쪽을 봐주면 되기 때문에, r을 m - 1로 셋팅
            }
        }
        return -1;
    }
}

Ch06-02. 버블 정렬 (Bubble Sort)

정렬

안정(stable) 정렬 vs 불안정(unstable) 정렬
- 중복된 값의 순서 보장 여부
  
  실제로는 동일한 1이지만, 구분하기 위해 1_a, 1_b 으로 표시
  
  이 리스트를 정렬했을 때는,
  
  위 그림과 같이, 2가지 경우가 가능
  
  위의 경우는 동일한 1에 대해서 처음에 a, b 순서가 동일하게 유지되었고, 아래 케이스도 정렬은 되었지만 숫자 1의 순서는 다르다.
  
  이렇게 중복된 값의 순서 보장 여부에 따라서, 순서가 보장이 되는 경우에는 ‘안정 정렬’, 보장이 되지 않는 경우에는 ‘불안정 정렬’이라고 한다.
In-place 정렬 vs Out-of-place 정렬
- 원본 데이터 내 정렬 여부
  - In-place 정렬 : 원본 데이터 내에서 정렬이 이루어지는 경우
  - Out-of-place 정렬 : 원본 데이터가 아닌 새로운 배열로 정렬된 output 결과를 만드는 경우

그래서, 정렬을 볼 때에는 정렬의 시간 복잡도와 안정 정렬 여부 그리고, 구현 방식 이렇게 3가지 관점에서 차이를 비교해볼 수 있다.

Bubble Sort

리스트의 처음부터 끝까지 이러한 싸이클을 1번 반복하게 되면, 이 리스트의 가장 끝에는 리스트 안에 존재하는 가장 큰 값이 위치하게된다. 하지만, 이 값을 제외한 앞의 값들은 여전히 정렬되지 않은 상태이므로, 다시 처음부터 비교하고 위치를 바꿔주는 연산을 실시한다.

이런 식으로 리스트 끝까지 반복하게 되면, 마찬가지로 마지막 인덱스의 바로 앞에는

이번 수행에서 가장 큰 값이었던 7이 위치하게된다.

그러면, 이 마지막 두 칸을 제외하고, 다시 처음부터 앞에서 비교와 위치를 바꾸는 swap 연산을 수행을 하게 된다.

이렇게 한 싸이클을 마무리 할 때마다, 현재 리스트에 위치한 가장 큰 값이 뒤에 하나 하나씩 쌓이게 될 것이다.

그래서, 마지막으로 정렬해야 할 데이터의 크기가 하나가 된다면,

배열 내에 모든 데이터가 정렬된 상태가 될 것이다.

다시 정리를 해보자면,

인접한 두 element의 값을 비교
두 값이 정렬되어 있지 않다면 위치를 교환
정렬이 완료된 elements를 제외하고 위의 과정을 반복
- $(n - 1) + (n - 2) + (n - 3) + … + 2 + 1 = \frac{n (n-1)}{2}$
시간복잡도 $O(N^2)$
직관적이고 단순한 알고리즘

그러나, Bubble sort는 느리기 때문에, 실제로 사용하기는 다소 어렵다는 단점도 존재함.

출처 : 위키백과

정렬되는 모양이 마치 거품이 있는 것 같다고해서 버블 정렬이라는 이름이 붙음


출처 : 위키백과

구현

BubbleSort.java

package sort;

public class BubbleSort implements ISort {
    @Override
    public void sort(int[] arr) {
        // 안정 정렬
        // 인플레이스 정렬
        for (int i = 0; i < arr.length - 1; i++) { // 전체 리스트
            for (int j=0; j < arr.length-1-i; j++) { // 정렬된 리스트를 제외시키고 반복
                if (arr[j] > arr[j + 1]) { // 앞에 있는 값이 뒤에 값보다 크면, 값을 바꿔줘야하는 경우
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }
}

Ch06-03. 삽입 정렬 (Insert Sort)

Insertion Sort

리스트의 앞에서부터
이미 정렬된 서브 리스트의 값들과 비교
자신의 위치에 삽입

근데, 우리는 정렬되어있지 않은 리스트를 정렬하려고 하는건데 그렇다면, 이미 정렬된 서브 리스트는 어디서 나오는걸지부터 생각해봐야한다.

만약에 사이즈가 1인 배열에 있다면 이 배열에는 어떤 값이 들어있어도 정렬된 상태라고 볼 수 있다. 배열이 1칸이라면 그 안에 5든, 1이든, 100이든 어떤 값이 들어있든 이 리스트는 정렬이 되어있는 상태인 것이다. 그래서, 삽입 정렬은 여기에서 출발하게된다.

리스트에서 가장 앞에 있는 하나의 원소를 이미 정렬된 서브 리스트로 보고, 정렬을 시작하게된다.

그렇기 때문에, 실질적인 정렬 로직은 리스트의 2번째(index로는 1번째) 위치에 있는 값부터 정렬을 시작하게된다.

이미 정렬되어있는 서브 리스트 내에서 값 비교를 통해서 자신이 삽입되어야 할 위치 (여기서는 0번째 인덱스에 숫자 4가 삽입된 모습). 4는 5보다 작기 때문에 5의 앞에 삽입된 거라고 볼 수 있다.

그러면, 사이즈가 2인 정렬된 서브 리스트가 생기게 되는 것이다.

그렇다면, 이번에는 2번 인덱스에 위치한(3번째 값) 1을 정렬할 차례다. 1을 앞에 정렬된 서브 리스트 내의 원소들과 값을 비교해서 위치를 찾아보면,

1의 위치는 서브 리스트의 가장 앞이 되겠다. 이제 정렬된 서브 리스트의 크기는 총 3개가 되었다.

그 다음은 9의 위치를 찾을 차례다.
마찬가지로, 서브 리스트들과 값 비교를 했을 때 9의 위치를 탐색해보면, 9는 현재 위치에 그대로 있게 된다.

그래서, 4칸의 정렬된 서브 리스트를 얻게 되었다.

이런식으로, 리스트의 끝까지 순환하면서 자신의 위치를 찾아가게 되고, 리스트 전체를 순환하게 되면, 모든 원소들이 정렬된 제자리를 찾아가게 되는게 삽입 정렬의 기본 매커니즘이다.

출처 : 위키백과


출처 : 위키백과

그래서 삽입 정렬의 특징을 보자면,

안정 정렬
단순한 알고리즘
데이터 이동이 많음
- 리스트 내의 데이터가 어느 정도 정렬이 되어있는 상태일 경우 데이터의 이동이 적어짐

시간 복잡도

평균 → $O(n^2)$
최선의 경우
- 모두 정렬이 되어있는 경우 → $O(n)$
최악의 경우
- 역으로 정렬되어 있는 경우 → $O(n^2)$

구현

InsertionSort.java

package sort;

public class InsertionSort implements ISort {
    @Override
    public void sort(int[] arr) {
//        int n = arr.length;
        for (int i = 1; i < arr.length; i++) { // 1. 가장 앞에 있는 0번째 데이터는 이미 정렬되어있는 서브리스트로 보기 때문에 i=1부터 시작
//        for (int i = 1; i < n; ++i) {
            int key = arr[i];   // 2. 삽입 위치를 찾아줄 데이터
            int j = i - 1;  // 3. 0 ~ j까지가 정렬된 서브 리스트의 인덱스로 보는 것
            // 6. 그런데 이 때, 키 값보다 정렬된 배열의 값이 클 때까지만 해주면 됨, 데이터를 이동하는 작업을 0번까지 할 필요도 없음. (아래)
            while (j >= 0 && arr[j] > key) { // 6. 그래서, arr[j]가 key보다 클 때까지 라는 조건을 하나 더 추가
                // 6. (그러면, key 값보다 정렬된 배열에 있는 값이 작아지면, 더 이상 값 이동을 하지 않게 됨)
                arr[j + 1] = arr[j]; // 5. 데이터를 한 칸씩 오른쪽으로 이동
                j = j - 1; // 4. 역순으로 값 비교 (이렇게 하면, j부터 0까지 역순으로 서브 리스트를 순환하게 됨)
            }
            arr[j + 1] = key; // 7. 그리고 그 위치에 arr[j + 1] = key 해주면, 해당 위치에 데이터가 삽입됨.
        }
    }
}

Ch06-04. 합병 정렬 (Merge Sort)

하나의 리스트를
두 개의 균등한 크기의 리스트로 분할하고
부분 리스트를 합치면서 정렬하여
전체가 정렬되게 하는 방법

부분 리스트의 사이즈가 1이 될 때까지 반복해서 분할

분할된 부분 리스트들을 합치면서, 정렬을 할 때도 부분 리스트들을 한번에 다 정렬해서 결과를 얻는게 아니라 분할과 동일한 크기로 부분 리스트들을 합쳐나가게된다.

합치는 과정을 원래 크기의 배열이 될 때까지 반복해나감.

분할 정복 (Divide and Conquer) 알고리즘

출처 : 위키백과

이렇게 하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과들을 조합해서 큰 문제를 해결하는 방식의 알고리즘을 ‘분할 정복 (Divide and Conquer) 알고리즘’ 이라고 함.

분할 정복은 알고리즘 풀이 기법에 있어서 적지 않게 쓰이는 패턴이고, 분할 정복 알고리즘은 보통 재귀함수로 구현이 됐다는 특징이 있다.

그래서, Merge Sort도 재귀함수를 통해서 구현을 하게 될 것이다.
시간복잡도 $O(NlogN)$

우선 분할 과정은 한번 시행할 때마다 리스트의 크기가 2분의 1씩 감소를 하게된다. 그래서, 처음 n개의 element에서 한 번 분할을 하게 되면 2분의 n개의 리스트 2개를 얻게 되고, 그 상태에서 또 분할을 수행하게 되면 4분의 n크기의 서브 리스트 4개를 얻을 수 있게된다.

이러한 분할 연산은 배열의 크기가 1이 될 때까지 반복해야되는데, 리스트의 크기가 2라면 이 분할은 1번 그리고, 4개라면 2번, 리스트의 개수가 총 8개라면 3번을 반복해야 크기가 1인 부분 리스트들을 얻을 수 있다.

즉, n개의 element가 있는 상황에서 n이 2^k 이라면 밑이 2인 log를 취했을 때, k만큼 반복해야 크기가 1인 배열로 분할가능하다는 추론이 가능할 것이다.

그래서, 분할 연산에서 $logN$의 시간 복잡도를 소요하게된다.

그리고, 분할이 된 상태에서 다시 배열을 합칠 때 각 element들을 비교하면서 정렬을 하기 때문에, 비교 연산이 수행되어야한다. 이 비교 연산도 시간 복잡도에 포함이 된다.

그래서, 리스트의 크기가 1인 상태일 때 크기가 1인 배열이 총 n개가 있게 될 것이다. 이 n개의 크기를 비교하면서, 2개씩 합쳐진 상태의 리스트를 만들거기 때문에, n번의 비교 연산이 발생하게된다.

그리고, $\frac{n}{4}$크기의 배열이 4개인 분할 상태에서도, $\frac{n}{4}$크기의 서브 리스트 4개의 개수만큼 비교 연산을 또 수행한다. 결국, 마찬가지로 n번의 비교 연산이 발생한다는 의미다.

그리고, 서브 리스트의 크기가 $\frac{n}{2}$개일 때도, 서브 리스트의 개수는 총 2개고, 이걸 다시 크기가 n인 배열 하나로 합칠 것이다. 결국, 각 depth에서 n개의 element만큼 크기 비교 연산을 수행하게된다.

그래서, 분할 연산을 할 때 총 depth가 $logN$이라는 값을 구할 수 있었고, 각 depth마다 비교 연산을 n번 수행하게 되기 때문에, Merge Sort의 시간 복잡도는 $NlogN$이 된다.


출처 : 위키백과

구현

MergeSort.java

Merge Sort를 구현할 수 있는 방법에는 in-place sort로 구현하는 방법과 out-of-place sort로 구현하는 방법 2가지가 있는데, 여기서는 in-place sort 방법으로 구현한다.

out-of-place sort는 in-place sort보다 난이도가 상대적으로 더 쉽기 때문에, in-place sort를 할 줄 알면 out-of-place sort 혼자서도 충분히 할 수 있을거라고 함.

package sort;

public class MergeSort implements ISort {
    // 안정 정렬

    @Override
    public void sort(int[] arr) {
        // 1. in-place sort
        mergeSort(arr, 0, arr.length - 1); // 정렬해야할 arr, 정렬할 인덱스를 넣어줌(0번째, arr의 가장 끝 인덱스)
    }

    // 2. 분할하는 작업
    private void mergeSort(int[] arr, int low, int high) {
        // 2-5. 그리고, merge sort에서는 종료 조건을 넣어주는게 중요하다.
        //      (종료 조건을 제대로 넣어주지 않으면 무한하게 호출될 수 있는 위험성 존재)
        if (low >= high) { // low 와 high 의 인덱스가 같다는 것 -> 배열의 크기가 1이 되는 경우
            return;
        }
        // 2-1. 분할을 할 때는 절반씩 분할을 하기 때문에, 중간값을 찾는 과정이 필요하다.
        //      실제로 arr 을 쪼개서 수많은 배열로 따로 만드는 게 아니라
        //      arr 가 둘씩 분할되는 인덱스 위치를 찾음
        int mid = low + ((high - low) / 2); // 2-2. 리스트의 중간 위치 인덱스. 중간 인덱스를 기준으로 분할
        mergeSort(arr, low, mid); // 2-3. (재귀 호출) // 중간 인덱스를 기준으로 왼쪽 부분
        mergeSort(arr, mid + 1, high); // 2-4. (재귀 호출) // 중간 인덱스를 기준으로 오른쪽 부분,
        // 이렇게 하면 동일한 크기의 절반씩 인덱스가 나올 것임
        // low, mid, high 에는 분할된 인덱스의 값이 있음
        merge(arr, low, mid, high); // 2-6. merge 하면서 정렬
    }

    // 3. 합병하면서 정렬하는 작업
    private void merge(int arr[], int low, int mid, int high) {
        // 3-1. 배열을 합칠 때는 보조 배열을 하나 두고 사용하게됨.
        int[] temp = new int[high - low + 1];   // 보조 배열
        int idx = 0;                            // 보조 배열의 인덱스

        int left = low; // 3-2. 분할된 왼쪽 리스트의 시작 인덱스
        int right = mid + 1; // 3-3. 분할된 오른쪽 리스트의 시작 인덱스
        while (left <= mid && right <= high) { // 3-4. left가 mid보다 작거나 같을 때 그리고, right가 high보다 작거나 같을 때까지 합병
            // left 나 right 인덱스 둘중 하나라도 리스트에 있는 값을 모두 꺼내게 되면, while 문이 종료
            if (arr[left] <= arr[right]) { // 3-5. 오름차순 정렬해서 데이터를 쌓아야 하므로 작은 값부터
                temp[idx] = arr[left];
                left++;
            } else { // 3-6. arr[right]가 arr[left]보다 더 작은 값인 경우
                temp[idx] = arr[right];
                right++;
            }
            idx++;
        }
        // 3-7. 그리고, 둘 중 하나라도 리스트에 있는 값을 꺼내면 while문이 종료가 되기 때문에,
        //      왼쪽 리스트나 오른쪽 리스트에 아직 값이 남아 있을 수가 있다.
        while (left <= mid) {   // 왼쪽 리스트에 아직 값이 남아 있는 경우
            temp[idx] = arr[left];
            idx++;
            left++;
        } // 이렇게 하면, 남아있는 값을 모두 temp array에 쌓게 될 것임.

        while (right <= high) { // 오른쪽 리스트에 아직 값이 남아 있는 경우
            temp[idx] = arr[right];
            idx++;
            right++;
        }
        // ▲ 만약에 left나 right 둘 중 하나가 자신의 리스트를 다 소진했다면, 이 2, 3번째 while문을 굳이 타진 않을 것이다.

        // 3-8. 여기까지 했을 때, temp라는 보조 배열에는 우리가 값을 합쳐서 정렬한 값이 들어있을 것이기 때문에,
        //      temp 라는 보조배열에 있는 값을 arr 로 복사
        for (int i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
    }
}

Ch06-05. 퀵 정렬 (Quick Sort)

시간복잡도 $O(NlogN)$

퀵 정렬도 Merge Sort와 마찬가지로, 배열을 둘씩 분할하면서 정렬하는 과정을 거치기 때문에 시간복잡도는 $O(NlogN)$이 됨.

하지만, 같은 $O(NlogN)$이더라도 실제 정렬에는 훨씬 더 짧은 시간이 소요됨.
- 참조 지역성(locality of reference)
  
  컴퓨터의 하드웨어 특성 때문에 더 빠른 성질을 가질 수 있게 된다.
  
  참조 지역성(locality of reference)의 원리로 설명하게 되는데, 퀵 정렬은 알고리즘 특성상 동일한 배열 내에서 자리를 이동시킴.
  
  그래서, 인접한 데이터들 사이에 이동이 발생하기 때문에, 제일 처음 배열에 접근할 때만 실제 메모리에서 데이터를 가져오고, 이후에는 캐시로 배열에 접근할 수 있기 때문에, 메모리로 접근할 때보다 빠른 속도로 접근이 가능.
- 한번 결정된 pivot 값은 이후의 연산에서 제외
  
  정렬이 진행될수록(분할이 될수록), 계산해야할 데이터의 수가 점점 줄어드는 특성이 있음.
  계산해야할 데이터의 수가 줄어들면, 당연히 정렬 속도를 줄이는데도 영향을 줌.
추가적인 메모리 공간 사용 X
불안정 정렬
Divide and conquer

퀵 정렬은 pivot값을 정하는 것부터 시작을 하게 된다. pivot값으로 정할 인덱스는 리스트에서 가장 앞에 위치한 원소여도 되고, 가장 뒤에 위치한 원소여도 된다. 혹은 위 그림처럼 가장 중간에 위치한 원소로 설정할 수도 있다.

그래서, pivot값을 기준으로 원소를 재배치하게 된다. pivot값의 왼쪽에는 pivot값보다 작은 값이 위치하게되고, pivot값의 오른쪽에는 pivot값보다 큰 값이 위치하게된다. 이 때, pivot값 자체가 중요한거라서 pivot값의 인덱스는 바뀔 수가 있다.

pivot값을 기준으로 생긴 왼쪽과 오른쪽 2개의 서브리스트를 볼 수 있는데, 이 때 각각 서브리스트에서도 마찬가지로 앞에서 했던 로직을 반복해준다.

그래서, 왼쪽의 서브리스트에서는 pivot값이 중간에 있는 1이 되고, 오른쪽에서는 pivot값을 6으로 설정할 수 있다.

마찬가지로, 정해진 pivot값을 기준으로 pivot값의 왼쪽에는 pivot값보다 작은 값, 오른쪽에는 pivot값보다 큰 값을 넣어주면 위 그림과 같이 다시 재정렬이 이뤄질 것이다.

이제 오른쪽의 서브리스트는 원소의 개수가 하나만 남았기 때문에, 더이상 분할할 수 없는 단위가 됐으므로, 오른쪽의 서브리스트는 퀵 정렬이 종료됨.

왼쪽에는 아직 여전히 서브리스트가 남아있기 때문에, 여기서도 pivot값을 구해서 정렬한다.

여기서 pivot값은 서브리스트의 중간에 위치한 값인 3이 될 수 있다.
3을 기준으로 3보다 작은 값은 pivot값의 왼쪽으로, 큰 값은 pivot의 오른쪽으로 위치시켜준다.

그러면, 각 서브리스트의 크기도 여기서 1이 되기 때문에, 더이상 분할할 수 있는 서브리스트도 없고, 실제로 각 element들도 아래와 같이 순서대로 정렬된 모습을 볼 수 있다.

출처: 위키백과

퀵 정렬의 데이터가 이동하는 모습은 위와 같다.
여기서는 pivot값을 중간값이 아니라 서브리스트에서 가장 오른쪽에 위치한 값을 pivot값으로 설정했을 때 퀵 정렬이 이뤄지는 모습이다.


출처: 위키백과

시간 복잡도

평균 → $O(NlogN)$

데이터를 절반씩 분할하면서 줄여나가기 때문에, $logN$ 만큼의 분할이 이뤄지게 되고, 각 분할에서 $N$번의 값 비교를 통해서 자신의 위치를 찾아가기 때문에, 시간 복잡도가 $NlogN$이 나옴
최악
- 정렬된 리스트 → $O(N^2)$
  
  최악의 경우, 정렬하고자 하는 리스트가 이미 정렬된 상태라면, 시간 복잡도는 $N^2$까지 늘어날 수 있게 된다.
  
  예를 들어서, 오름차순 되어있는 리스트에서 위키백과 gif 이미지처럼
  
  리스트의 가장 앞이나 가장 뒤에 있는 값을 pivot값으로 정하게 되면, pivot값을 기준으로 리스트를 분할하게 될텐데
  
  분할 결과를 보면 이런식으로 될 것이다. 왜냐하면, pivot값의 왼쪽에 넣을 작은 값이 없기 때문이다.
  
  그러면 여기서 동일한 기준으로 pivot값이 결정될 것이기 때문에,
  
  이런식으로 분할이 될 것이다.
  
  다시 말해서, 이 배열의 pivot값이 리스트에서 최솟값이나 최대값으로 지정이 되어버려서 분할이 절반씩 이뤄지지 않는 상태가 될 때 퀵 정렬이 효율을 내지 못한다고 볼 수 있다.
  
  그러면, 절반씩 분할할 때 $logN$번의 분할 횟수가 나온다는 것을 도출을 해서, $NlogN$이라는 시간 복잡도가 나왔던건데, 분할 횟수가 데이터의 갯수만큼 즉, $N$번만큼 발생하게 되므로, $logN$이 $N$으로 증가하게 되고, 그래서 시간 복잡도가 $N^2$ 만큼이 나오게 되는 것이다.
  
  이러한 치우침 분할을 극복하기 위해서, pivot값을 고를 때 몇 가지 pivot값의 후보군을 두고, 그 중에 가장 중간값을 찾아서 pivot으로 사용하는 알고리즘을 쓰기도 한다. (이것을 Median of Three라고 함)

구현

우리는 단순하게 가장 중간 인덱스에 위치한 값을 pivot으로 선택해서 구현.

QuickSort.java

package sort;

public class QuickSort implements ISort {
    @Override
    public void sort(int[] arr) { // 1.
        // 재귀호출하면서 정렬
        quickSort(arr, 0, arr.length - 1); // 정렬할 배열, 가장 낮은 인덱스, 가장 큰 인덱스
    }

    private void quickSort(int[] arr, int low, int high) {
        // 2.
        // 분할된 배열의 크기가 1이 될 때까지 반복하도록
        if (low >= high) { // low가 high보다 크거나 같아지면,
            return; // 퀵 소트 종료
        }
        // 3.
        // pivot값의 인덱스를 찾아줌
        int pivot = low + ((high - low) / 2); // pivot의 인덱스는 중간값을 가져옴
        // pivot 인덱스에 위치한 값 pivotValue
        int pivotValue = arr[pivot];
        // 4.
        int left = low;
        int right = high;
        // 피봇값을 기준으로 피봇값의 왼쪽에는 피봇값보다 작은 값
        // 오른쪽엔 피봇값보다 큰 값을 넣는 작업
        while (left <= right) { // left가 right보다 작을 때까지
            // 5. 왼쪽 값이 피봇값보다 작으면
            while (arr[left] < pivotValue) {
                left++; // 왼쪽값이 pivot값보다 작은 경우이므로 위치를 바꿀 필요가 없으니 그대로 두고, 왼쪽 인덱스를 증가시킴
            }
            // 6. (오른쪽에서도 동일한 동작 진행)
            // 오른쪽 값이 피봇값보다 크면
            while (arr[right] > pivotValue) {
                right--; // 위치를 바꿀 필요가 없기 때문에 계속 오른쪽 인덱스를 감소
            }

            // 7. 왼쪽 인덱스와 오른쪽 인덱스가 교차 하지 않은 상황이라면, 왼쪽 값과 오른쪽 값 swap
            if (left <= right) {
                int tmp = arr[right];
                arr[right] = arr[left]; // arr[left]값을 arr[right]에 넣어주고,
                arr[left] = tmp; // 원래 arr[right]에 들어있던 tmp값을 arr[left]에 넣어줌
                left++; // left는 한 칸씩 증가이동 시킴.
                right--; // right는 한 칸씩 감소이동 시킴.
            }
        } // 이렇게 해서 while문을 종료시키고나면, pivot값의 왼쪽에는 pivot값보다 작은 값이 들어있게 되고, pivot값의 오른쪽에는 pivot값보다 큰 값이 들어있게된다.

이것을 그림으로 보면,

예를 들어, pivot값을 5라고 설정했을 때, 처음 left의 인덱스는 1이 있는 위치까지 이동을 할 것이다. 그리고, right는 6까지만 오게 될 것이다.

왼쪽 인덱스와 오른쪽 인덱스가 교차하지 않은 상태이므로, 두 값을 swap해준다. (2와 5의 위치 바뀜)

그리고 swap을 하게되면,

다시 while문의 위로 돌아오게 될 것이다. 여기서 left는 한 칸 더 이동을 시킬 수 있게 되고, 오른쪽은 여전히 이동을 시키지 않은 상태가 된다. 여기서도, 아직 두 인덱스가 교차하지 않았기 때문에, 두 값을 swap한다.

이렇게해서, pivot값을 기준으로 왼쪽과 오른쪽으로 작은 값과 큰 값이 나눠지게 된다. while문이 빠져나왔을 때는 pivot을 제외한 왼쪽 리스트와 오른쪽 리스트에서 이 작업을 반복을 하게 되면, 퀵 정렬이 되겠다.

최종

맨 마지막 부분(quickSort 호출 부분) 두줄 추가됨.

package sort;

public class QuickSort implements ISort {
    @Override
    public void sort(int[] arr) { // 1.
        // 재귀호출하면서 정렬
        quickSort(arr, 0, arr.length - 1); // 정렬할 배열, 가장 낮은 인덱스, 가장 큰 인덱스
    }

    private void quickSort(int[] arr, int low, int high) {
        // 2.
        // 분할된 배열의 크기가 1이 될 때까지 반복하도록
        if (low >= high) { // low가 high보다 크거나 같아지면,
            return; // 퀵 소트 종료
        }
        // 3.
        // pivot값의 인덱스를 찾아줌
        int pivot = low + ((high - low) / 2); // pivot의 인덱스는 중간값을 가져옴
        // pivot 인덱스에 위치한 값 pivotValue
        int pivotValue = arr[pivot];
        // 4.
        int left = low;
        int right = high;
        // 피봇값을 기준으로 피봇값의 왼쪽에는 피봇값보다 작은 값
        // 오른쪽엔 피봇값보다 큰 값을 넣는 작업
        while (left <= right) { // left가 right보다 작을 때까지
            // 5. 왼쪽 값이 피봇값보다 작으면
            while (arr[left] < pivotValue) {
                left++; // 왼쪽값이 pivot값보다 작은 경우이므로 위치를 바꿀 필요가 없으니 그대로 두고, 왼쪽 인덱스를 증가시킴
            }
            // 6. (오른쪽에서도 동일한 동작 진행)
            // 오른쪽 값이 피봇값보다 크면
            while (arr[right] > pivotValue) {
                right--; // 위치를 바꿀 필요가 없기 때문에 계속 오른쪽 인덱스를 감소
            }

            // 7. 왼쪽 인덱스와 오른쪽 인덱스가 교차 하지 않은 상황이라면, 왼쪽 값과 오른쪽 값 swap
            if (left <= right) {
                int tmp = arr[right];
                arr[right] = arr[left]; // arr[left]값을 arr[right]에 넣어주고,
                arr[left] = tmp; // 원래 arr[right]에 들어있던 tmp값을 arr[left]에 넣어줌
                left++; // left는 한 칸씩 증가이동 시킴.
                right--; // right는 한 칸씩 감소이동 시킴.
            }
        } // 이렇게 해서 while문을 종료시키고나면, pivot값의 왼쪽에는 pivot값보다 작은 값이 들어있게 되고, pivot값의 오른쪽에는 pivot값보다 큰 값이 들어있게된다.
        // 8. while문이 종료된 시점에서 quickSort를 한번 더 호출
        quickSort(arr, low, right); // 왼쪽 서브리스트를 정렬시켜주고,
        quickSort(arr, left, high); // 오른쪽 서브리스트 정렬
        // 배열의 사이즈가 1이 될 때까지, quickSort를 재귀적으로 계속 호출한다.
    }
}

🔊 캡쳐 이미지는 패스트캠퍼스(Fast Campus) 소유이므로, 무단 불펌하지 말아주세요!

맨 위로 이동하기

Share on

Twitter Facebook LinkedIn

Devvoo

[자료구조 및 알고리즘] Ch06. 정렬(sort)

정렬(sort)

🔊 패스트캠퍼스 "한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online." 강의를 보고 공부하면서 정리한 노트 게시물입니다.

Ch06-01. 이진 탐색 (Binary Search)

구현

Ch06-02. 버블 정렬 (Bubble Sort)

정렬

Bubble Sort

구현

Ch06-03. 삽입 정렬 (Insert Sort)

Insertion Sort

시간 복잡도

구현

Ch06-04. 합병 정렬 (Merge Sort)

구현

Ch06-05. 퀵 정렬 (Quick Sort)

시간 복잡도

구현

🔊 캡쳐 이미지는 패스트캠퍼스(Fast Campus) 소유이므로, 무단 불펌하지 말아주세요!

Share on

Leave a comment

You may also enjoy

[자료구조 및 알고리즘] Ch05. 해시(Hash)

[자료구조 및 알고리즘] Ch02. 리스트(List)

[자료구조 및 알고리즘] Ch04. 큐(Queue)

[컴퓨터네트워크] 컴퓨터네트워크 기본 (1)