[Algorithm] 정렬 알고리즘

wujin·2024년 1월 13일
algorithm
post-thumbnail

0. 정렬 알고리즘 시간 복잡도

정렬 알고리즘평균 시간 복잡도최선의 시간 복잡도최악의 시간 복잡도
선택 정렬O(n^2)O(n^2)O(n^2)
삽입 정렬O(n^2)O(n)O(n^2)
버블 정렬O(n^2)O(n)O(n^2)
병합 정렬O(n log n)O(n log n)O(n log n)
힙 정렬O(n log n)O(n log n)O(n log n)
퀵 정렬O(n log n)O(n log n)O(n^2) (피봇 선택에 따라 다름)
트리 정렬O(n log n)O(n log n)O(n^2) (특정한 트리 구조에 따라 다름)

1. 선택 정렬(Selection Sort)

  • 시간복잡도
    • Avg: O(n^2)
    • Worst: O(n^2)
    • Best: O(n^2)

선택 정렬은 리스트에서 가장 작은(또는 큰) 요소를 선택하여 순서대로 정렬하는 방법이다.

  1. 리스트에서 가장 작은 요소를 찾는다.

  2. 그 요소를 리스트의 맨 앞 요소과 교환한다.

  3. 나머지 리스트에서 가장 작은 요소를 찾아 그 다음 위치에 넣는다.

  4. 이러한 과정을 리스트의 모든 요소가 정렬될 때까지 반복한다.

리스트의 크기가 커질수록 효율성이 떨어진다. 하지만 선택 정렬은 추가적인 메모리가 필요하지 않고, 구현이 간단하여 작은 크기의 리스트에 대해서는 꽤 효과적일 수 있다.

void selectionSort(int[] arr) {
	// 배열의 모든 요소를 반복하며 정렬 수행
    for (int i = 0; i < arr.length - 1; i++) {
    	// 현재 위치부터 끝까지의 요소 중 가장 작은 값을 찾음
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // 현재 위치의 요소와 가장 작은 값을 가진 요소를 교환
        swap(arr, i, minIdx);
    }
}

2. 삽입 정렬(Insertion Sort)

  • 시간복잡도
    • Avg: O(n^2)
    • Worst: O(n^2)
    • Best: O(n)

삽입 정렬은 정렬되지 않은 부분 리스트에서 값을 하나씩 추출하며 이미 정렬된 부분 리스트에 삽입하여 정렬하는 방식으로 동작한다.

  1. 정렬되지 않은 부분 리스트에서 첫 번째 요소를 선택한다(처음에는 정렬된 부분 리스트는 비어있다).

  2. 선택한 요소를 정렬된 부분 리스트에서 적절한 위치에 삽입한다. 이를 위해 정렬된 부분 리스트를 역순으로 탐색하면서 삽입할 위치를 찾는다.

  3. 선택한 요소를 찾은 위치에 삽입한 후, 다음 정렬되지 않은 요소를 선택하여 위 과정을 반복한다.

  4. 정렬되지 않은 부분 리스트의 모든 요소가 정렬될 때까지 위 과정을 반복한다.

삽입 정렬은 선택 정렬과 달리 이미 정렬된 부분 리스트에 대해 비교를 하면서 정렬을 진행하기 때문에, 일반적으로 입력 리스트가 이미 정렬되어 있는 경우에는 빠른 성능을 보인다. 그러나 최악의 경우에는 시간 복잡도가 O(n^2)이기 때문에 큰 입력에 대해서는 비효율적일 수 있다.

void insertionSort(int[] arr) {
	// 배열의 두 번째 요소부터 시작하여 삽입 정렬 수행
	for (int i = 1; i < arr.length; i++) {
		int tmp = arr[i];
		int j = i - 1;
		// 정렬된 부분 리스트를 역순으로 탐색하며 삽입할 위치를 찾음
		while (j >= 0 && tmp < arr[j]) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = tmp;
	}
}

