정렬(Sort)

정렬이란?

---

정렬(sort)이란 사용자가 정의한 순서로 데이터를 나열하는 것

이때 사용자가 정의한 순서는 오름차순이나 내림차순일 수도 있고 임의 조건일 수도 있다.

 

정렬은 원하는 데이터를 쉽게 찾기 위해 필요하다. 

예를 들어, 다음의 두 가지 데이터가 있다고 해보자.

정렬된 데이터: [1, 3, 5, 7, 9]

정렬되지 않은 데이터: [1, 5, 7, 9, 3]

여기서 데이터의 중앙값을 찾는다고 할 때 어떤 데이터가 더 찾기 쉬울까?

바로 정렬된 데이터이다.

정렬된 데이터는 그냥 인덱스의 중앙값만 보면 된다. 반면 정렬되지 않은 데이터는 모든 데이터를 확인하며 찾아야 한다.

 

이 세상에는 수 많은 정렬 알고리즘이 존재한다.

정렬 알고리즘은 시간복잡도로 분류할 수 있는데 지금부터 그 시간 복잡도별로 정렬 알고리즘에 대해 이야기 해보도록 하겠다.

 

 

O(N^2)인 정렬 알고리즘

---

1. 선택 정렬(Selection Sort)

동작 방식

선택 정렬은 배열에서 가장 작은 요소를 찾아 첫 번째 위치와 교환하고, 두 번째 작은 요소를 찾아 두 번째 위치와 교환하는 식으로 정렬한다.

선택 정렬의 기본적인 동작 방식은 다음과 같다. (오름차순)

1️⃣ 배열의 최솟값을 찾는다.

2️⃣ 최솟값을 배열의 첫번째 값과 바꾼다.

3️⃣ 첫번째 값을 제외하고 배열의 최솟값을 찾는다.

4️⃣ 최솟값을 배열의 두번째 값과 바꾼다.

5️⃣ 해당 과정을 모든 요소들에 대해 수행한다.

 

[5, 3, 4, 1, 2]를 선택 정렬을 통해 오름차순 정렬하는 경우를 확인해보자.

❶ 첫번째 교환

최솟값인 1을 첫번째 값인 5와 바꿨다.

 

❷ 두 번째 교환

최솟값인 2를 두 번째 값인 3과 바꿨다.

 

❸ 세 번째 교환

최솟값인 3을 세 번째 값인 4와 바꿨다.

 

❹ 네 번째 교환

최솟값인 4를 네 번째 값인 5와 바꿨다.

 

마지막 요소는 이미 정렬이 되어 있기 때문에 배열 요소의 갯수 - 1번 만큼 반복하면 된다.

 

구현(Java)

public static void selectionSort(int[] arr) {

    for(int i = 0; i < arr.length - 1; i++) {
    
    	// 1. 최솟값을 찾는다.
        int min_index = i;
        for(int j = i + 1; j < arr.length; j++) {
            if(arr[min_index] > arr[j])
                min_index = j;
        }
        // 2. 최솟값과 현재 위치의 값을 바꾼다.
        int swap = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = swap;
    }
}

 

시간복잡도

• 최악의 경우: O(N^2)
• 최선의 경우: O(N^2)

삽입 정렬은 어떤 경우던지 O(N^2)이다.

 

2. 버블 정렬(Bubble Sort)

동작 방식

버블 정렬은 인접한 두 요소를 비교하여 필요하면 교환하는 방식으로, 배열 끝까지 반복하면서 가장 큰 요소를 끝으로 이동시키는 과정을 반복한다.

버블 정렬의 기본적인 동작 방식은 다음과 같다.(오름차순)

1️⃣ 첫 번째 값과 두 번째 값을 비교해 두 번째 값이 작다면 위치를 바꾼다.

2️⃣ 두 번째 값과 세 번째 값을 비교해 세 번째 값이 작다면 위치를 바꾼다.

