Rena Makise

Rena Makise

Thrilling Dream

Sort

Sorting Algorithm

  1. 선택 정렬 (Selection Sort)

    • 선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.

    • 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(Min-Selection Sort)와 최대 선택 정렬(Max-Selection Sort)로 구분할 수 있다.

    • 최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것이다.

    • 기본 로직은 다음과 같다.

      • 정렬되지 않은 인덱스의 맨 앞에서부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

        (정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)

      • 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꾸어 준다.

      • 다음 인덱스에서 위 과정을 반복해준다.

    • 이 정렬 알고리즘은 n-1개, n-2개, … , 1개씩 비교를 반복한다.

    • 배열이 어떻게 되어있던지 간에 전체 비교를 진행하므로 시간복잡도는 $O(n^2)$이다.

    • 공간복잡도는 단 하나의 배열에서만 진행하므로 $O(n)$이다.

      public class Selection {
    public void sort(int[] data) {
        int size = data.length;
        int min;
        int temp;
             
        for (int i = 0; i < size - 1; ++i) {
            min = i;
            for (int j = i + 1; j < size; ++j) {
                if (data[min] > data[j]) {
                    min = j;
                }
            }
            temp = data[i];
            data[i] = data[min];
            data[min] = temp;
        }
    }
    public static void main(String[] args) {
        Selection selection = new Selection();
        int data[] = {66, 10, 1, 99, 5};
        selection.sort(data);
    }
}

  2. 삽입 정렬(Insertion Sort)

    • 삽입 정렬은 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아 그 위치에 삽입하는 배열 알고리즘이다.

    • 기본 로직은 다음과 같다.

      • 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해두고, 비교 인덱스를 (현재 인덱스 - 1)로 잡는다.
      • 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
      • 삽입 변수의 값이 더 작으면 현재 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.
      • 만약 삽입 변수가 더 크면, (비교 인덱스 + 1)에 삽입 변수를 저장한다.

    • 이 정렬 알고리즘 또한 최악의 경우(역으로 정렬되어있을 경우)엔 n - 1개, n - 2개, … , 1개씩 비교를 반복하여 시간복잡도는 $O(n^2)$이지만 이미 정렬되어 있는 경우에는 한 번씩 밖에 비교를 하지 않아 시간 복잡도는 $O(n)$이다.

    • 하지만 빅오는 최악의 경우를 기준으로 평가하므로 삽입정렬의 시간복잡도는 $O(n^2)$이다.

    • 공간 복잡도는 단 하나의 배열에서만 진행하므로 $O(n)$이다.

      public class Insertion {
    public void sort(int[] data) {
        int size = A.length;
        int temp = 0;
        int j = 0;
        for (int i = 1; i < size; ++i) {
            temp = A[i];
            for (j = i - 1; j >= 0 && temp < A[j]; --j) {
                A[j + 1] = A[j];
            }
            A[j + 1] = temp;
        }
    }
    public static void main(String[] args) {
        Insertion insertion = new Insertion();
        int data[] = {66, 10, 1, 99, 5};
        insertion.sort(data);
    }
}

  3. 버블 정렬(Bubble Sort)

    • 버블 정렬은 매번 연속된 두 개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법니다.

    • 오름차순으로 정렬하고자 할 경우 비교시마다 큰 값이 뒤로 이동하여 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.

    • 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복해 주면 된다.

    • 기본 로직은 다음과 같다.

      • 버블 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전의 인덱스 값을 비교한다.
      • 만약 이전 인데긋가 더 크면 현재 인덱스와 바꿔준다.
      • 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열 값을 비교한다.
      • 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

    • 이 정렬 알고리즘은 1부터 비교를 시작하여 n - 1개, n - 2개, …, 1개씩 비교를 반복하며, 선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간 복잡도는 $O(n^2)$이다.

    • 공간 복잡도도 이 또한 단 하나의 배열에서만 진행하므로 $O(n)$이다.

      public class Bubble {
    public void sort(int[] data) {
        int temp = 0;
        for (int i = data.length - 1; i >= 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (data[j] > data[j + 1]) {
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        Bubble bubble = new Bubble();
        int data[] = {66, 10, 1, 99, 5};
        bubble.sort(data);
    }
}

  4. 합병 정렬(Merge Sort)

    • 합병 정렬은 분할 정복(Divide and conquer) 방식으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다.

    • 입력으로 하나의 배열을 받고, 연산 중에 두 개의 배열로 계속 쪼개 나간 뒤, 합치면서 정렬해 최후에는 하나의 배열을 출력한다.

    • 합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

    • 오름차순의 경우 배열 A, 배열 B를 비교하여 A에 있는 값이 더 작다면 새 배열에 저장해주고, A인덱스를 증가시킨 후 A, B의 반복을 진행한다.

    • 이는 A나 B중 하나가 모든 배열 값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다.

    • 분할 과정의 기본 로직은 다음과 같다.

      • 현재 배열을 반으로 쪼갠다. 배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.
      • 이를 쪼갠 배열의 크기가 0이거나 1일 때까지 반복한다.

    • 합병 과정의 기본 로직은 다음과 같다.

      • 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i, j로 가정하자.

      • i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 인덱스를 저장한다.

      • A[i]와 B[j]를 비교한다. 오름차순의 경우 이 중에 작은 값을 새 배열 C에 저장한다.

        만약 A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.

      • 이를 i나 j 둘 중 하나가 각자 배열의 끝에 도달할 때까지 반복한다.

      • 끝까지 저장을 못한 배열의 값을 순서대로 전부 다 C에 저장한다.

      • C 배열을 원래의 배열에 저장해준다.

    • 이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.

    • 합병 과정은 두 배열 A, B를 정렬하기 때문에 A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우 $O(N1 + N2)$와 같다. 배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 떄문에 전체 배열의 길이가 N이라고 할 경우 결국 $O(N)$이라고 할 수 있다.

    • 분할 과정은 $logN$만큼 일어나는데 그 이유는 간단하다. 크기가 N인 배열을 분할하면, 한번 분할하면 N/2, N/2로 2개, 그 다음 분할하면 N/4, N/4, N/4, N/4로 4개… 즉 분할 과정은 매번 반씩 감소하므로 $logN$만큼 반복해야 크기가 1인 배열로 분할할 수 있다.

    • 각 분할벼로 합병을 진행하므로, 합병 정렬의 시간 복잡도는 $O(NlogN)$이다.

    • 사용하는 공간은 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다.

      public class MergeSort {
    public void sort(int[] data, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            sort(data, low, mid);
            sort(data, mid + 1, high);
            merge(data, low, mid, high);
        }
    }
    public void merge(int[] data, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int k = low;
        int temp[] = new int[data.length];
        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 idx = low; idx <= high; ++idx) {
            arr[idx] = temp[idx];
        }
    }
    public static void main(String[] args) {
        MergeSort mergesort = new MergeSort();
        int data[] = {66, 10, 1, 99, 5};
        mergesort.sort(data, 0, data.length - 1);
    }
}

  5. 퀵 정렬(Quick Sort)

    • 퀵 정렬 또한 분할 정복(Divide and conquer)을 이용하여 정렬을 수행하는 알고리즘이다.

    • pivot point라고 기준이 되는 값을 하나 설정하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다.

    • 이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된 것이다.

    • 기본 로직은 다음과 같다.

      • pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열의 값 중 중간 값이나 랜덤 값으로 정한다.
      • 분할을 진행하기 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장한 left 변수, 가장 오른쪽 배열의 인덱스를 저장한 right변수를 생성한다.
      • right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며 비교한 배열 값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다. pivot point보다 작은 배열 값을 찾으면 반복을 중지한다.
      • 그 다음 left부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며 비교한 배열 값이 pivot point보다 작으면 left를 하나 증가시키고 비교를 반복한다. pivot point보다 큰 배열 값을 찾으면 반복을 중지한다.
      • left인덱스의 값과 right인덱스의 값을 바꿔준다.
      • 3, 4, 5과정을 left < right가 만족할 때까지 반복한다.
      • 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.
      • 맨 왼쪽부터 left - 1까지, left + 1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.

    • 퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이다.

    • 각 정렬은 배열의 크기 N만큼 비교하며, 이를 총 분할 깊이인 $logN$만큼 진행하므로 총 비교횟수는 $NlogN$, 즉 시간 복잡도는 $O(NlogN)$이다.

    • 다만 퀵 정렬에는 최악의 경우가 존재하는데, 이는 배열이 이미 정렬되어 있는 경우이다. 이 경우 분할이 N만큼 일어나므로 시간 복잡도는 $O(N^2)$이다. 이를 방지하기 위해 pivot point를 중간 값이나 랜덤 값으로 정하는 방법을 쓰기도 한다.

      public class Quick {
    public void sort(int[] data, int l, int r) {
        int left = l;
        int right = r;
        int pivot = data[(l + r) / 2];
             
        do {
            while(data[left] < pivot) left++;
            while(data[right] > pivot) right++;
            if (left <= right) {
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        } while (left <= right);
        if (l < right) sort(data, l, right);
        if (r > left) sort(data, left, r);
    }
    public static void main(String[] args) {
        int data[] = {66, 10, 1, 34, 5, -10};
        Quick quick = new Quick();
        quick.sort(data, 0, data.length - 1);
    }
}

  6. 힙 정렬(Heap Sort)

    • 힙 정렬은 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식이다
    • 시간복잡도는 $O(NlogN)$을 가진다.
    • 기본 로직은 다음과 같다.
      • 최대 힙을 구성한다
      • 현재 힙의 루트는 가장 큰 값이 존재하게 된다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄인다.
      • 힙의 사이즈가 1보다 크면 위 과정을 반복한다.
    • 이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬을 할 수 있게 된다.

    public class Heap {
    public void sort(int[] data) {
        int size = data.length;
           
        for (int i = size / 2 - 1; i >= 0; --i) {
            heapify(data, size, i);
        }
           
        for (int i = size - 1; i > 0; --i) {
            swap(array, 0, i);
            heapify(data, i, 0);
        }
    }
       
    public void heapify(int[] data, int size, int i) {
        int p = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;
           
        if (left < size && data[p] < data[left]) {
            p = left;
        }
        if (right < n && data[p] < data[right]) {
            p = right;
        }
           
        if (i != p) {
            swap(data, p, i);
            heapify(data, size, p);
        }
    }
       
    public void swap(int[] data, int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }
       
    public static void main(String[] args) {
        int data[] = {66, 10, 1, 34, 5, -10};
        Heap heap = new Heap();
        heap.sort(data);
    }
}

정렬의 종류

안정 정렬

  • 동일한 값에 대해 기존의순서가 유지되는 정렬방식이다.
  • 버블정렬, 삽입정렬, 합병정렬이 이에 속한다

불안정 정렬

  • 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식이다
  • 선택 정렬, 퀵 소트, 힙 정렬이 이에 속한다.