알고리즘 - 정렬(Sort)

버블 정렬 (Bubble Sort)

인접한 두 자리 데이터를 비교하며 자리를 바꾸는 방식의 정렬
ex) 오름차순 : 두 자리를 비교해서, 작은 값을 앞으로 보냄. 한 바퀴 돈 후에는 가장 큰 수가 맨 뒤로 가므로, 그 다음 바퀴에서는 마지막 값을 빼고 비교

시간복잡도 : O(n₂)

    // 버블 정렬
    public static void bubbleSort(int[] arr) {
        // 1 ~ 배열의 크기까지
        for (int i = 1; i < arr.length - 1; i++) {
            // 0 ~ 배열의 크기까지
            for (int j = 0; j < arr.length - 1; j++) {
                // 비교할 값이 그 다음 값보다 크다면
                if (arr[j] > arr[j + 1]) {
                    // 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

---

삽입 정렬 (Insertion Sort)

앞의 데이터를 정렬해가며 삽입 위치를 찾아 정렬
ex> 오름차순 : 첫 번째 데이터는 비교할 것이 없음, 두 번째 데이터를 앞의 데이터와 비교 후, 맞는 자리를 찾아 삽입, 세 번째 데이터를 앞의 데이터와 비교 후, 맞는 자리를 찾아 삽입 ...

시간복잡도 : O(n₂)

    // 삽입 정렬
    public static void insertionSort(int[] arr) {
        // 1부터 배열의 길이까지
        for (int i = 1; i < arr.length; i++) {
            // i부터 0까지 감소
            for (int j = i; j > 0; j--) {
                // 비교할 값이 그 앞의 값보다 크다면
                if (arr[j] < arr[j - 1]) {
                    // 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                } else {
                    // 아니라면 다음 반복문으로
                    break;
                }
            }
        }
    }

---

선택 정렬 (Selection Sort)

최솟값 또는 최댓값을 찾아서 가장 앞 또는 뒤부터 정렬
시간복잡도 : O(n₂)

ex) 오름차순 : 값들 중 최솟값을 찾음 -> 그것을 맨 앞에 보내기 -> 그 외의 값들 중 최솟값 찾음 -> 반복

    // 선택 정렬
    public static void selectionSort(int[] arr) {
        // 0부터 배열의 길이까지
        for (int i = 0; i < arr.length - 1; i++) {
            // 최솟값 담을 곳 준비
            int min = i;
            // 첫번째 값 그 다음의 값
            for (int j = i + 1; j < arr.length; j++) {
                // 비교할 값이 최솟값보다 작다면
                if (arr[j] < arr[min]) {
                    // 최솟값 등록
                    min = j;
                }
            }
            // 교환
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

---

합병 정렬 (Merge Sort)

배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분까지 정렬하며 합병

시간 복잡도 : O(nlogn)

ex) 오름차순 : 배열을 두 덩어리로 나눈다 (한 덩어리에 들어가는 값이 한개가 될 때까지) -> 나눈 값을 두개씩 합친다 -> 합치는 과정에서 값이 더 작은 것을 앞으로 보냄

추가 저장을 위한 메모리가 필요하지만, 상대적으로 빠르다

    // 합병 정렬
    public static void mergeSort (int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            // 중앙값
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid); // 배열의 좌측 부분
            mergeSort(arr, temp, mid + 1, right); // 배열의 우측 부분

            merge(arr, temp, left, right, mid);
        }
    }

    public static void merge(int[] arr, int[] temp, int left, int right, int mid) {
        // 좌측에서 시작할 값
        int p = left;
        // 우측에서 시작할 값
        int q = mid + 1;
        int index = p;

        // p : 좌측 부분
        // q : 우측 부분
        while (p <= mid || q <= right) {
            // 두 값이 모두 유효범위 안일 때
            if (p <= mid && q <= right) {
                if (arr[p] <= arr[q]) {
                    // q가 p보다 더 크면, temp에 p를 넣고(오름차순이니까) 다음 값 확인
                    temp[index++] = arr[p++];
                } else {
                    // p가 q보다 더 크면, temp에 q를 넣고 다음 값 확인
                    temp[index++] = arr[q++];
                }
            } else if (p <= mid && q > right) {
                // 값이 왼쪽에만 남아있는 경우
                temp[index++] = arr[p++];
            } else {
                // 값이 오른쪽에만 남아있는 경우
                temp[index++] = arr[q++];
            }
        }

        // temp에 넣었던 값을 다시 arr에 넣기
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 7, 1, 4};
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

---

힙 정렬 (Heap Sort)

힙 자료구조 형태의 정렬, 기존 배열을 최대 힙으로 구조 변경 후 정렬

시간 복잡도 : O(nlogn)

    // 힙 정렬
    public static void heapSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0 ; i--) {
            heapify(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }

    // 힙 자료구조로 바꿔주는 메서드
    public static void heapify(int[] arr, int parentIdx, int size) {
        // 자식 노드의 위치 가져오기
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;

        if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
            maxIdx = leftIdx;
        }
        if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
            maxIdx = rightIdx;
        }
        if (parentIdx != maxIdx) {
            swap(arr, maxIdx, parentIdx);
            heapify(arr, maxIdx, size);
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 7, 1, 4};

        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

---

퀵 정렬 (Quick Sort)

임의의 기준 값(pivot, 피봇)을 정하고, 그 값을 기준으로 좌우로 분할하며 정렬

시간복잡도 : O(n₂) -> 기준 값이 최소값 또는 최대값일 때 (worst case)

ex) 오름차순 1회차 : 기준값을 고른다 -> 좌측에서 가운데로 진행하며 기준값보다 큰 값을 고른다 -> 우측에서 가운데로 진행하며 기준값보다 작은 값을 고른다. -> 두 값의 자리를 바꾼다 -> 진행이 종료되면 그 곳의 값과 기준값의 자리를 바꾼다

오름차순 2회차 : 자리를 바꾼 기준값의 앞과 뒤로 덩어리를 나눈다 -> 1회차 방법과 같게 정렬 -> 반복

---

트리 정렬 (Tree Sort)

이진 탐색 트리(BST)를 만들어 정렬하는 방식

시간 복잡도 : O(nlogn)

---

기수 정렬 (Radix Sort)

낮은 자리(1의자리, 10의자리, 100의자리 ...) 수부터 정렬
각 원소 간의 비교 연산을 하지 않음 (빠르지만 별도의 메모리가 필요)

시간 복잡도 : O(dn) -> d: 최대 자릿수