본문 바로가기
CS 정리/알고리즘

정렬 알고리즘 (with Java 코드)

실패 수집가 2025. 4. 23. 16:46

목차

  1. 정렬 알고리즘이란?
  2. 버블 정렬
  3. 선택 정렬
  4. 삽입 정렬
  5. 퀵 정렬
  6. 병합 정렬
  7. 힙 정렬
  8. Java 내장 정렬
  9. 마무리

 

1. 정렬 알고리즘이란?

정렬(Sorting)은 데이터를 일정한 순서(오름차순, 내림차순 등)로 나열하는 알고리즘.
많은 알고리즘의 전처리로 사용되며, 시간복잡도와 메모리 효율에 따라 다양한 방식이 존재함.

 

 

2. 버블 정렬 (Bubble Sort)

- 인접한 두 값을 비교하여, 큰 값을 뒤로 보내며 정렬함

- 가장 단순하지만 비효율적*임

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

초기:     [5, 3, 8, 4, 2]
1회전:    [3, 5, 4, 2, 8]
2회전:    [3, 4, 2, 5, 8]
3회전:    [3, 2, 4, 5, 8]
4회전:    [2, 3, 4, 5, 8]  <- 정렬 완료

 

Java 코드

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

 

 

*버블 정렬이 비효율적인 이유

  1. 불필요한 비교와 스왑이 많음
    • 인접한 두 원소만 비교하므로, 한 번의 패스로는 거의 정렬 효과가 없음
    • 정렬이 거의 끝난 상태에서도 마지막까지 모든 요소를 비교해야 함
  2. 스왑 횟수가 많음
    • 선택 정렬은 한 패스에 최대 한 번만 스왑하지만,
      버블 정렬은 조건만 맞으면 계속 스왑함 → 실행시간 증가
  3. 최적화 없이는 항상 O(n²)
    • 이미 정렬된 배열이라도, early termination 처리를 안 하면 무조건 끝까지 다 비교함
  4. 캐시 친화도가 낮음
    • 메모리 접근 방식이 산발적이고, 많은 스왑으로 인해 캐시 적중률이 떨어짐
  5. 실무나 라이브러리에서 쓰이지 않음
    • Python, Java, C++ 모두 버블 정렬은 교육용 예시로만 쓰이고,
      실용적인 경우에는 퀵 정렬, 병합 정렬, 힙 정렬 등이 사용됨

특징 요약

항목 내용
정렬 방식 인접한 두 원소 비교 후 swap
시간복잡도 (최선) O(n) (이미 정렬된 경우)
시간복잡도 (평균/최악) O(n²)
공간복잡도 O(1)
정렬 안정성 ✅ 안정 정렬
in-place 여부 ✅ 가능
특징 단순하지만 비효율적, swap 잦음

 

 

3. 선택 정렬 (Selection Sort)

- 매 단계에서 가장 작은 값을 선택해서 앞쪽에 정렬함

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

초기:     [5, 3, 8, 4, 2]
1단계:    [2, 3, 8, 4, 5]
2단계:    [2, 3, 8, 4, 5]
3단계:    [2, 3, 4, 8, 5]
4단계:    [2, 3, 4, 5, 8]

Java 코드

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

특징 요약

항목 내용
정렬 방식 전체에서 최소값 선택 후 swap
시간복잡도 O(n²) (모든 경우 동일)
공간복잡도 O(1)
정렬 안정성 ❌ 불안정 정렬
in-place 여부 ✅ 가능
특징 비교 횟수는 고정, swap은 적음

 

 

4. 삽입 정렬 (Insertion Sort)

- 왼쪽부터 차례로 정렬된 상태를 유지하면서, 현재 값을 그에 맞는 위치에 삽입하는 방식

- 카드 게임에서 손에 카드를 정렬하며 끼워넣는 방식과 유사

- 이미 정렬된 배열일수록 빠름

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

초기:     [5, 3, 8, 4, 2] // 첫 번째 원소(5)는 이미 정렬되어 있다고 가정
1단계:    [3, 5, 8, 4, 2] // 두 번째 원소(3)를 왼쪽으로 비교하여 5보다 작으므로 앞으로 삽입
2단계:    [3, 5, 8, 4, 2] // 다음 원소(8)는 이미 정렬된 자리
3단계:    [3, 4, 5, 8, 2] // 다음 원소(4)는 8보다 작으므로 4와 8을 교환, 또 4는 5보다 작으므로 계속 앞으로
4단계:    [2, 3, 4, 5, 8] // 마지막 원소(2)는 계속 앞으로 밀어서 제일 앞으로 삽입

Java 코드

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

특징 요약

