23.07.03 알고리즘 스터디

삽입 정렬 Insertion Sort

• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식입니다.
• 즉, 대상이 되는 i 번쨰 수에 대해, 이미 정렬되어 있는 왼편의 어디에 삽입하면 되는지를 찾아서 집어넣고,
  i를 ++증가 하면서 오른쪽 끝까지 정렬해 나가는 것입니다.
• 평균 시간복잡도는 O(n^2)
  

핵심

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심입니다.

code

public class InsertionSort {
    public static void main(String[] args {
        int[] arr = {5, 2, 4, 6, 1, 3};
        insertionSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ");
        }
    }

    public static 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 = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

순서 및 코드해석

1. insertionSort 메서드에 정할 배열(arr)을 전달합니다.
2. 배열의 두 번째 인덱스(1번 인덱스)부터 시작하여 각 요소를 변수 key에 저장합니다.
3. key보다 앞에 있는 요소들을 반복문을 통해 뒤쪽으로 하나씩 이동시키면서 이미 정렬된 부분의 올른 위치를 찾습니다.
4. 찾은 위치에 key를 삽입합니다.
   --> 이 과정을 배열의 마지막 요소에 도달할 때까지 반복합니다.

퀵 정렬 Quick sort

• 분할 정복(Divide and Conquer) 방법을 사용하여 배열을 정렬하는 효율적인 알고리즘입니다.
• 다시말해, 퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘입니다.
  또한, 기준값이 어떻게 선정되는지가 시간복잡도에 많은 영향을 미치며, 시간복잡도는 O(n)입니다.

핵심이론

pivot 을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심입니다.

Code

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        quickSort(arr, 0, arr.length - 1);
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

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

    public static 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++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

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

code 및 로직 설명

1. quickSort 메서드에 정렬할 배열(arr), 시작 인덱스(low)와 종료 인덱스(high)를 전달합니다.
2. 배열의 부분 배열이 정렬되지 않은 경우, pivot(피벗) 요소를 기준으로 배열을 분할하여 재귀적으로 정렬을 수행합니다.
3. partition 메서드를 사용하여 각 부분 배열에 대해 pivot 요소를 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 위치시킵니다.
4. 모든 요소들이 올바른 위치에 놓이면 반복이 종료되고 정렬된 배열이 완성됩니다.
   퀵 정렬 알고리즘을 사용하면 평균적으로 O(n log n)의 시간 복잡도로 빠르게 정렬을 수행할 수 있습니다. 그러나 퀵 정렬은 최악의 경우 시간 복잡도가 O(n²)가 되므로, 이럴 경우에는 최악의 경우를 대비해야 합니다

병합 정렬 Merge Sort

분할 정복 방법을 사용하여 데이터를 분할하고 분할한 집합 및 배열을 정렬며 합치는 효율적인 알고리즘입니다.
시간복잡도 평균값은 O(n)입니다.

핵심로직

병합과정중에서, 가장 작은 데이터 집합으로 분할하여, 병합하면서 정렬하는 것이 핵심입니다.

code

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        mergeSort(arr, 0, arr.length - 1);
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

    public static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[arr.length];
        int i = low;
        int j = mid + 1;
        int k = low;

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

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= high) {
            temp[k++] = arr[j++];
        }

        for (int l = low; l <= high; l++) {
            arr[l] = temp[l];
        }
    }
}

코드 및 로직 설명

1. mergeSort 메서드에 정렬할 배열(arr), 시작 인덱스(low)와 종료 인덱스(high)를 전달합니다.
2. 배열을 중간 인덱스(mid)에서 두 하위 배열로 분할한 뒤에 각 배열에 대해 재귀적으로 정렬을 수행합니다.
3. 정렬된 두 배열을 merge 메서드를 이용하여 병합합니다.
4. 병합 과정에서 정렬된 순서가 유지되도록 임시 배열(temp)에 요소를 저장한 다음, 원래 배열(arr)에 복사합니다.
5. 모든 요소들이 올바른 위치에 놓이면 반복이 종료되고 정렬된 배열이 완성됩니다.

병합 정렬 알고리즘은 시간 복잡도가 O(n log n)로 꽤 빠른 정렬 방법이며, 최악의 경우에도 이 복잡도가 유지됩니다. 하지만 공간 복잡도가 O(n)으로 추가적인 메모리를 사용하게 됩니다.
따라서, 필자의 생각으로는 병합 알고리즘은 코테에서 채택하기 좋은 자료구조라고 생각됩니다.

문제링크

1. https://www.acmicpc.net/problem/11399
2. https://www.acmicpc.net/problem/11651
3. https://www.acmicpc.net/problem/10815
4. https://www.acmicpc.net/problem/10816
5. https://www.acmicpc.net/problem/1764
6. https://www.acmicpc.net/problem/11004
7. https://www.acmicpc.net/problem/11728
8. https://www.acmicpc.net/problem/11656
9. https://www.acmicpc.net/problem/11652
10. https://www.acmicpc.net/problem/2822
11. https://www.acmicpc.net/problem/8979
12. https://www.acmicpc.net/problem/11931
13. https://www.acmicpc.net/problem/1931

정렬 리스트 확인 링크

https://www.acmicpc.net/problemset?sort=ac_desc&algo=97
출처1 출처2 출처3