3️⃣ 이 과정을 마지막 값까지 반복한다. 이렇게 되면 마지막에 제일 큰 값이 위치하게 된다.

4️⃣ 모든 데이터가 정렬될 때까지 위의 과정을 반복한다.

 

[5, 3, 4, 1, 2]를 버블 정렬을 통해 오름차순 정렬하는 경우를 확인해보자.

❶ 1회전

 

❷ 2회전

❸ 3회전

 

❹ 4회전

 

마지막 요소는 이미 정렬이 되어 있기 때문에 배열 요소의 갯수 - 1번 만큼 반복하면 된다.

 

구현(Java)

public static void bubbleSort(int[] arr) {

    for(int i = 0; i < arr.length - 1; i++) {
        boolean flag = false;
        for(int j = 0; j < arr.length - 1 - i; j++) {
        	// 만약 뒤에 값이 더 작다면 교환
            if(arr[j] > arr[j + 1]) {
                int swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
                flag = true;
            }
        }
        // 한번도 스왑이 되지 않으면 정렬이 끝난 것
        if(!flag)
            break;;
    }
}

❗️버블 정렬에서 한번도 스왑이 일어나지 않는다면 해당 배열은 정렬이 끝난 것이다. 이를 통해 배열의 성능을 증가시킬 수 있다.

 

시간복잡도

• 최악의 경우: O(N^2)
• 최선의 경우: O(N)

버블 정렬의 경우 이미 정렬된 배열의 경우, O(N)으로 정렬을 할 수 있다.

 

3. 삽입 정렬(Insertion Sort)

동작 방식

삽입 정렬은 배열을 순차적으로 탐색하면서 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 요소를 정렬된 부분에 적절한 위치에 삽입하는 정렬이다.

삽입 정렬의 동작방식은 다음과 같다. (오름차순)

1️⃣ 두 번째 값부터 왼쪽의 값과 하나씩 비교해 작다면 계속 탐색하고 크다면 그 자리에 삽입한다.

2️⃣ 모든 값에 대해 해당 과정을 반복한다.

 

[5, 3, 4, 1, 2]를 삽입 정렬을 통해 오름차순 정렬하는 경우를 확인해보자.

 

❶ 1회전

3과 왼쪽 정렬된 부분과 비교한다.

5는 3보다 크기 때문에 해당 자리에 삽입한다.

 

❷ 2회전

4는 5보다는 작고 3보다는 크기 때문에 그 사이에 삽입한다.

 

❸ 3회전

1은 3, 4, 5보다 작으므로 3앞에 삽입한다.

 

❹ 4회전

2는 3, 4, 5보단 작고 1보단 크기 때문에 1과 3사이에 삽입한다.

 

구현(Java)