3. 버블 정렬(Bubble Sort)

  • 시간복잡도
    • Avg: O(n^2)
    • Worst: O(n^2)
    • Best: O(n)

버블 정렬은 인접한 두 요소를 비교하여 필요에 따라 서로 위치를 교환하여 리스트를 정렬한다. 이러한 과정이서 가장 큰(또는 가장 작은) 요소가 맨 끝으로 이동한다. 이 과정을 반복하여 리스트 전체가 정렬될 때까지 진행한다.

  1. 리스트의 첫 번째 요소부터 시작하여 인접한 요소를 순차적으로 비교한다.

  2. 인접한 요소를 비교하여 정렬된 순서가 아니면 두 요소의 위치를 교환한다.

  3. 리스트의 끝까지 이러한 비교와 교환 과정을 반복한다.

  4. 리스트의 끝까지 한 번의 전체 순회 동안 요소의 교환이 일어나지 않으면 정렬이 완료된것으로 간주한다.

이해하기 쉬운 알고리즘이지만, 특히 입력 리스트가 이미 거의 정렬되어있는 경우에는 매우 효율적이다. 그러나 입력 리스트의 크기가 큰 경우에는 비효율적일 수 있다.

void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

4. 병합 정렬(Merge Sort)

  • 시간복잡도
    • Avg: O(n log n)
    • Worst: O(n log n)
    • Best: O(n log n)

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 정렬되는 방식이다. 리스트를 더 작은 단위로 나눈 다음, 나누어진 부분 리스트들을 정렬하고 합병하여 전체 지스트를 정렬하는 방식이다. 병합 정렬은 일반적으로 재귀적으로 구현되며, 각 재귀 단계에서 리스트를 반으로 나누는 작업이 이루어진다.

  1. 리스트를 절반으로 분할하는 단계(Divide)

    • 리스트를 반으로 나누어 두 개의 부분 리스트로 분할한다. 이 과정은 재귀적으로 반복되어 리스트의 크기가 1 이하가 될 때까지 반복한다.

  2. 부분 리스트 정렬 및 합병 단계(Conquer)

    • 각 부분 리스트를 재귀적으로 정렬한다. 이는 리스트가 하나의 요소 또는 정렬된 상태가 될 때까지 반복한다.

  3. 합병 단계(Merge)

    • 정렬된 부분 리스트들을 합병하여 하나의 정렬된 리스트로 합친다. 이 과정에서 각 부분 리스트의 첫 번째 요소를 비교하여 작은 순서대로 새로운 리스트에 추가하고, 모든 요소가 합쳐질 때까지 반복한다.

병합 정렬은 입력 데이터에 민감하지 않고, 특히 대규모 데이터에 대해서 효율적으로 동작한다. 그러나 추가적인 메모리 공간이 필요하며, 재귀적인 호출로 인해 스택 오버플로우가 발생할 수 있다.

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

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

    // 재귀 호출을 통한 부분 배열의 정렬
    mergeSort(leftHalf);
    mergeSort(rightHalf);

    // 정렬된 부분 배열들의 병합
    merge(arr, leftHalf, rightHalf);
}

void merge(int[] arr, int[] left, int[] right) {
    int leftIdx = 0, rightIdx = 0, mergedIdx = 0;

    // 두 부분 배열을 비교하면서 병합하는 단계
    while (leftIdx < left.length && rightIdx < right.length) {
        if (left[leftIdx] < right[rightIdx]) {
            arr[mergedIdx++] = left[leftIdx++];
        } else {
            arr[mergedIdx++] = right[rightIdx++];
        }
    }

    // 남은 요소들을 추가하는 단계
    while (leftIdx < left.length) {
        arr[mergedIdx++] = left[leftIdx++];
    }
    while (rightIdx < right.length) {
        arr[mergedIdx++] = right[rightIdx++];
    }
}

