contents

자바로 배우는 정렬 알고리즘 – 상세 설명 및 코드 예제

다음은 코딩 테스트 또는 알고리즘 학습을 위한 주요 정렬 알고리즘들의 개념, 시간 복잡도, 작동 방식, 자바 코드 예제를 포함한 상세 가이드입니다.

1. 🫧 버블 정렬 (Bubble Sort)

🧠 개념:
이웃한 값을 반복적으로 비교하여 큰 값을 바깥쪽(끝)으로 밀어냄. 한 번의 반복마다 가장 큰 값이 "거품"처럼 떠오르듯 뒤로 이동함.

🕒 시간 복잡도:

최악/평균: O(n²), 최선(정렬되어 있을 때): O(n)

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // 이미 정렬되었으면 중단
    }
}

2. ✅ 선택 정렬 (Selection Sort)

🧠 개념:
남은 부분에서 가장 작은(또는 큰) 값을 찾아 정렬되지 않은 영역의 맨 앞으로 이동

🕒 시간 복잡도: 항상 O(n²)

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

3. ✋ 삽입 정렬 (Insertion Sort)

🧠 개념:
앞에서부터 요소를 하나씩 정렬된 리스트에 삽입하며 순서 유지

🕒 시간 복잡도:

최악/평균: O(n²), 최선(거의 정렬되어 있음): O(n)

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;
    }
}

4. ✂️ 병합 정렬 (Merge Sort)

🧠 개념:
“분할 정복” 전략. 배열을 반씩 나누고 재귀적으로 정렬한 후 병합.

🕒 시간 복잡도: O(n log n)

void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int[] L = new int[n1], R = new int[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

5. ⚡ 퀵 정렬 (Quick Sort)

🧠 개념:
하나의 기준점(pivot)을 선택하고, 그 기준보다 작은 값과 큰 값으로 파티셔닝한 뒤 재귀적으로 정렬

🕒 시간 복잡도:

평균: O(n log n), 최악: O(n²) (하지만 거의 발생하지 않음)

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

int partition(int[] arr, int left, int right) {
    int pivot = arr[right], i = left - 1;
    for (int j = left; j < right; 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[right]; arr[right] = temp;
    return i + 1;
}

6. 🪜 힙 정렬 (Heap Sort)

🧠 개념:
최대 힙을 구성한 후 루트를 꺼내면서 배열에 정렬. 무조건 O(n log n)에 작동.

🕒 시간 복잡도: O(n log n)

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, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

7. 🔢 카운팅 정렬 (Counting Sort - 정수 전용)

🧠 개념:
각 숫자별 개수를 세어 그 순서로 다시 배열을 구성. 비교 연산 없이 작동.

🕒 시간 복잡도: O(n + k), k는 수의 범위

void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int num : arr) count[num]++;
    int idx = 0;
    for (int num = 0; num < count.length; num++) {
        while (count[num]-- > 0) arr[idx++] = num;
    }
}

8. 🚀 라딕스 정렬 (Radix Sort - 자릿수 기반)

🧠 개념:
각 자릿수(1의 자리 → 10의 자리 ...) 기준으로 반복해서 Counting Sort 적용.

🕒 시간 복잡도: O(d × (n + k))
(d는 자릿수 수, k는 진법 기수)

void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSortByDigit(arr, exp);
}

void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n], count = new int[10];
    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        int d = (arr[i] / exp) % 10;
        output[--count[d]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, n);
}

💡 정렬 알고리즘 비교 요약표

정렬 알고리즘	평균 시간복잡도	제자리 정렬	안정성	특징
Bubble, Selection	O(n²)	✔️	✔️	단순하지만 느림
Insertion	O(n²) / O(n)	✔️	✔️	거의 정렬된 배열엔 빠름
Merge Sort	O(n log n)	❌	✔️	안정정렬, O(n) 공간 필요
Quick Sort	O(n log n)	✔️	❌	빠르지만 최악은 n², 불안정
Heap Sort	O(n log n)	✔️	❌	항상 안정적 시간복잡도, 불안정
Counting/Radix	O(n + k)	부분적으로	✔️	정수 전용, 비교 없는 정렬

✅ 실전 팁

인터뷰에선 Arrays.sort 등 내장 함수보다 직접 구현력 확인을 요구하는 경우 많음.
Quick Sort, Merge Sort, Insertion Sort는 꼭 수기로 구현해 연습하세요.
안정성(Stable Sort), 공간 사용, 정렬 속도 등의 특징을 비교해 쓸 줄 아는 것도 중요합니다.