public static void insertionSort(int[] arr) {
    for(int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

 

시간복잡도

• 최악의 경우: O(N^2)
• 최선의 경우: O(N)

이미 배열이 정렬된 경우 삽입할 곳을 찾는 과정을 수행하지 않아도 되므로 O(N)이 된다.

반면 배열이 역순인 경우 삽입할 곳을 찾기 위해 매번 모든 요소를 비교해야 하므로 O(N^2)이 된다.

 

 

 

O(NlogN)인 정렬 알고리즘

---

1. 병합 정렬(Merge Sort)

동작 방식

병합 정렬은 데이터를 분할할 수 있을 때까지 분할한 다음, 정렬된 상태로 병합하는 정렬 방식이다.

병합 정렬의 동작 방식은 다음과 같다:

1️⃣ 데이터를 더 이상 분할할 수 없을 때까지(즉, 데이터가 하나의 원소가 될 때까지) 분할한다.

2️⃣ 분할한 데이터를 두 개의 정렬된 부분 배열로 만든 후, 이 두 부분 배열을 정렬하며 병합한다.

3️⃣ 모든 데이터를 병합하여 하나의 정렬된 배열이 될 때까지 이 과정을 반복한다.

 

[38, 27, 43, 3, 9, 82, 10]을 병합 정렬을 통해 오름차순 정렬하는 경우를 확인해보자.

1. 데이터를 더 이상 분할할 수 없을 때까지 (즉, 데이터가 하나의 원소가 될 때까지) 분할한다.

 

2. 분할한 데이터를 두 개의 정렬된 부분 배열로 만든 후, 이 두 부분 배열을 정렬하며 병합한다.

 

3. 모든 데이터를 병합하여 하나의 배열이 될때까지 반복한다.

 

● 두 개의 부분 배열이 정렬되는 방식

각각의 부분 배열에는 포인터가 존재한다. 최초의 포인터는 배열의 첫 번째 요소를 가리키고 있다.

 

현재 포인터의 값을 비교해 더 작은 값을 병합할 배열에 넣고 포인터를 다음으로 옮긴다.

 

이 과정을 모든 요소가 배열에 들어갈 때까지 반복한다.

 

구현(Java)

public static void main(String[] args) {
    int[] arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr);
    System.out.println(Arrays.toString(arr));
}

public static void mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return;
    }

    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);

    mergeSort(left);
    mergeSort(right);

    merge(arr, left, right);
}

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    while (i < left.length) {
        arr[k++] = left[i++];
    }

    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

시간복잡도

• 최악의 경우: O(NlogN)
• 최상의 경우: O(NlogN)

분할: logN, 병합: N 이므로 O(NlogN)이다.

최악이던, 최상이던 데이터를 분할하고 합치는 과정을 똑같이 거치기 때문에 시간복잡도는 일정하다.

 

2. 퀵 정렬(Quick Sort)

동작 방식

퀵 정렬은 피벗을 선택하고, 피벗을 기준으로 작은 값과 큰 값을 나누어 정렬하는 정렬 방식이다.

퀵 정렬의 동작방식은 다음과 같다.

1️⃣ 피벗을 선택한다(일반적으로 첫번째 값)

2️⃣ 두 개의 배열로 분할한다. 피벗을 기준으로 피벗보다 작은 값들은 왼쪽 배열로, 큰 값들은 오른쪽 배열로 분할한다.

3️⃣ 이 과정을 배열의 크기가 1 이하가 될 때까지 반복한다.

4️⃣ 퀵 정렬은 분할과 동시에 정렬이 이루어지므로 별도의 병합 과정이 필요 없다.

5️⃣ 모든 분할 과정이 완료되면 전체 배열이 정렬된 상태가 된다.

 

[38, 27, 43, 3, 9, 82, 10]을 퀵 정렬을 통해 오름차순 정렬하는 경우를 확인해보자.

 

피벗을 배열의 첫번째 값으로 설정하였다. 

 

분할이 완료되면 전체 배열이 정렬된 상태가 된다.

 

구현(Java)

public static void main(String[] args) {
    int[] arr = {38, 27, 43, 3, 9, 82, 10};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high);
        quickSort(array, low, pi - 1);  // 피벗보다 작은 요소들 정렬
        quickSort(array, pi + 1, high); // 피벗보다 큰 요소들 정렬
    }
}

public static int partition(int[] array, int low, int high) {
    int pivot = array[low];  // 피벗을 첫 번째 요소로 설정
    int i = low;             // i는 피벗보다 작은 요소들의 끝을 가리킴

    for (int j = low + 1; j <= high; j++) {
        if (array[j] < pivot) {
            i++;
            swap(array, i, j); // 현재 요소가 피벗보다 작으면 i와 교환
        }
    }

    swap(array, low, i); // 피벗을 최종 위치로 이동
    return i;            // 피벗의 최종 위치 반환
}

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

 

시간복잡도

• 최악의 경우: O(N^2)
• 최상의 경우: O(NlogN)

피벗이 배열의 가장 작은 값만 선정되는 경우엔 분할을 할때마다 배열의 크기가 1씩만 줄어든다. 따라서 O(N^2)