5. 힙 정렬(Heap Sort)

  • 시간복잡도
    • Avg: O(n log n)
    • Worst: O(n log n)
    • Best: O(n log n)

힙 정렬은 힙 자료구조를 기반으로 하는 정렬 알고리즘이다. 이 알고리즘은 선택 정렬의 개념과 유사하게 가장 큰(또는 가장 작은) 요소를 반복적으로 힙에서 추출하여 정렬된 리스트를 구성한다. 힙 정렬은 일반적으로 'in-place'정렬 알고리즘 중 하나로 분류되며, 추가적인 메모리를 사용하지 않는다.

  1. 주어진 배열을 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구성한다. 이를 위해 힙 구조의 특성을 이용하여 부모 노드가 자식 노드보다 항상 큰지(최대 힙) 또는 작은지(최소 힙)를 확인한다.

  2. 최상단에 있는 루트 노드(최대 힙의 경우 가장 큰 요소, 최소 힙의 경우 가장 작은 요소)를 추출하여 배열의 마지막 요소와 교환한다. 이를 통해 가장 큰(또는 가장 작은) 요소가 맨 뒤로 이동한다.

  3. 힙의 크기를 줄이고, 새로운 루트 노드를 기준으로 다시 힙을 구성한다.

  4. 위 과정을 반복하여 힙의 크기가 1이 될 때까지 수행한다.

힙 정렬은 선택 정렬과 마찬가지로 정렬이 끝날 때까지 모든 요소를 처리해야 하기 때문에 이미 정렬되어 있는 경우에도 항상 동일한 시간이 소요된다. 또한 안정적인 정렬 알고리즘이 아니기 때문에 동일한 값의 상대적인 순서가 보장되지 않는다.

힙 정렬은 보통 힙 자료구조를 구현하는 것과 병합하여 사용된다. Java의 표준 라이브러리인 java.util.PriorityQueue 클래스는 힙을 기반으로한 우선순위 큐를 제공하며, 이를 활용하여 힙 정렬을 구현할 수 있다.

