Algorithm
정렬

Sort

Sort 정렬 알고리즘을 정리해놓는 공간

안정 정렬과 불안정 정렬

  • 정렬 후에도 같은 값을 가진 원소들의 상대적인 순서가 유지되는 정렬 알고리즘
  • 안정 정렬(Stable Sort)이란 [5a, 3b, 5c]를 정렬해도 [3b, 5a, 5c]로 상대적인 순서가 유지되는 것을 말함
  • 예를 들어 User라는 객체가 있고 나이순으로 정렬하고 싶은데 나머지는 기존 순서를 유지하고 싶다면 안정 정렬을 사용해야 함

선택정렬(Selection Sort)

  • 1번째부터 끝까지 훑어서 가장 작은 1번째, 2번째부터 끝까지 훑어서 가장 작은게 2번째... 정렬이 끝날 때까지 반복함
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};
 
    int min = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            if(arr[j] < arr[min])min = j;
        }
        swap(arr, i, min);
    }
 
    System.out.println(Arrays.toString(arr));
}
 
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

삽입정렬(Insertion Sort)

  • 삽입 정렬은 현재 위치의 값은 TEMP에 저장한 뒤 TEMP보다 큰 값을 한 칸씩 뒤로 밀어내고, 앞의 빈자리에 TEMP가 들어가는 방식으로 정렬하는 알고리즘
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};
 
    for(int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > tmp) {
            // 다음 칸으로 현재 값을 옮김
            arr[j + 1] = arr[j];
            j--;
        }
        // tmp 값을 현재 위치에 삽입
        // 현재 위치는 tmp보다 작은 값의 바로 뒤
        arr[j + 1] = tmp;
    }
 
    System.out.println(Arrays.toString(arr));
}

버블정렬(Bubble Sort)

  • 이중 반복을 돌면서 원소가 자기보다 더 큰 값이 없을 때까지 계속해서 위로 올라가는 방식으로 정렬하는 알고리즘
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};
 
    for(int i = 0; i < arr.length; i ++) {
        // -i를 하는 이유는 정렬함에 따라
        // i개의 가장 큰 원소를 가지기 때문
        for(int j = 0; j < arr.length - i - 1; j ++) {
            if(arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
    }
 
    System.out.println(Arrays.toString(arr));
}
 
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

버블정렬이 최선 케이스 O(n)인 이유

  • 버블정렬에 아래와 같은 조건을 추가하면 최선 케이스가 O(n)이 됨
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8,3,1,5,6,2,9,7,4};
    boolean swapped = false;
 
    for(int i = 0; i < arr.length; i ++) {
        swapped = false;
        // -i를 하는 이유는 정렬함에 따라
        // i개의 가장 큰 원소를 가지기 때문
        for(int j = 0; j < arr.length - i - 1; j ++) {
            if(arr[j] > arr[j + 1]) {
                swapped = true;
                swap(arr, j, j + 1);
            }
            if(!swapped) break;
        }
    }
 
    System.out.println(Arrays.toString(arr));
}
 
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

병합정렬

  • 배열을 원소 1개짜리 배열로 계속해서 쪼개고 쪼개진 부분을 합치면서 정렬하는 방식
⚠️코드 개김
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8, 3, 1, 5, 6, 2, 9, 7, 4};
 
    sorted = new int[arr.length];    // 정렬된 배열을 담을 공간
    mergeSort(arr, 0, arr.length - 1);
 
    System.out.println(Arrays.toString(arr));
}
 
// Top-Down 방식 구현
private static void mergeSort(int[] a, int left, int right) {
 
    /*
     *  left==right 즉, 부분리스트가 1개의 원소만 갖고있는경우
     *  더이상 쪼갤 수 없으므로 return한다.
     */
    if (left == right) return;
 
    int mid = (left + right) / 2;    // 절반 위치
 
    mergeSort(a, left, mid);        // 절반 중 왼쪽 부분리스트(left ~ mid)
    mergeSort(a, mid + 1, right);    // 절반 중 오른쪽 부분리스트(mid+1 ~ right)
 
    merge(a, left, mid, right);        // 병합작업
 
}
 
