1. 정렬 알고리즘이란?

핵심 항목(Key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업이다.
정렬 알고리즘의 핵심 요소 3가지는 교환, 선택, 삽입이다.

2. 버블 정렬

a. 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 알고리즘
b. 시간복잡도 : O(N²)


버블 정렬 소스코드 (개선 Ver.1)

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

        System.out.println("버블 정렬 후 배열의 요소: ");
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void bubbleSort(int[] arr) {
        boolean isSwapped;
        for (int i = 0; i < arr.length - 1; i++) {
            isSwapped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 인접한 두 원소를 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    isSwapped = true;
                }
            }
            // 이번 패스에서 원소를 교환하지 않았다면 정렬이 끝난 것
            if (!isSwapped) {
                break;
            }
        }
    }
}

위 코드에서는 isSwapped 변수를 추가하여, 각 패스에서 원소 교환이 발생하지 않았는지 여부를 체크한다. 만약 교환이 발생하지 않았다면, 해당 패스에서는 정렬이 끝났다고 판단하고 반복문을 종료함.

이 방법을 사용하면, 이미 정렬된 배열을 정렬하거나, 정렬된 부분이 많은 배열에서는 훨씬 빠른 속도로 정렬을 마칠 수 있다.


버블 정렬 소스코드 (개선 Ver.2)

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

        System.out.println("버블 정렬 후 배열의 요소: ");
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        int lastSwapIndex = n - 1; // 초기값은 배열의 마지막 인덱스로 설정
        while (lastSwapIndex > 0) {
            int endIndex = lastSwapIndex; // 이번 패스에서는 endIndex까지만 검사
            lastSwapIndex = 0; // 다음 패스에서는 초기값을 다시 설정
            for (int i = 0; i < endIndex; i++) {
                if (arr[i] > arr[i + 1]) {
                    // 인접한 두 원소를 교환
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    lastSwapIndex = i; // 마지막으로 교환된 인덱스를 기록
                }
            }
        }
    }
}

위 코드에서는, lastSwapIndex 변수를 추가하여, 이전 패스에서 마지막으로 원소 교환이 일어난 인덱스를 기록한다. endIndex 변수는 이번 패스에서 검사할 마지막 인덱스를 나타낸다. 이전 패스에서 원소 교환이 일어나지 않았다면, lastSwapIndex 값은 초기값인 n - 1로 설정된다. 각 패스가 끝나면, lastSwapIndex 변수를 이전 패스에서 마지막으로 원소 교환이 일어난 인덱스로 업데이트하고, 다음 패스에서는 lastSwapIndex 이후의 인덱스는 검사하지 않는다.

이 방법을 사용하면, 이전에 정렬이 완료된 부분은 더 이상 검사하지 않으므로, 이미 정렬된 배열이나, 정렬된 부분이 많은 배열에서는 훨씬 빠르게 정렬을 마칠 수 있다. 또한, 최선의 경우에는 시간 복잡도가 O(n)이 된다.


버블 정렬 소스코드 (기본ver.)

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

        System.out.println("버블 정렬 후 배열의 요소: ");
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
    }
    public static 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;
                }
            }
        }
    }
}

3. 선택 정렬

a. 가장 작은 값을 찾아 선택 후, 정렬되지 않은 인덱스 중 가장 앞자리와 교환을 반복하는 알고리즘

b. 시간복잡도 : O(N²)

선택 정렬 소스코드

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        selectionSort(arr);
        System.out.println("선택 정렬 후 배열의 요소: ");
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    // 최솟값을 찾습니다
                    minIndex = j;
                }
            }
            // 최솟값을 현재 위치로 옮깁니다
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

선택 정렬 알고리즘도 개선버전이 있다. 양방향 선택 정렬 알고리즘은 최소값을 찾아 옮기는 동시에 최대값도 찾아서 옮긴다. 다만, 시간복잡도에는 큰 변화가 없다.


4. 삽입 정렬

a. 선택한 요소를 앞쪽의 알맞은 위치삽입하는 작업을 반복하여 정렬하는 알고리즘

b. 시간복잡도 : O(N²)

삽입 정렬 소스코드

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("삽입 정렬 후 배열의 요소: ");
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // key 값보다 작은 값을 찾아서 오른쪽으로 이동합니다
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

5. 퀵 정렬

a. 분할 정복(Divide and Conquer) 알고리즘을 이용하여 구현된 정렬 알고리즘
b. 평균적으로 다른 정렬 알고리즘에 비해 빠른 속도를 보여준다.

