[자료구조] 정렬(Sorting)

정렬(Sorting)이란?

• 정의: 데이터를 특정 기준에 따라 순서대로 나열하는 과정
• 장점:
  - 검색과 탐색 속도 향상
  - 데이터 구조 내에서 일관성을 유지
• 정렬 방식
  - 오름차순(Ascending Order)
  - 내림차순(Descending Order)

---

정렬 알고리즘의 분류

1. 비교 기반 정렬(Comparison Sort)

• 데이터를 비교하며 정렬
• 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬

2. 비교 비기반 정렬(Non-Comparison Sort)

• 데이터를 비교하지 않고 정렬
• 계수 정렬, 기수 정렬

---

버블 정렬(Bubble Sort)

• 정의: 인접한 두 원소를 비교하여 교환하는 방식으로 정렬. 가장 큰 값이 반복적으로 뒤로 이동
• 특징
  - 단순한 정렬 알고리즘
  - 정렬이 거의 되어 있는 경우 유리
• 시간 복잡도
  - 최선: O(n) (이미 정렬된 경우)
  - 최악/평균: O(n²)
• 장단점
  - 장점: 구현이 간단하다.
  - 단점: 비효율적이며 실무에서 잘 사용되지 않음
• 예제

public void bubbleSort(int[] arr) {
    int n = arr.length();
    for (int i = 0; i < n - 1; i++) {
    	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;
            }
        }
    }
}

---

삽입 정렬(Insertion Sort)

• 정의: 정렬된 부분에 새로운 데이터를 삽입하여 정렬
• 특징
  - 정렬된 데이터에 새 데이터를 추가할 때 유리
  - 정렬이 거의 되어 있는 경우 빠름
• 시간 복잡도
  - 최선: O(n) (이미 정렬된 경우)
  - 최악/평균: O(n²)
• 장단점
  - 장점: 간단하며, 적은 데이터에 유리
  - 단점: 데이터가 많을수록 비효율적
• 예제

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

---

선택 정렬(Selection Sort)

• 정의: 매번 최소값(또는 최대값)을 찾아 앞에서부터 정렬
• 특징: 데이터 교환 횟수가 적음
• 시간 복잡도
  - 최선/최악/평균: O(n²)
• 장단점
  - 장점: 교환 횟수가 적음
  - 단점: 시간이 오래 걸림
• 예제

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

---

퀵 정렬(Quick Sort)

• 정의: 피봇을 기준으로 데이터를 두 그룹으로 나누어 정렬
• 특징
  - 분할 정복(Divide and Conquer) 알고리즘
  - 평균적으로 가장 빠름
• 시간 복잡도
  - 최선/평균: O(n log n)
  - 최악: O(n²) (피봇 선택이 나쁠 때)
• 장단점
  - 장점: 평균적으로 빠르다
  - 단점: 최악의 경우 성능이 떨어질 수 있음
• 예제

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

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

---

병합 정렬(Merge Sort)

• 정의: 데이터를 반으로 나누고, 각각을 정렬 후 병합
• 특징
  - 안정적인 정렬
  - 데이터 크기가 클수록 유리
• 시간 복잡도
  - 최선/최악/평균: O(n log n)
• 장단점
  - 장점: 안정적이며 예측 가능한 성능
  - 단점: 추가 메모리 필요
• 예제

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

private void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    System.arraycopy(arr, l, L, 0, n1);
    System.arraycopy(arr, m + 1, R, 0, n2);
    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++];
}

---

계수 정렬(Counting Sort)

• 정의: 특정 값의 빈도를 세어 정렬
• 특징: 데이터의 범위가 제한적인 경우 유리
• 시간 복잡도
  - 최선/최악/평균: O(n + k)
• 장단점
  - 장점: 매우 빠름
  - 단점: 메모리 사용량이 많음

---

기수 정렬(Radix Sort)

• 정의: 자릿수를 기준으로 데이터를 정렬
• 특징: 숫자 또는 문자열 정렬에 유리
• 시간 복잡도
  - 최선/최악/평균: O(d(n + k))