피벗이 중앙 값으로 선정되는 경우엔 분할을 할 때마다 배열의 크기가 반씩 줄어든다. 따라서 O(NlogN)

 

3. 힙 정렬(Heap Sort)

힙 정렬을 이해하기 위해선 힙 자료구조가 무엇인지 이해해야 한다.

힙이란?

힙은 부모노드가 자식노드보다 작거나 큰 이진트리이다.

힙에는 최소힙과 최대힙이 있다.

최소힙: 부모 노드가 자식 노드보다 작다.

최대힙: 부모 노드가 자식 노드보다 크다.

 

최대힙 예시

 

힙 구축방법

기본적인 규칙은 다음과 같다.

1. 현재 노드와 자식 노드의 값을 비교

 1-1. 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다.

 1-2. 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산을 종료한다.

2. 맞바꾼 자식 노드의 위치를 현재 노드로 하여 1번과정을 반복한다.

 

위에서 사용했던 배열인 [38, 27, 43, 3, 9, 82, 10]로 최대힙을 구축해보겠다.

배열 [38, 27, 43, 3, 9, 82, 10]을 트리로 나타내면 다음과 같이 나타낼 수 있다.

❗️인덱스는 1부터 시작한다.

 

힙 구축은 마지막 노드의 부모노드 부터 시작한다. 즉, 배열의 크기가 n일 때 n/2번 인덱스부터 시작한다.

이 경우엔 3번 인덱스부터 시작한다. 

 

1. 3번 인덱스: 43

현재 노드가 모든 자식 노드보다 크지 않다. 그러므로 자식 노드중 가장 큰 값과 바꾼다.

• 43과 82를 바꾼다.

2. 2번 인덱스: 27

현재 노드가 모두 자식노드보다 크기 때문에 넘어간다.

 

3. 1번 인덱스: 38

현재 노드가 모든 자식 노드보다 크지 않다. 그러므로 자식 노드중 가장 큰 값과 바꾼다.

• 38과 82를 바꾼다.

바꾼 자식 노드를 현재 노드로 설정하여 반복한다.

현재노드가 모든 자식 노드보다 크지 않다. 그러므로 가장 큰 자식 노드와 바꾼다.

• 38과 43을 바꾼다.

이렇게 최대힙 구축을 끝냈다.

동작 방식

힙 정렬은 힙 자료구조를 이용한 정렬 방식이다.

힙 정렬의 동작 방식은 다음과 같다.

1️⃣ 배열을 가지고 최대힙을 구축한다.(최대힙: 오름차순 / 최소힙: 내림차순)

2️⃣ 루트 노드를 마지막 노드와 바꾼다.

3️⃣ 바꾼 루트노드를 트리에서 제외시킨다. (해당 노드는 정렬 완료)

4️⃣ 다시 최대힙을 구축한다.

5️⃣ 트리의 노드가 없을 때까지 반복한다.

 

[38, 27, 43, 3, 9, 82, 10]을 힙 정렬을 통해 오름차순 정렬하는 경우를 확인해보자.

 

1. 배열을 가지고 최대힙을 구축한다.

• 위에서 구축했기 때문에 설명은 생략하겠다.

2. 루트노드와 마지막 노드를 바꾼다.

• 10과 82를 바꿨다.

3. 바꾼 루트 노드를 제외시킨다.

• 82를 제외시켰다.
• 제외된 노드는 정렬이 완료된 것이다.

4. 다시 최대힙을 구축한다.

 

이제 위의 과정을 트리의 모든 노드가 사라질때까지 반복하면 된다.

 

구현(Java)