항목 내용
정렬 방식 정렬된 범위에 원소를 삽입
시간복잡도 (최선) O(n) (거의 정렬된 경우)
시간복잡도 (평균/최악) O(n²)
공간복잡도 O(1)
정렬 안정성 ✅ 안정 정렬
in-place 여부 ✅ 가능
특징 거의 정렬된 배열에 매우 효율적, 캐시 친화도 좋음

 

 

5. 퀵 정렬 (Quick Sort)

- 분할 정복(Divide and Conquer) 기반의 정렬.

- 배열에서 하나의 요소(피벗, pivot)를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하고,
  양쪽 부분 배열을 재귀적으로 정렬함.

- 평균 성능 매우 우수

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

초기:        [5, 3, 8, 4, 2]
pivot = 5
분할:        [3, 4, 2] + [5] + [8]

왼쪽 재귀:   [3, 4, 2]
pivot = 4
분할:        [3, 2] + [4] + []

왼쪽 재귀:   [3, 2]
pivot = 2
분할:        [] + [2] + [3]      → 정렬됨: [2, 3]

합치면:      [2, 3] + [4]        → 정렬됨: [2, 3, 4]

오른쪽 [8]은 길이 1 → 그대로 유지

최종 결과:   [2, 3, 4] + [5] + [8]
정렬 완료:   [2, 3, 4, 5, 8]

Java 코드

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[(left + right) / 2];
    int index = partition(arr, left, right, pivot);
    quickSort(arr, left, index - 1);
    quickSort(arr, index, right);
}

int partition(int[] arr, int left, int right, int pivot) {
    while (left <= right) {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;
        if (left <= right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}

특징 요약

항목 내용
정렬 방식 피벗 기준으로 분할 정복
시간복잡도 (평균) O(n log n)
시간복잡도 (최악) O(n²) (pivot 선택 나쁠 때)
공간복잡도 O(log n) (재귀 호출 스택)
정렬 안정성 ❌ 불안정 정렬
in-place 여부 ✅ 가능
특징 평균 성능 우수, 실무에서 가장 많이 사용됨, 데이터가 클수록 유리

 

 

6. 병합 정렬 (Merge Sort)

- 반으로 나눈 후 정렬된 상태로 병합하는 분할 정복 알고리즘

- 배열을 절반으로 분할함 → 더 이상 나눌 수 없을 때까지 (길이 1이 될 때까지)

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

초기: [5, 3, 8, 4, 2]
→ [5, 3], [8, 4, 2]
→ [5], [3], [8], [4], [2]  ← 분할 완료
→ [3, 5], [4, 8], [2]      ← 병합 (정렬)
→ [3, 5], [2, 4, 8]
→ [2, 3, 4, 5, 8]          ← 최종 병합

Java 코드

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int t = 0; t < temp.length; t++) {
        arr[left + t] = temp[t];
    }
}

특징 요약

항목 내용
정렬 방식 반으로 나누고 병합
시간복잡도 O(n log n) (모든 경우 동일)
공간복잡도 O(n) (보조 배열 필요)
정렬 안정성 ✅ 안정 정렬
in-place 여부 ❌ 불가능 (추가 메모리 필요)
특징 성능 안정적, 대용량 데이터에 적합

 

* 병합 정렬을 사용하면 좋은 경우

  • 정렬 안정성(stability)이 중요한 경우
  • 최악 성능도 보장되어야 하는 경우
  • 파일/디스크 정렬 등 외부 정렬 환경
  • 병렬 처리(split → 병합 구조 활용)에 유리

 

 

7. 힙 정렬 (Heap Sort)

- 완전 이진 트리 형태의 힙(Heap) 자료구조를 이용하여 정렬하는 알고리즘
- 보통 최대 힙(max heap)을 사용해서 내림차순, 최소 힙(min heap)을 사용해서 오름차순 정렬을 수행함.
  최대 힙(Max-Heap): 부모 노드 ≥ 자식 노드
  최소 힙(Min-Heap): 부모 노드 ≤ 자식 노드

 

- 방법
  1) 배열을 힙 구조(보통 최대 힙)로 변환
  2) 루트(가장 큰 값)를 끝으로 보내고, 힙 크기를 줄인 뒤 다시 heapify
  3) 이 과정을 반복하여 정렬 완료

 

- heapify: 어떤 노드를 기준으로, 그 하위 트리를 힙(Heap) 구조로 만드는 과정 

예시: [5, 3, 8, 4, 2] → 최대 힙 → 정렬

최대 힙 생성: [8, 4, 5, 3, 2]

8 ↔ 2 스왑 → [2, 4, 5, 3, 8], heapify → [5, 4, 2, 3, 8]

5 ↔ 3 스왑 → [3, 4, 2, 5, 8], heapify → [4, 3, 2, 5, 8]

... 반복