/**
 * 합칠 부분리스트는 a배열의 left ~ right 까지이다.
 *
 * @param a     정렬할 배열
 * @param left  배열의 시작점
 * @param mid   배열의 중간점
 * @param right 배열의 끝 점
 */
private static void merge(int[] a, int left, int mid, int right) {
    int l = left;        // 왼쪽 부분리스트 시작점
    int r = mid + 1;    // 오른쪽 부분리스트의 시작점
    int idx = left;        // 채워넣을 배열의 인덱스
 
    while (l <= mid && r <= right) {
        /*
         *  왼쪽 부분리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
         *  왼쪽의 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
         */
        if (a[l] <= a[r]) {
            sorted[idx] = a[l];
            idx++;
            l++;
        }
        /*
         *  오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
         *  오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
         */
        else {
            sorted[idx] = a[r];
            idx++;
            r++;
        }
    }
 
    /*
     * 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
     * = 오른쪽 부분리스트 원소가 아직 남아있을 경우
     * 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
     */
    if (l > mid) {
        while (r <= right) {
            sorted[idx] = a[r];
            idx++;
            r++;
        }
    }
 
    /*
     * 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
     * = 왼쪽 부분리스트 원소가 아직 남아있을 경우
     * 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
     */
    else {
        while (l <= mid) {
            sorted[idx] = a[l];
            idx++;
            l++;
        }
    }
 
    /*
     * 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
     */
    for (int i = left; i <= right; i++) {
        a[i] = sorted[i];
    }
}

힙 정렬(Heap Sort)

  • 힙을 사용해서 정렬하는 방법
  • 힙에 데이터를 삽입할 때 O(logN)의 시간복잡도를 가지기 때문에 해당 정렬의 시간 복잡도도 O(NlogN)임
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8, 3, 1, 5, 6, 2, 9, 7, 4};
    Queue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o));
    pq.addAll(Arrays.stream(arr).boxed().toList());
    for (int i = 0; i < arr.length; i++) {
        if(!pq.isEmpty()) arr[i] = pq.poll();
    }
 
    System.out.println(Arrays.toString(arr));
}

퀵 정렬

  • pivot을 기준으로 왼쪽에 피벗보다 큰 값, 오른쪽의 피벗보다 작은 값을 swap하면서 피벗의 위치를 계속 변경함
  • 이 때 피벗의 위치는 더 이상 쪼개지지 않을 때까지 반복함
public static void main(String[] args) throws Exception {
    int[] arr = new int[]{8, 3, 1, 5, 6, 2, 9, 7, 4};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}
 
private static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}
 
private static void quickSort(int[] arr, int left, int right) {
    int part = partition(arr, left, right);
    if (left < part - 1) {
        quickSort(arr, left, part - 1);
    }
    // 더 이상 쪼개지지 않을 때까지
    if (part < right) {
        quickSort(arr, part, right);
    }
}
 
private static int partition(int[] arr, int left, int right) {
    int pivot = arr[(left + right) / 2];
    while (left <= right) { // 해당 부분 배열에 대해 반복
        while (arr[left] < pivot) { //피벗보다 큰 left를 찾음
            left++;
        }
        while (arr[right] > pivot) { //피벗보다 작은 right를 찾음
            right--;
        }
        if (left <= right) { //left가 right보다 왼쪽에 있으면 둘이 자리 바꿈
            swap(arr, left, right);
            left++;
            right--;
        }
    }
    return left;
}
 
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

트리 정렬

  • 이진 탐색 트리를 만들어 정렬하는 방식
  • 추가될 값이 기존 노드 값보다 작으면 왼쪽 자식으로 크거나 같으면 오른쪽 자식 위치로 감

