[Coding Test] 정렬

Do it! 알고리즘 코딩테스트 with JAVA
인프런 로드맵 보기

---

버블 정렬

버블 정렬이란?

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

동작 예시

// 자바 코드 예시: 배열 {5, 3, 8, 4, 2} 를 정렬
int[] arr = {5, 3, 8, 4, 2};
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
// 결과: {2, 3, 4, 5, 8}

시간 복잡도

O(n²)

특징

• 구현이 쉽고 직관적임
• 교환이 많이 발생하여 비효율적임

---

선택 정렬

선택 정렬이란?

대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식

동작 예시

// 자바 코드 예시: 배열 {5, 3, 8, 4, 2} 를 정렬
int[] arr = {5, 3, 8, 4, 2};
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[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
}
// 결과: {2, 3, 4, 5, 8}

시간 복잡도

O(n²)

특징

• 구현이 매우 간단함
• 교환 횟수가 적음(최대 n-1회)
• 데이터가 많아질수록 비효율적

---

삽입 정렬

삽입 정렬이란?

대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

동작 예시

// 자바 코드 예시: 배열 {5, 3, 8, 4, 2} 를 정렬
int[] arr = {5, 3, 8, 4, 2};
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;
}
// 결과: {2, 3, 4, 5, 8}

시간 복잡도

O(n²)

특징

• 이진 탐색 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.

---

퀵 정렬

퀵 정렬이란?

pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식

동작 예시

// 자바 코드 예시: 배열 {5, 3, 8, 4, 2} 를 정렬
int[] arr = {5, 3, 8, 4, 2};
quickSort(arr, 0, arr.length - 1);

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}
// 결과: {2, 3, 4, 5, 8}

시간 복잡도

O(n log n)

특징

• 평균적으로 매우 빠름
• 분할 정복 방식, 재귀 사용
• 대부분의 라이브러리 정렬 기본 구현에 사용됨

---

병합 정렬

병합 정렬이란?

이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식

동작 예시

// 자바 코드 예시: 배열 {5, 3, 8, 4, 2} 를 정렬
int[] arr = {5, 3, 8, 4, 2};
mergeSort(arr, 0, arr.length - 1);

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 l = 0; l < temp.length; l++) arr[left + l] = temp[l];
}
// 결과: {2, 3, 4, 5, 8}

시간 복잡도

O(n log n)

특징

• 항상 안정적으로 빠름
• 추가 메모리 공간 필요
• 안정 정렬, 분할 정복 방식

---

기수 정렬

기수 정렬이란?

데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

동작 예시

// 자바 코드 예시: 배열 {5, 3, 8, 4, 2} 를 정렬 (LSD 방식)
int[] arr = {5, 3, 8, 4, 2};
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
    int[] output = new int[arr.length];
    int[] count = new int[10];
    for (int i = 0; i < arr.length; i++)
        count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < arr.length; i++)
        arr[i] = output[i];
}
// 결과: {2, 3, 4, 5, 8}

시간 복잡도

O(kn) (k = 자릿수)

특징

• 비교 연산을 하지 않음
• 정수, 문자열 등 자릿수 기반 데이터에 적합
• 안정 정렬

---