[CS] 정렬

 

알고리즘 문제 풀이에서 정렬(Sorting)은 꼭 알고 있어야 하는 기본이다.

단순 오름차순, 내림차순을 넘어 문제 해결 전제가 되거나, 복잡한 알고리즘의 기반이 된다.

이 포스트에서는 정렬 알고리즘의 종류, 시간복잡도

마지막으로 Java에서의 정렬에 대해 작성한다

 

---

 

1. 정렬(Sorting)이란?

정렬이란 데이터를 일정한 기준에 따라 순서를 재배열하는 작업이다.

대표적인 예시로는 오름차순으로 1, 2, 3, 4와 같이 커지는 방향으로 정렬한다.

 

- 효율적인 탐색이나 비교를 위해

- 중복을 제거하거나 우선순위 처리를 위해

- 이진 탐색을 위해

 

위의 세 가지 경우에서 정렬은 필수적으로 사용된다.

 

 

 

2. 정렬의 종류

정렬 방식엔 다양한 종류가 있는데, 대표적인 정렬 방식에 대해 알아보자.

각 정렬은 오름차순을 기준으로 설명했다!

 

 

1) 버블 정렬(Bubble Sort)

로직 : 인접한 두 요소를 비교하여 큰 수를 뒤로 보내는 과정을 반복한다.

거품(bubble)이 물 위로 올라오듯, 가장 큰 숫자가 뒤로 한 칸씩 이동한다.

버블 정렬을 시각화한 그림

 

- 시간복잡도 : (최악/평균) O(n^2), 최선 O(n)

 

시간복잡도가 n^2이기 때문에 많은 양의 데이터나, 코딩 테스트에서는 적합하지 않다.

보통 temp 라는  임시 변수를 통해 값을 저장하고 교환한다.

 

public 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]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

 

 

 

 

2) 선택 정렬(Selection Sort)

로직 : 가장 작은 값을 찾아 맨 앞과 교환한다. 그 다음 값을 찾아 두 번째와 교환한다 (반복)

여러 값 중 하나를 선택 하고, 그 값을 제 위치에 넣어준다.

 

선택 정렬을 시각화한 그림

 

- 시간복잡도 :  항상 O(n^2)

 

시간 복잡도가 좋지 않기 때문에, 메모리를 거의 쓰지 않고 단순한 정렬을 원할 때 사용한다.

같은 값이 많을 경우, 순서가 바뀔 수 있어 안정성이 떨어진다.

 

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

 

 

 

3) 삽입 정렬(Insertion Sort)

로직 : 현재 값을 앞쪽의 정렬된 리스트에서 알맞은 위치에 끼워 넣는다 (반복)

쉽게 생각하면 카드 더미가 있을 때 한 장씩 정렬된 위치에 끼워 넣는다.

즉 현재 정렬해야 될 대상을 기존에 정렬된 리스트에서 맞는 위치에 삽입한다.

 

삽입 정렬을 시각화한 그림

 

- 시간복잡도 :  평균/최악 O(n^2), 최선 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;
    }
}

 

 

 

4) 병합 정렬(Merge Sort)

로직 : 배열을 반으로 나누고, 각각 정렬한 후 두 배열을 병합한다

책 더미를 순서대로 해야할 때, 반으로 나누고 각각 순서대로 만든 후

두 더미를 다시 하나의 더미로 합친다고 생각하면 쉽다.

 

병합 정렬 시각

 

- 시간복잡도 : 항상 O(n log n) 

- 공간복잡도 : O(n)

 

안정성이 뛰어나기 때문에, 데이터가 크고 안정성이 중요할 때 사용한다.

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

public 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) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

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

 

 

 

 

5) 퀵 정렬(Quick Sort)

로직 : 하나의 pivot을 기준으로 작은 값, 큰 값을 양쪽에 배치하여 정렬한다(재귀)

하나의 기준을 정하고 기준을 기준으로 하여 팀을 나누는 느낌!

 

퀵 정렬을 나타낸 영상을 첨부한다.

 

https://www.youtube.com/watch?v=8hEyhs3OV1w

 

- 시간복잡도 : 평균 O(n log n) / 최악 O(n^2) - pivot을 극단으로 선택했을 경우

 

퀵 정렬이라는 이름 답게 빠른 속도를 가지고 있어 속도가 중요할 경우 자주 사용한다.실제 Java의 sort 내부 구현도 quick sort 기반이다!

 

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

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

 

 

 

---

 

 

묵디 묵은 정렬 글 발행..

마음에 안들지만 ~ 일단은 올려!

 

이 글을 정리하면서 느낀점은 알고리즘은 정말

꾸준하게 복습을 해줘야 한다는 거 ..!

 

힙정렬과 추가 정렬들은 다음 포스트에..