public static void main(String[] args) {
    int[] arr = {38, 27, 43, 3, 9, 82, 10};
    heapSort(arr);
    System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
    // 최대힙 구축
    int n = arr.length;
    for(int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, i, n);
    }

    for(int i = n - 1; i >= 0 ; i--) {
        swap(arr, 0, i ); // 루트 노드와 마지막 노드 교환
        heapify(arr, 0, i); // 마지막 노드를 제외하고 루트 노드에 대해 다시 heapify 진행
    }

}
private static void heapify(int[] arr, int start, int end) {
    int largest = start;
    int left = start * 2 + 1;
    int right = start * 2 + 2;

    if(left < end && arr[largest] < arr[left])
        largest = left;

    if(right < end && arr[largest] < arr[right])
        largest = right;

    if(largest != start) {
        swap(arr, start, largest);
        heapify(arr, largest, end);
    }
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

시간복잡도

• 최악의 경우: O(NlogN)
• 최상의 경우: O(NlogN)

최초 최대힙을 구축하는데 O(N), 그 이후 N번 힙을 재구성하는데 힙을 재구성하는 것은 logN이다. 그러므로 O(NlogN)

총 시간복잡도는 O(N + NlogN)이므로 시간복잡도는 O(NlogN)이다.

 

 

 

O(N)인 정렬 알고리즘

---

1. 계수 정렬(Counting Sort)

동작 방식

계수 정렬은 데이터의 빈도수를 통해 정렬하는 방식이다.

계수 정렬의 동작 방식은 다음과 같다.

1️⃣ 빈도 수를 저장할 카운팅 배열을 선언한다. 이때 카운팅 배열의 크기는 정렬하고자 하는 배열 요소의 최댓값으로 해야한다. 

2️⃣ 정렬하고자 하는 배열의 요소들을 순회하며 빈도 수를 카운팅 배열에 저장한다. 

3️⃣ 카운팅 배열의 낮은 인덱스부터 빈도수만큼 해당 인덱스 값을 반환한다.

 

[4, 2, 2, 8, 3, 3, 1]을 계수정렬을 이용해서 오름차순으로 정렬하는 경우를 확인해보자.

 

1. 카운팅 배열을 생성한다.

• 정렬하고자 하는 배열의 최댓값이 8이므로 인덱스가 0부터 시작하는 것을 감안해 배열의 크기를 9로 설정한다.

2. 배열을 순회하며 요소들의 빈도 수를 카운팅 배열에 저장한다. 

 

3. 빈도수 배열의 낮은 인덱스부터 빈도 수 만큼 해당 인덱스를 반환한다.

 

구현(Java)

public static void main(String[] args) {
    int[] arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    System.out.println(Arrays.toString(arr));
}

public static void countingSort(int[] arr) {
    int[] counting = new int[getMax(arr) + 1];

    for(int i = 0; i < arr.length; i++) {
        counting[arr[i]]++;
    }

    int k = 0;
    for(int i = 0; i < counting.length; i++) {
        for(int j = 0; j < counting[i]; j++) {
            arr[k] = i;
            k++;
        }
    }
}

private static int getMax(int[] arr) {
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < arr.length; i++) {
        if(max < arr[i])
            max = arr[i];
    }
    return max;
}

시간복잡도

• O(N + K) (N: 정렬 배열의 크기, K: 정렬배열의 최댓값)

최댓값 찾기: O(N)

카운팅 배열 빈도수 저장: O(K)

출력배열에 값 배치: O(K + N)

 

2. 위상 정렬(Topolgical Sort)

위상 정렬은 지금까지 이야기했던 정렬과는 성격이 다르다.

지금까지의 정렬은 오름차순, 내림차순으로 배열의 데이터를 정렬했다면, 위상 정렬은 그래프의 방문 순서를 결정하는 정렬이다.

위상 정렬은 작업의 순서를 결정하는 알고리즘이다. 그렇기 때문에 반드시 그래프에 순환이 없고 간선의 방향이 있어야 한다.

위상 정렬을 이해하기 위해선 진입차수라는 개념을 이해해야한다.

진입차수?

진입차수란 자신을 가리키고 있는 간선의 개수를 의미한다.

