1.1 개념

정렬: 레코드 집합을 특정 키 값의 크기를 기준으로 오름차순 또는 내림차순으로 재배열하는 작업

안정성: 동일 키 값을 가진 레코드들이 정렬 후에도 원본 순서를 유지하면 안정적, 그렇지 않으면 불안정

1.2 일반적인 응용

• 대학 순위 산정
• 상품 정렬 시스템

2.1 삽입 정렬

두 번째 요소부터 기준 설정, 이전 요소들과 비교하며 적절한 위치에 삽입

public static void 삽입정렬(int[] 배열) {
    for (int i = 1; i < 배열.length; i++) {
        int 현재값 = 배열[i];
        int j = i - 1;
        while (j >= 0 && 배열[j] > 현재값) {
            배열[j + 1] = 배열[j];
            j--;
        }
        배열[j + 1] = 현재값;
    }
}

특징:

• 데이터 유사 정렬 상태에서 효율적
• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)
• 안정적

2.2 셸 정렬

삽입 정렬 개선, 간격(gap) 설정하여 부분 배열 정렬 후 간격 축소

public static void 셸정렬(int[] 배열) {
    int 간격 = 배열.length / 2;
    while (간격 > 0) {
        for (int i = 간격; i < 배열.length; i++) {
            int 임시 = 배열[i];
            int j = i;
            while (j >= 간격 && 배열[j - 간격] > 임시) {
                배열[j] = 배열[j - 간격];
                j -= 간격;
            }
            배열[j] = 임시;
        }
        간격 /= 2;
    }
}

특징:

• 간격 1에서 삽입 정렬로 전환
• 시간 복잡도: O(n¹·²⁵ ~ n¹·⁶)
• 불안정

2.3 선택 정렬

최소값 탐색 후 현재 위치와 교환

public static void 선택정렬(int[] 배열) {
    for (int i = 0; i < 배열.length - 1; i++) {
        int 최소위치 = i;
        for (int j = i + 1; j < 배열.length; j++) {
            if (배열[j] < 배열[최소위치]) 
                최소위치 = j;
        }
        int 임시 = 배열[최소위치];
        배열[최소위치] = 배열[i];
        배열[i] = 임시;
    }
}

특징:

• 시간 복잡도: O(n²)
• 실무에서 비효율적

2.4 버블 정렬

인접 요소 비교하며 교환, 라운드마다 최대값이 끝으로 이동

public static void 버블정렬(int[] 배열) {
    for (int i = 0; i < 배열.length - 1; i++) {
        boolean 교환발생 = false;
        for (int j = 0; j < 배열.length - i - 1; j++) {
            if (배열[j] > 배열[j + 1]) {
                int 임시 = 배열[j];
                배열[j] = 배열[j + 1];
                배열[j + 1] = 임시;
                교환발생 = true;
            }
        }
        if (!교환발생) break;
    }
}

특징:

• 안정적
• 간단하지만 대규모 데이터에 비효율적

2.5 힙 정렬

최대 힙 구성 후 루트와 마지막 요소 교환, 힙 크기 축소하며 반복

public static void 힙정렬(int[] 배열) {
    // 최대 힙 생성
    for (int i = 배열.length / 2 - 1; i >= 0; i--)
        힙조정(배열, 배열.length, i);
    
    // 요소 추출 및 힙 조정
    for (int i = 배열.length - 1; i > 0; i--) {
        int 임시 = 배열[0];
        배열[0] = 배열[i];
        배열[i] = 임시;
        힙조정(배열, i, 0);
    }
}

private static void 힙조정(int[] 배열, int 힙크기, int 부모) {
    int 최대 = 부모;
    int 왼쪽 = 2 * 부모 + 1;
    int 오른쪽 = 2 * 부모 + 2;
    
    if (왼쪽 < 힙크기 && 배열[왼쪽] > 배열[최대]) 
        최대 = 왼쪽;
    if (오른쪽 < 힙크기 && 배열[오른쪽] > 배열[최대]) 
        최대 = 오른쪽;
        
    if (최대 != 부모) {
        int 교환 = 배열[부모];
        배열[부모] = 배열[최대];
        배열[최대] = 교환;
        힙조정(배열, 힙크기, 최대);
    }
}

특징:

• 대용량 데이터에 적합
• 시간 복잡도: O(n log n)
• 불안정

2.6 퀵 정렬

피벗 선택 후 분할 정복, 좌측엔 작은 값, 우측엔 큰 값 배치

2.6.1 호어 분할

private static int 분할(int[] 배열, int 시작, int 끝) {
    int 피벗 = 배열[시작];
    int i = 시작 + 1;
    int j = 끝;
    while (i <= j) {
        while (i <= 끝 && 배열[i] <= 피벗) i++;
        while (j > 시작 && 배열[j] >= 피벗) j--;
        if (i < j) {
            int 임시 = 배열[i];
            배열[i] = 배열[j];
            배열[j] = 임시;
        }
    }
    배열[시작] = 배열[j];
    배열[j] = 피벗;
    return j;
}

2.6.2 삼중 분할

public static void 삼중분할(int[] 배열, int 왼쪽, int 오른쪽) {
    if (왼쪽 >= 오른쪽) return;
    int 피벗 = 배열[new Random().nextInt(오른쪽 - 왼쪽) + 왼쪽];
    int l = 왼쪽 - 1;
    int r = 오른쪽 + 1;
    int i = 왼쪽;
    while (i < r) {
        if (배열[i] < 피벗) {
            l++;
            int 임시 = 배열[l];
            배열[l] = 배열[i];
            배열[i] = 임시;
            i++;
        } else if (배열[i] > 피벗) {
            r--;
            int 임시 = 배열[r];
            배열[r] = 배열[i];
            배열[i] = 임시;
        } else {
            i++;
        }
    }
    삼중분할(배열, 왼쪽, l);
    삼중분할(배열, r, 오른쪽);
}

특징:

• 피벗 선택 최적화 필요
• 평균 시간 복잡도: O(n log n)

2.7 병합 정렬

배열 분할 후 정렬하며 병합

public static void 병합정렬(int[] 배열) {
    if (배열.length < 2) return;
    int 중간 = 배열.length / 2;
    int[] 왼쪽 = Arrays.copyOfRange(배열, 0, 중간);
    int[] 오른쪽 = Arrays.copyOfRange(배열, 중간, 배열.length);
    
    병합정렬(왼쪽);
    병합정렬(오른쪽);
    병합(배열, 왼쪽, 오른쪽);
}

private static void 병합(int[] 결과, int[] 왼쪽, int[] 오른쪽) {
    int i = 0, j = 0, k = 0;
    while (i < 왼쪽.length && j < 오른쪽.length) {
        if (왼쪽[i] <= 오른쪽[j]) 
            결과[k++] = 왼쪽[i++];
        else 
            결과[k++] = 오른쪽[j++];
    }
    while (i < 왼쪽.length) 결과[k++] = 왼쪽[i++];
    while (j < 오른쪽.length) 결과[k++] = 오른쪽[j++];
}

특징:

• 안정적
• 시간 복잡도: O(n log n)
• 공간 복잡도: O(n)