b. 시간복잡도 : O(n log n) (최악의 경우 O(n²))

  1. 피벗(Pivot)을 선택한다. 피벗은 배열의 중간값이나 첫 번째 값, 마지막 값 등으로 선택할 수 있다.
  2. 피벗을 기준으로 작은 값은 피벗의 왼쪽, 큰 값은 피벗의 오른쪽으로 이동시킨다.
  3. 왼쪽과 오른쪽에 있는 부분 배열에 대해 재귀적으로 위 과정을 반복한다.
  4. 부분 배열의 크기가 1 이하가 되면 정렬이 완료된다.

퀵 정렬 소스코드 (피벗 - 배열의 마지막 값)

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr1 = {10,30,40,25,60,5};
        quickSort(arr1, 0, arr1.length-1);
        System.out.println(Arrays.toString(arr1)); // [5, 10, 25, 30, 40, 60]
    }

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

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }

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

위 코드는 재귀적으로 구현된 퀵 정렬이다. 배열의 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 매개변수로 전달받아, 재귀적으로 부분 배열을 정렬한다. partition 메소드는 피벗을 기준으로 작은 값과 큰 값으로 나누어주는 역할을 한다. 위 코드는 피벗을 배열의 마지막 값으로 선택했다.

5. 병합 정렬

a. 병합 알고리즘(merge sort)은 분할 정복 알고리즘을 이용하여 구현된 정렬 알고리즘이다.
b. 시간복잡도 : O(n log n)

  1. 배열을 반으로 나눈다.
  2. 나누어진 배열의 크기가 1 이하가 될 때까지 재귀적으로 반복한다.
  3. 두 배열을 하나로 합친다. 이 때, 두 배열은 이미 정렬된 상태여야 한다.

알고리즘 도감APP

병합 정렬 소스코드

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr1 = {10,45,30,20,15,45,5};
        mergeSort(arr1,0,arr1.length-1);
        System.out.println(Arrays.toString(arr1));
    }
    public static 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);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tempArr = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;

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

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

        while (j <= right) {
            tempArr[k++] = arr[j++];
        }

        for (int index = 0; index < k; index++) {
            arr[left + index] = tempArr[index];
        }
    }
}

5. 힙 정렬

a. 최대 힙(max heap) 또는 최소 힙(min heap)을 이용한 정렬 알고리즘
b. 시간복잡도 : O(n log n)
c. 최소힙과 최대힙의 시간복잡도는 동일하나 최소힙이 구현이 더 어렵다.

알고리즘 도감APP

힙 정렬 소스코드 (최대 힙 방식)

import java.util.Arrays;

public class HeapSortTest {
    public static void main(String[] args) {
        int[] arr1 = {10, 45, 30, 20, 15, 45, 5};
        heapSort(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 최대 힙 구성
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 힙에서 원소 하나씩 꺼내오며 정렬
        for (int i = n - 1; i >= 0; i--) {
            // 루트 노드를 배열의 가장 뒤쪽으로 이동
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 다시 최대 힙 구성
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 가장 큰 값은 현재 노드로 초기화
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 왼쪽 자식 노드가 더 크면 largest를 왼쪽 자식 노드로 갱신
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 오른쪽 자식 노드가 더 크면 largest를 오른쪽 자식 노드로 갱신
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // largest가 현재 노드(i)가 아니라면 자식 노드 중에 큰 값이 있으므로 교환
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            // 교환된 노드를 중심으로 다시 최대 힙 구성
            heapify(arr, n, largest);
        }
    }
}

위 코드는 최대 힙을 이용한 힙 정렬이다. 배열을 최대 힙으로 구성한 후, 루트 노드를 배열의 가장 뒤쪽으로 이동시키고, 힙의 크기를 줄여 다시 최대 힙으로 구성하는 과정을 반복하여, 정렬된 값을 얻게 된다. 최대 힙을 이용한 힙 정렬의 구현 방법은 다음과 같다.

  1. 주어진 배열을 최대 힙 구조로 변환한다. 이를 위해, 먼저 주어진 배열을 이진 힙 구조로 변환하고, 이진 힙의 루트 노드에서부터 시작하여 부모 노드보다 자식 노드의 값이 더 작을 경우, 부모 노드와 자식 노드를 교환하는 방식으로 최대 힙 구조를 만든다.

  2. 최대 힙에서 루트 노드(최대 값)를 제거하여 배열의 가장 뒤쪽으로 이동시킨다. 이 과정에서는 배열의 마지막 위치부터 하나씩 채워나가면서 정렬된 값을 얻을 수 있다.

  3. 힙의 크기를 줄이고, 다시 최대 힙 구조를 만든다. 이를 위해, 제거된 루트 노드 위치에 있던 값을 힙의 맨 끝 노드로 이동시키고, 이 노드부터 시작하여 부모 노드보다 자식 노드의 값이 더 작을 경우, 부모 노드와 자식 노드를 교환하는 방식으로 최대 힙 구조를 만든다.

