정렬 알고리즘이란?

개요

• 정렬 알고리즘은 데이터를 일정한 순서로 배치하는 알고리즘임
• 코딩 테스트와 실무 프로젝트에서 매우 자주 사용됨
• 데이터의 크기와 특성에 따라 적절한 알고리즘을 선택하는 것이 성능을 크게 좌우함

정렬 알고리즘의 분류

비교 정렬

• 데이터 간의 상대적 크기 관계를 비교하여 정렬하는 방식임
• 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬이 해당됨
• 이론적 하한선은 $O(n \log n)$임

비교하지 않는 정렬

• 데이터의 특성을 활용하여 직접 위치를 결정함
• 계수 정렬, 기수 정렬이 해당됨
• 특정 조건에서 $O(n)$까지 가능함

정렬 알고리즘 성능 비교

알고리즘	평균 시간 복잡도	최악 시간 복잡도	최선 시간 복잡도	공간 복잡도	안정성
버블 정렬	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	안정
선택 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	불안정
삽입 정렬	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	안정
병합 정렬	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	안정
퀵 정렬	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(\log n)$	불안정
힙 정렬	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	불안정
계수 정렬	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(k)$	안정
기수 정렬	$O(d \times n)$	$O(d \times n)$	$O(d \times n)$	$O(n + k)$	안정

주요 정렬 알고리즘

버블 정렬

• 인접한 두 요소를 비교하여 크기 순서가 맞지 않으면 교환하는 방식임
• 거품이 수면으로 올라오는 것처럼 큰 요소가 배열의 끝으로 이동함
• 각 패스마다 가장 큰 요소가 맨 뒤로 정렬됨
• 시간 복잡도
  • 평균: $O(n^2)$
  • 최악: $O(n^2)$
  • 최선: $O(n)$
• 공간 복잡도
  • $O(1)$ (추가 메모리 불필요)
• 안정성
  • 안정적임
• 구현이 단순하지만 성능이 매우 떨어짐

class="highlight">

void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                // 교환
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        // 교환이 없으면 이미 정렬된 상태
        if (!swapped) break;
    }
}