힙 정렬 vs 트리 정렬

  • 힙은 완전 이진 트리의 일종으로 마지막 노드를 제외하면 모두 2개의 자식을 가지고 있는 트리 구조를 의미함
  • 또한 부모의 값이 항상 더 큰 값을 가지는 최대 힙과 부모의 값이 항상 더 작은 값을 가지는 최소 힙이 있음
  • 반면, 이진 탐색 트리의 경우 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 값을 가지는 트리 구조를 의미함
  • 만약 아래와 같이 편향된 이진 탐색 트리가 만들어진다면 트리 정렬의 시간 복잡도는 O(n²)이 될 수 있음
    • 첫 번째 삽입: 트리가 비어 있으므로 탐색 비용은 (O(0)).
    • 두 번째 삽입: 트리의 높이가 1이므로 탐색 비용은 (O(1)).
    • 세 번째 삽입: 트리의 높이가 2이므로 탐색 비용은 (O(2)).
    • ...
    • (N)번째 삽입: 트리의 높이가 (N-1)이므로 탐색 비용은 (O(N-1)).
    • 이를 수식으로 표현하면 (N-1)N/2이므로 O(N²)이 됨
1
 \
  2
   \
    3
     \
      4
       \
        5

정렬 알고리즘 시간/공간 복잡도 및 안정성 비교

정렬 알고리즘최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도공간 복잡도안정성
선택 정렬 (Selection Sort)O(n²)O(n²)O(n²)O(1)Unstable
삽입 정렬 (Insertion Sort)O(n)O(n²)O(n²)O(1)Stable
버블 정렬 (Bubble Sort)O(n)O(n²)O(n²)O(1)Stable
병합 정렬 (Merge Sort)O(n log n)O(n log n)O(n log n)O(n)Stable
힙 정렬 (Heap Sort)O(n log n)O(n log n)O(n log n)O(1)Unstable
퀵 정렬 (Quick Sort)O(n log n)O(n log n)O(n²)O(log n)Unstable
트리 정렬 (Tree Sort)O(n log n)O(n log n)O(n²)O(n)Stable/Unstable (depends on implementation)

자바에서 사용하는 정렬 알고리즘

정렬 방식알고리즘안정성시간 복잡도공간 복잡도사용 대상
Arrays.sort()Dual-Pivot Quicksort불안정(O(n \log n)), (O(n^2))(O(\log n))Primitive 타입 배열
Collections.sort()TimSort안정(O(n \log n))(O(n))객체 데이터 (List)

Arrays.sort()

  • 타입에 따라서 다른 정렬 방식을 씀
    • Primitive -> Dual-Pivot Quicksort
    • Reference -> TimSort
  • ⚠️ 아래는 Dual-Pivot Quicksort 기준
  • 두 개의 피벗으로 배열을 세 부분으로 나눠 정렬
  • 시간 복잡도: 최선/평균 (O(n \log n)), 최악 (O(n^2))
  • 공간 복잡도: (O(\log n))
  • 안정 정렬 아님

Collections.sort()

  • TimSort 사용
  • 합병 정렬과 삽입 정렬의 하이브리드
  • 시간 복잡도: 최선/평균/최악 (O(n \log n))
  • 공간 복잡도: (O(n))
  • 안정 정렬
  • 객체 데이터(List 등) 정렬에 적합

정렬 알고리즘 시간/공간 복잡도 및 안정성 비교

정렬 알고리즘최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도공간 복잡도안정성
선택 정렬 (Selection Sort)O(n²)O(n²)O(n²)O(1)Unstable
삽입 정렬 (Insertion Sort)O(n)O(n²)O(n²)O(1)Stable
버블 정렬 (Bubble Sort)O(n)O(n²)O(n²)O(1)Stable
병합 정렬 (Merge Sort)O(n log n)O(n log n)O(n log n)O(n)Stable
힙 정렬 (Heap Sort)O(n log n)O(n log n)O(n log n)O(1)Unstable
퀵 정렬 (Quick Sort)O(n log n)O(n log n)O(n²)O(log n)Unstable
트리 정렬 (Tree Sort)O(n log n)O(n log n)O(n²)O(n)Stable/Unstable (depends on implementation)

참고 자료

MST탐색