  4. 2번과 3번 과정을 반복한다. 힙의 크기가 1이 될 때까지 반복하여 정렬을 완료한다.

6. 기수 정렬

a. 기수정렬(Radix sort)은 비교 연산 없이 데이터를 정렬하는 알고리즘
b. 시간복잡도 : O(nk)

기수 정렬은 정렬 대상 데이터를 자리수나 문자 등의 특정한 기준으로 나누어 각각의 자리수를 비교하며 정렬한다.

예를 들어, 100 이하의 자연수로 이루어진 데이터가 있을 때, 기수정렬은 먼저 일의 자리수부터 정렬하고, 이어서 십의 자리수, 백의 자리수 등의 순서로 정렬한다. 각 자리수별로 정렬된 데이터를 다시 합쳐서 전체적으로 정렬된 데이터를 얻을 수 있다.

하지만 데이터의 크기가 매우 크거나 자릿수가 많은 경우에는 다른 정렬 알고리즘보다 느리게 동작할 수 있다. 또한, 정렬 대상 데이터가 숫자가 아닌 문자열이나 객체 등일 때는 기수정렬을 적용하기 어려울 수 있다.

위 그림의 과정에 대한 설명이다.

  1. 일의 자리수를 기준으로 정렬
  • 954, 354, 009, 411

    각 숫자의 일의 자리수를 보면 4, 4, 9, 1 입니다. 이를 기준으로 정렬하면 009, 411, 954, 354가 됩니다.

  1. 십의 자리수를 기준으로 정렬
  • 009, 411, 954, 354

    각 숫자의 십의 자리수를 보면 0, 1, 5, 5가 됩니다. 이를 기준으로 정렬하면 009, 411, 354, 954가 됩니다.

  1. 백의 자리수를 기준으로 정렬
  • 009, 411, 354, 954

    모든 숫자의 백의 자리수가 0이므로 추가적인 정렬 작업이 필요하지 않습니다.

  1. 최종 결과
  • 009, 411, 354, 954

이렇게 기수정렬을 사용하여 데이터를 정렬할 수 있습니다. 위의 예시에서는 숫자의 최대 자릿수가 3이므로 세 번의 정렬 작업을 거쳤습니다. 데이터의 개수는 4이므로 시간 복잡도는 O(nk) = O(4*3) = O(12)가 됩니다.


7. 계수 정렬

a. 정계수정렬(Counting sort)은 비교 기반 정렬이 아닌, 선형 시간에 작동하는 정수 정렬 알고리즘
b. 각 데이터의 개수를 카운팅하는 작업을 통해 정렬을 수행한다.
c. 주어진 데이터를 순회하면서 각 데이터의 개수를 세는 작업을 거쳐, 데이터의 범위만큼 배열을 생성한다. 이후, 배열을 순회하면서 각 데이터의 개수만큼 해당 데이터를 출력하면 정렬이 완료된다.

배열의 최대값만큼의 카운팅 테이블(배열)을 생성하고, 배열값에 해당되는 인덱스에 대입하여 카운팅한다. 예를 들면, 위의 그림에서 99가 가장 큰 값이므로 카운팅 테이블의 길이는 0~99이다. 그리고 10은 총 2번 나왔으므로, 카운팅 테이블의 인덱스 10번에 2라는 카운팅 숫자가 대입된다.

대입이 끝나면 카운팅된 숫자만큼 해당숫자를 작은 숫자부터 다시 아웃풋한다.
10은 카운팅 숫자가 2개이니 10 10 그 다음 나온 숫자는 17 1개 이므로 10 10 17 ...
이런식으로 나열하면 끝이 난다.


8. 셸 정렬

a. 삽입 정렬의 약점을 보완한 정렬 방식
b. 삽입 정렬의 약점

  • 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서 앞 데이터와 모두 비교하며 교환 필요

c. 이전의 모든 데이터와 비교하지 않고 일정 간격을 두고 비교
d. 시간복잡도 : O(N²)

셸 정렬은 먼저 정렬할 데이터를 일정한 간격으로 나누어 부분적으로 정렬한 후, 간격을 점점 줄여가며 전체 데이터를 정렬한다. 간격을 줄여가는 과정에서는 삽입 정렬을 사용하여 정렬한다.

간격을 나누는 방법은 여러 가지가 있지만, 대표적인 방법인 '하이네켈 간격(Heinrich Shell)'은 아래와 같이 계산된다.

간격 = N / 2, N / 4, N / 8, ... (N은 데이터의 개수)
간격이 작아질수록 삽입 정렬의 효과가 커지므로, 마지막에는 간격을 1로 설정하여 전체 데이터를 한 번 더 정렬한다.

profile
I'm still hungry.

0개의 댓글