최종 정렬: [2, 3, 4, 5, 8]

Java 코드

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

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

    // 2. 힙에서 하나씩 꺼내서 뒤로 이동
    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 swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        heapify(arr, n, largest);
    }
}

시간 복잡도

경우 시간복잡도 설명
최선 O(n log n) 힙 구성 + 추출 반복
평균 O(n log n) 항상 일정함
최악 O(n log n) 균일한 성능
공간복잡도 O(1) 추가 메모리 필요 없음

특징 요약

항목 설명
정렬 안정성 ❌ 불안정 (동일 값 순서 유지 X)
in-place 정렬 ✅ 가능
캐시 친화도 ❌ 낮음 (heapify 시 불연속 접근)
성능 안정성 ✅ 항상 O(n log n)
라이브러리 사용 Python: heapq, Java: PriorityQueue (내장 정렬에는 사용 X)

 

 

8. Java 내장 정렬

1차원 배열 정렬

Arrays.sort(arr); // 오름차순

내림차순 정렬 (객체형 배열만 가능)

Integer[] arr = {3, 5, 1};
Arrays.sort(arr, Collections.reverseOrder());

2차원 배열 정렬 (예: 좌표)

Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

 

 

9. 마무리

✅ 시간복잡도 & 공간복잡도

정렬 알고리즘 최선 시간복잡도 평균 시간복잡도 최악 시간복잡도 공간복잡도
버블 정렬 O(n) 이미 정렬된 경우 혹은 최적화 O(n²) O(n²) O(1)
선택 정렬 O(n²) O(n²) O(n²) O(1)
삽입 정렬 O(n) O(n²) O(n²) O(1)
퀵 정렬 O(n log n) O(n log n) O(n²) O(log n)
병합 정렬 O(n log n) O(n log n) O(n log n) O(n)
힙 정렬 O(n log n) O(n log n) O(n log n) O(1)

 

✅ 정렬 안정성 & in-place 여부

* 정렬 안정성(Stable Sorting): 동일한 키(값)를 가진 원소들의 상대적 순서가 정렬 후에도 유지되는 성질

정렬 알고리즘 정렬 안정성 내부(in-place) 정렬 여부
버블 정렬 ✅ 안정 ✅
선택 정렬 ❌ 불안정 ✅
삽입 정렬
✅ 안정 ✅
퀵 정렬 ❌ 불안정 ✅
병합 정렬 ✅ 안정 ❌ 외부(out-of-place) 정렬
힙 정렬 ❌ 불안정 ✅

 

 

✅ 특징 요약

정렬 알고리즘 특징 요약
버블 정렬 가장 단순
인접한 값 swap -> 비효율적
최적화 시 최선 O(n)
느림
선택 정렬 가장 작은 값 선택 후 swap
swap 적지만 비교 많음
불안정 정렬
삽입 정렬 거의 정렬된 배열에 빠름
shift 방식
퀵 정렬 분할 정복
평균 성능 최고
최악 O(n²)
실무에서 많이 사용
불안정 정렬
병합 정렬 분할 정복
안정 정렬
항상 일정한 성능
추가 배열 필요 (out-of-place정렬. 메모리 많이 씀)
힙 정렬 힙 자료구조 기반
메모리 효율 좋음
성능 일정 O(n log n)
캐시 친화도 낮음
불안정 정렬

 

 

✅ 퀵 정렬 vs 병합 정렬

항목 퀵 정렬 병합 정렬
기반 원리 분할 정복 (pivot 기준 분할) 분할 정복 (절반 나눈 뒤 병합)
동작 방식 pivot 기준으로 좌우 나누고 재귀 정렬 반으로 나누고, 정렬된 배열 병합
정렬 안정성 ❌ 불안정 (순서 바뀔 수 있음) ✅ 안정 정렬 (순서 유지됨)
공간 복잡도 O(log n) (스택 공간) O(n) (병합용 보조 배열 필요)
정렬 방식 ✅ 내부(in-place) 정렬 ❌ 외부(out-of-place) 정렬
최악 시간복잡도 ❌ O(n²) (pivot 선택이 나쁘면) ✅ O(n log n) 항상 일정함
평균 성능 ✅ O(n log n), 매우 빠름 ✅ O(n log n), 안정적이지만 느릴 수 있음
캐시 친화성 ✅ 좋음 (인접 요소 처리 많음) ❌ 나쁨 (병합 과정 중 불연속 접근)

 

>> 상황별 추천 정렬

메모리를 아끼고 싶을 때 퀵 정렬
항상 일정한 성능이 필요한 경우 병합 정렬
안정 정렬이 중요한 경우 병합 정렬
평균 성능이 중요한 경우 퀵 정렬

 

 

* 참고 링크

티스토리툴바