📘 Shell Sort & TimSort 정렬 알고리즘 – 상세 설명 및 예제

다음은 고급 정렬 알고리즘 중에서 Shell Sort(셸 정렬) 및 TimSort(팀 정렬) 에 대한 개념 설명과 자바 코드 예제입니다.
Shell Sort는 간단하지만 빠른 정렬 방식이고, TimSort는 실제로 많은 언어의 기본 정렬 알고리즘으로 사용됩니다.

1. 🌀 Shell Sort (셸 정렬)

🧠 개념

삽입 정렬의 개선판입니다.
가까운 요소만 정렬하는 것이 아니라, 간격(gap)을 두고 떨어져 있는 요소들을 먼저 정렬하면서 전체 배열의 무질서를 빠르게 줄입니다.
이후 간격을 점점 줄여가면서 정렬을 반복하고, 마지막에는 간격이 1이 되어 일반 삽입 정렬이 수행됩니다.

🔢 갭 시퀀스 예시

가장 일반적인: n/2, n/4, ..., 1
Knuth, Sedgewick 시퀀스 등 더 효율적인 패턴도 있음

⏱ 시간 복잡도

평균: O(n log² n) 정도
최악: O(n^1.5)
인플레이스 정렬 (추가 공간 없음), 불안정 정렬

✅ 자바 예제 코드

void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

🔍 정리

gap = 4 → 인덱스 0, 4, 8... / 1, 5, 9... 식으로 그룹 정렬 진행
gap이 줄어들수록 세부 정렬이 정밀해짐
중간 크기 배열, 메모리 사용이 엄격한 환경에서 효과적

2. 🐎 TimSort (팀 정렬)

🧠 개념

**병합 정렬(Merge Sort)**과 **삽입 정렬(Insertion Sort)**를 결합한 하이브리드 정렬 알고리즘
Python의 sort(), Java의 Arrays.sort(Object[]) 등 실제 언어에서 기본으로 사용되는 고성능 정렬 알고리즘

핵심 원리

배열 내 **이미 정렬된 부분(run)**을 감지
작은 구간은 삽입 정렬 → 정렬 성능 향상
이후 run(정렬된 덩어리)들을 병합 정렬로 합침

📌 실 데이터에서 자주 나타나는 "부분 정렬 상태"를 잘 활용함

⏱ 시간 복잡도

최선: O(n) (이미 거의 정렬된 배열)
평균/최악: O(n log n)
안정 정렬 (Stable), 추가 공간 사용함

✅ 간단한 자바 예제 (개념 설명용)

static final int RUN = 32;

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

    // 1단계: 작은 블록은 삽입 정렬로 처리
    for (int i = 0; i < n; i += RUN)
        insertionSort(arr, i, Math.min((i + RUN - 1), (n - 1)));

    // 2단계: Merge Sort로 정렬된 블록 병합
    for (int size = RUN; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = Math.min((left + 2 * size - 1), (n - 1));
            if (mid < right)
                merge(arr, left, mid, right);
        }
    }
}

void insertionSort(int[] arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int[] L = new int[n1], R = new int[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

🔍 공식 구현에서는...

run(정렬된 연속 구간) 길이를 자동으로 감지하여 더 효율적으로 처리합니다.
병합 정렬 과정에서 **스택(stack)**을 사용해 병합 순서와 메모리 사용을 최적화합니다.
Galloping Merge(갤로핑 병합) 등 특수 방식으로 매우 긴/비정상적인 데이터에도 빠른 속도를 냅니다.
실제 자바(Java)의 Arrays.sort(Object[]), 파이썬의 list.sort(), 그리고 안드로이드 등에서 TimSort가 표준 정렬로 적용되어 있습니다.

👨💻 TimSort를 직접 구현할 필요가 있을까?

보통은 직접 구현할 일이 없습니다.
대부분의 실무·코테에서는 내장 정렬 메서드(Arrays.sort(), Collections.sort() 등)는 이미 TimSort 또는 그에 준하는 빠르고 안정적인 알고리즘을 사용합니다.
하지만 부분 정렬이 많은 대규모 데이터, 안정성(Stable Sort)이 필수인 경우에도 TimSort가 최적의 선택입니다.

📝 정리 표

알고리즘	핵심 아이디어	평균/최악 시간복잡도	안정성	공간	실제 활용 및 특징
Shell Sort	갭 기반 삽입정렬	O(n log²n)/O(n^1.5)	✗	제자리	중·소형, 인플레이스 필요시
TimSort	구간 감지 + 하이브리드	O(n log n)	✔	O(n)	실제 언어 내장, 부분 정렬 강점

references