void heapSort(int[] arr) {
    int n = arr.length;

    // 최대 힙을 구성
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 최대 힙을 기반으로 배열을 정렬
    for (int i = n - 1; i > 0; i--) {
        // 루트 노드(최대값)를 맨 뒤로 이동
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 힙 재구성
        heapify(arr, i, 0);
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i; // 루트 노드
    int left = 2 * i + 1; // 왼쪽 자식 노드
    int right = 2 * i + 2; // 오른쪽 자식 노드

    // 왼쪽 자식 노드가 루트보다 큰 경우
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 오른쪽 자식 노드가 루트보다 큰 경우
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 루트가 변경된 경우에는 힙을 재구성
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

6. 퀵 정렬(Quick Sort)

  • 시간복잡도
    • Avg: O(n log n)
    • Worst: O(n^2) (피봇 선택에 따라 다름)
    • Best: O(n log n)

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 하는 정렬 알고리즘 중 하나이다. 평균적으로 매우 빠른 속도를 보이며, 많은 정렬 알고리즘 중에서도 가장 많이 사용된다. 이 알고리즘은 주어진 배열을 기준 요소(pivot)를 기준으로 두 개의 하위 배열로 분할하고, 각 하위 배열을 재귀적으로 정렬하여 최종적으로 전체 배열을 정렬하는 방식이다.

  1. 기준 요소(pivot) 선택

    • 배열에서 하나의 요소를 기준으로 선택한다. 일반적으로 첫 번째 요소, 마지막 요소, 또는 배열의 중간 요소가 선택된다.

  2. 파티션(partitioning)

    • 선택한 기준 요소를 기준으로 배열을 두 개의 하위 배열로 분할한다. 기준 요소보다 작은 요소는 왼쪽 하위 배열로, 큰 요소는 오른쪽 하위 배열로 이동된다. 이 과정에서 파티션 함수(partition function)가 사용된다.

  3. 재귀적으로 정렬

    • 분할된 하위 배열에 대해 재귀적으로 퀵 정렬을 수행한다.

  4. 병합(합병)

    • 재귀적인 정렬이 완료된 후에는 하위 배열들을 병합하여 전체 배열을 정렬한다.

퀵 정렬은 'in-place' 정렬 알고리즘으로, 추가적인 메모리를 사용하지 않는다. 그러나 퀵 정렬은 안정적이지 않은 정렬 알고리즘으로, 동일한 값의 상대적인 순서가 보장되지 않는다.

void quickSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    
    quickSort(arr, 0, arr.length - 1);
}

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

트리 정렬(Tree Sort)

  • 시간복잡도
    • Avg: O(n log n)
    • Worst: O(n^2) (특정한 트리 구조에 따라 다름)
    • Best: O(n log n)

트리 정렬은 이진 탐색 트리(Binary Search Tree, BST) 자료구조를 사용하여 정렬을 수행하는 정렬 알고리즘이다.

  1. 주어진 배열의 모든 요소를 이진 탐색 트리에 삽입.

  2. 이진 탐색 트리에서 중위 순회(In-order Traversal)를 수행한다. 이렇게 하면 트리의 모든 요소를 정렬된 순서대로 방문할 수 있다.

  3. 중위 순회된 요소들을 순서대로 배열에 다시 저장한다.

이진 탐색 트리는 각 노드가 두 개의 자식 노드를 가질 수 있는 이진 트리로, 왼쪽 자식 노드는 해당 노드보다 작은 값을 갖고 오른쪽 자식 노드는 해당 노드보다 큰 값을 갖는다. 따라서 중위 순회를 수행하면 모든 요소가 정렬된 순서로 출력된다.

트리 정렬은 일반적으로 효율적인 알고리즘으로 간주되지만, 최악의 경우에는 트리가 편향되어 있을 수 있어 시간 복잡도가 O(n^2)가 될 수 있다. 이를 방지하기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree)를 사용할 수 있다. 대표적으로 AVL 트리나 레드-블랙 트리 등이 있다.

트리 정렬은 추가적인 메모리 공간을 필요로 한다. 그러나 이진 탐색 트리의 균형을 유지하는 작업이 추가로 필요할 수 있다. 따라서 퀵 정렬이나 병합 정렬과 같은 다른 정렬 알고리즘과 비교했을 때 성능이 조금 떨어질 수 있다.

// 이진 탐색 트리의 노드 클래스
class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

// 이진 탐색 트리 클래스
class BinarySearchTree {
    Node root;

    // 이진 탐색 트리에 새로운 요소를 삽입하는 메서드
    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key) {
            root.left = insertRec(root.left, key);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key);
        }
        return root;
    }

    // 중위 순회를 통해 정렬된 배열을 반환하는 메서드
    void inOrder(Node root, int[] arr, int[] index) {
        if (root != null) {
            inOrder(root.left, arr, index);
            arr[index[0]++] = root.key;
            inOrder(root.right, arr, index);
        }
    }
}

public class TreeSort {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        int n = arr.length;

        // 이진 탐색 트리 생성
        BinarySearchTree bst = new BinarySearchTree();
        for (int i = 0; i < n; i++) {
            bst.insert(arr[i]);
        }

        // 중위 순회를 통해 정렬된 배열 얻기
        int[] sortedArr = new int[n];
        bst.inOrder(bst.root, sortedArr, new int[]{0});

        // 정렬된 배열 출력
        System.out.print("정렬된 배열: ");
        for (int num : sortedArr) {
            System.out.print(num + " ");
        }
    }
}

후기

정렬 알고리즘 파고들수록 참 어려운거같다......ㅎ

profile
wujin
이전 포스트

[Java] 추상 클래스(Abstract Class), 인터페이스(Interface)

다음 포스트

[Algorithm] 정렬 알고리즘

0개의 댓글