• A, B, C는 자신을 가리키고 있는 간선이 없으므로 진입차수가 0이 된다.
• D는 A가 자신을 가리키고 있으므로 진입차수가 1이 된다.
• E는 B와 C가 자신을 가리키고 있으므로 진입차수가 2가 된다.

동작 방식

위상 정렬은 그래프의 진입차수를 기준으로 정렬하는 정렬 방식이다.

위상 정렬의 동작방식은 다음과 같다.

1️⃣ 진입차수가 0인 노드를 큐에 넣는다.

2️⃣ 큐에 데이터를 모두 꺼내고 해당 노드들이 가리키고 있던 노드들의 진입차수를 하나씩 줄인다. 

3️⃣ 모든 노드의 진입차수가 0이 돼 큐를 거칠때 까지 반복한다.

4️⃣ 큐에서 데이터를 꺼낸 순서가 정렬 순서가 된다.

 

다음의 그래프를 위상정렬하는 경우를 보자.

 

1. 진입차수가 0인 노드를 큐에 넣는다.

• 진입차수가 0인 A, B, C를 큐에 넣었다.

2. 큐에서 데이터를 모두 꺼내고 각 노드들이 가리키는 노드들의 진입차수를 1 줄인다.

• A가 가리키던 D의 진입차수가 1 줄어 0이 됐다.
• B가 가리키던 G의 진입차수가 1 줄어 0이 됐다.
• C가 가리키던 E의 진입차수가 1 줄어 1이 됐다.

1. 다시 진입차수가 0인 노드를 큐에 넣는다.

• 진입차수가 0인 D, G를 큐에 넣는다.

2. 큐에서 데이터를 모두 꺼내고 각 노드들이 가리키는 노드들의 진입차수를 1 줄인다.

• D가 가리키던 E의 진입차수가 1 줄어 0이 됐다.
• G가 가리키던 노드가 없다.

끝까지 반복하면

A - B - C - D - G - E - F가 답이 된다.

 

구현(Java)

public static List<String> topologicalSort(Map<String, List<String>> graph) {
    Map<String, Integer> inDegree = new HashMap<>();
    for (String node : graph.keySet()) {
        inDegree.put(node, 0);  // 모든 노드의 진입차수를 0으로 초기화
    }

    for (String node : graph.keySet()) {
        for (String neighbor : graph.get(node)) {
            inDegree.put(neighbor, inDegree.get(neighbor) + 1);  // 노드의 진입차수 증가
        }
    }

    Queue<String> queue = new LinkedList<>();
    for (String node : inDegree.keySet()) {
        if (inDegree.get(node) == 0) {
            queue.offer(node);  // 진입차수가 0인 노드를 큐에 삽입
        }
    }

    List<String> sortedList = new ArrayList<>();
    while (!queue.isEmpty()) {
        String node = queue.poll();
        sortedList.add(node);
        for (String neighbor : graph.get(node)) {
            inDegree.put(neighbor, inDegree.get(neighbor) - 1);  // 노드의 진입차수 감소
            if (inDegree.get(neighbor) == 0) {
                queue.offer(neighbor);
            }
        }
    }

    if (sortedList.size() != graph.size()) {
        throw new RuntimeException("The graph has a cycle");
    }

    return sortedList;
}

public static void main(String[] args) {
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("D"));
    graph.put("B", Arrays.asList("G"));
    graph.put("C", Arrays.asList("E"));
    graph.put("D", Arrays.asList("E"));
    graph.put("E", Arrays.asList("F"));
    graph.put("F", new ArrayList<>());
    graph.put("G", new ArrayList<>());


    System.out.println(topologicalSort(graph));
}

 

시간복잡도

• 최악의 경우: O(V + E)
• 최상의 경우: O(V + E) (V: 정점의 갯수, E: 간선의 갯수)

모든 정점과 간선을 딱 한번만 지나므로 시간복잡도는 O(V+E)