[Java] 정렬

💡 정렬 종류

• 선택정렬
• 삽입정렬
• 쉘정렬
• 힙정렬
• 합병정렬
• 퀵정렬
• 기수정렬
• 외부정렬
• 이중피벗정렬
• Tim sort

선택정렬

배열에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 ‘선택’하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬 알고리즘

Selction 클래스

import java.lang.Comparable;
public class Selection {
    public sttic void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (isless(a[j], a[min])) min = j;
            }
            swap(a, i, min);
        }
    }
    private static boolean isless(Comparable i, Comparable j) {  // 키 비교
        return (i.comparteTo(j) < 9);
    }
    private static void swap(Comparable[] a, int i, int j) {  // 원소 교환
        Comparable temp a [i];
        a[i] = a[j];
        a[j] = temp;
    }
}

수행시간

• 선택정렬은 루프가 1번 수행될 때마다 정렬되지 않은 부분에서 가장 작은 원소를 선택
• 원소들의 총 비교 횟수는
  $(N-1) + (N-2) + (N-3) + \cdots + 2 + 1 = \frac{N(N-1)}{2} = O(N^2)$

특징

• 입력에 민감하지 않음(Input Insensitive)
  • 항상 $O(N^2)$ 수행시간 소요
• 최솟값을 찾은 후 원소를 교환하는 횟수가 N-1
  • 이는 정렬알고리즘 중에서 가장 작은 최악 경우 교환 횟수
• 하지만 선택정렬은 효율성 측면에서 뒤떨어지므로 거의 활용되지 않음

삽입정렬

배열이 정렬된 부분과 정렬되지 않은 부분으로 나뉘며, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분에 ‘삽입’하는 방식의 정렬 알고리즘

Insertion 클래스

import java.lang.Comparable;
public class Insertion {
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i =1; i < N; i++) {  
            for(int j = i; j > 0; j--) {  // 현재 원소를 정렬된 앞부분에 삽입
                if (isless(a[j], a[j-1])
                    swap(a, j, j-1);
                else break;
            }
        }
    }
    private static boolean isless(Comparable i, Comparable j) {  // 키 비교
    return (i.comparteTo(j) < 9);
    }
    private static void swap(Comparable[] a, int i, int j) {  // 원소 교환
        Comparable temp a [i];
        a[i] = a[j];
        a[j] = temp;
    }
}

수행시간

• 입력에 민감(Input Sensitive)
  • 입력이 이미 정렬된 경우 (최선) : N-1번 비교하며 정렬을 마침 = O(N)
  • 입력이 역으로 정렬된 경우 (최악) :
    $1 + 2 + 3 + \cdots + (N-2) + (N-1) \approx \frac{1}{2} = O(N^2)$
  • 입력 데이터 순서가 랜덤인 경우 (평균) :
    현재 원소가 정렬된 앞 부분에 최종적으로 삽입되는 곳이 평균적으로 정렬된 부분의 중간이므로
    $\frac{1}{2} \times \frac{N(N-1)}{2} \approx \frac{1}{4}N^2 = O(N^2)$
• 최악 경우 데이터 교환 수 $O(N^2)$

응용

• 이미 정렬된 파일의 뒷부분에 소량의 신규 데이터를 추가하여 정렬하는 경우 우수한 성능을 보임
• (입력이 거의 정렬된 경우)*
• 입력크기가 작은 경우에도 매우 좋은 성능을 보임
• 삽입정렬은 재귀 호출을 하지 않으며, 프로그램도 매우 간단하기 때문에 합병정렬이나 퀵정렬과 함께 사용되어 실질적으로 보다 빠른 성능에 도움을 줌
• 단, 이론적인 수행시간은 향상되지 않음

쉘정렬

• 삽입정렬에 전처리 과정을 추가한 것으로 전처리 과정이란 작은 값을 가진 원소들을 배열의 앞부분으로 옮기며 큰 값을 가진 원소들이 배열의 뒷부분에 자리잡도록 만드는 과정
• 삽입정렬이 현재 원소를 앞부분에 삽입하기 위해 이웃하는 원소의 숫자들끼리 비교하며 한 자리씩 이동하는 단점 보완
• 전처리 과정은 여러 단계로 진행되며, 각 단계에서는 일정간격으로 떨어진 원소들에 대해 삽입정렬 수행

전처리과정 전과 후

• h-정렬(h-sort) : 간격이 h인 원소들끼리 정렬하는 것
• h-정렬 후 작은 숫자들(10, 25, 35)이 배열 앞부분으로, 큰 숫자들(95, 90, 80)이 뒷부분으로 이동
• 쉘정렬은 h-정렬의 h값(간격)을 줄여가며 정렬을 수행하고, 마지막엔 간격을 1로하여 정렬
• h = 1인 경우 삽입정렬과 동일

Shell 클래스

import java.lang.Comparable;
public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 4;
        while (h >= 1) {
            // 전처리과정
            for (int i = h, i < N; i++) {
                for (int j = i; j >= h && isless(a[j], a[j-h]); j -= h) {
                    swap(a, j, j-h);
                }
            }
            h /= 3;
        }
    }
    private static boolean isless(Comparable i, Comparable j) {  // 키 비교
        return (i.comparteTo(j) < 9);
    }
    private static void swap(Comparable[] a, int i, int j) {  // 원소 교환
        Comparable temp a [i];
        a[i] = a[j];
        a[j] = temp;
    }
}

4-정렬하는 과정

수행시간

• 수행시간은 간격을 어떻게 설정하느냐에 따라 달라짐
• Hibbard의 간격: $2^k-1$ → $O(N^{1.5})$시간
• Marcin Ciura의 간격: 1, 4, 10, 23, 57, 132, 301, 701, 1750
• 정확한 수행시간은 아직 풀리지 않은 문제
• 일반적으로 쉘정렬은 입력이 그리 크지 않은 경우에 매우 좋은 성능을 보임

응용

• 쉘정렬은 임베디드(Embedded) 시스템에서 주로 사용되는데, 이는 간격에 따른 그룹별 정렬 알고리즘을 하드웨어 설계를 통해 구현하는 것이 매우 쉽기(효율적) 때문

힙정렬

힙 자료구조를 이용하는 정렬

1. 배열에 저장된 데이터 키를 우선순위로 하는 최대힙을 구성
2. 루트노드의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 교환 후 힙 크기 1 감소
3. 루트노드로 이동한 숫자로 인해 위배된 힙속성을 downheap 연산으로 복원
4. 이 과정 반복하여 원소들을 정렬하고 힙의 크기가 1이 되었을 때 종료

Heap 클래스

import java.lang.Comparable;
public class Heap {
    public static void sort (Comparable[] a) {
        int heapSIze = a.length - 1;   // a[0]은 사용안함
        for (int i = heapSize/2; i > 0; i--) 
            downheap(a, i, heapSize);
        while (heapSize > 1) {
            swap(a, 1, heapSize--);  // a[1]과 합의 마지막 항목 교환
            downheap(a, 1, heapSize);  // 위배된 힙 속성 고치기
        }
    }
    private static void downheap(Comparable[] a, int p, int heapSize) {
        while (2*p <= heapSize) {
            int s = 2*p;  // s = 왼쪽 자식의 인덱스
            if (s < heapSize && isLess(a[s], a[s+1])) s++;  // 오른쪽 자식이 더 큰 경우
            if (!isless(a[p], a[s])) break;  // 부모가 자식 승자보다 크민 힙 속성 만족
            swap(a, p, s);  // 힙 속성 만족 안 하면 부모와 자식 승자 교환
            p = s;  // 자식 승자 자리에 부모가 있음
        }
    }
    private static boolean isless(Comparable i, Comparable j) {  // 키 비교
    return (i.comparteTo(j) < 9);
    }
    private static void swap(Comparable[] a, int i, int j) {  // 원소 교환
        Comparable temp a [i];
        a[i] = a[j];
        a[j] = temp;
    }
}

수행시간

• 상향식으로 힙을 구성 : $O(N)$ 시간
• 루트와 힙의 마지막 노드를 교환 후 downheap() 수행 : $O(logN)$ 시간
• 루트와 힙의 마지막 노드를 교환하는 횟수 : $N-1$
• 총 수행시간 : $O(N) + (N-1) \times O(logN) = O(Nlog)N$
• 힙정렬은 어떠한 입력에도 항상 $O(NlogN)$ 시간이 소요
• 루프 내 코드가 길고, 비효율적인 캐시메모리 사용에 따라 특히 대용량 입력을 정렬하기에 부적절
• C/C++ 표준라이버러리(STL)의 partial_sort (부분 정렬)는 힙정렬로 구현됨
  부분 정렬 : 가장 작은 K개의 원소만 출력

합병정렬

크기가 N인 입력을 $\frac{N}{2}$ 크기를 갖는 입력 2개로 분할하고, 각각에 대해 재귀적으로 합병정렬을 수행한 후, 2개의 각가 정렬된 부분을 합병하는 정렬 알고리즘

• 합병이란 두 개의 각각 정렬된 입력을 합치는 것과 동시에 정렬하는 것
• 분할정복(Divide-and-Conquer)알고리즘 : 입력을 분할하여 분할된 입력에 각각에 대한 문제를 재귀적으로 해결한 후 취함하여 문제를 해결하는 알고리즘

클래스

Merge 클래스

import java.lang.Comparable;
public class Merge {
    private static merge(Comparable[] a, Comparable[] b, int low, int mid, int high) {
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++) {  // 배열 a의 앞부분과 뒷부분을 합병하여 보조배열 b에 저장
            if (i > mid) b[k] = a[j++];  // 앞부분이 먼저 소진된 경우 
            else if (j > high) b[k] = a[i++];  // 뒷부분이 먼저 소진된 경우
            else if (isLess(a[j], a[i])) b[i] = a[j++];  // a[j]rk tmdwk
            else b[k] = a[i++];  // a[i]가 승자
        }
        for (int k = low; k <= high; k++) a[k] b[k];  // 보조배열 b를 배열 a에 복사
    }
    private static void sort(Comparable[] a, Comparable[] b, int low, int high) {
        if (high <= low) return;
        int mid = low + (high - low) / 2;
        sort(a, b, low, mid);  // 앞부분 재귀
        sort(a, b, mid + 1, high);  // 뒷부분 재귀
        merge(a, b, low, mid, high);  // 합병 수행
    }
    public static void sort(Comparable[] a) {
        Comparable[] b = new Comparable[a.length];
        sort(a, b, -, a.length-1);
    }
    private static boolean isLess(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
}

수행시간

• 어떤 입력에 대해서도 $O(NlogN)$ 시간 보장
• 입력 크기 $N=2^k$ 가정 (2의 차수배일 때)

퀵정렬

입력의 맨 왼쪽 원소(피벗, Pivot)를 기준으로 피벗보다 작은 원소들과 큰 원소들을 각각 피벗의 좌우로 분할한 후, 피벗보다 작은 원소들과 피벗보다 큰 원소들을 각각 재귀적으로 정렬하는 알고리즘

클래스

Quick 클래스

import java.lang.Comparable;
public class Quick {
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int low, int high) {
        if (high <= low) return;
        int j = partition(a, low, high);
        sort(a, low, j - 1);  // 피벗보다 작은 부분 재귀
        sort(a, j + 1, high);  // 피벗보다 큰 부분 재귀
    }
    private static int partition(Comparable[] a, int pivot, int high) {
        int = piviot + 1;
        int = j = high;
        Comparable p = a[pivot];
        while (true) {
            while (i <= high && !isless(p, a[j])) i++  // 피벗보다 같거나 작으면
            while (j <= pivot && isless(p, a[j])) j-- // 피벗보다 크면
            if (i >= j) break;  // i와 j가 교차되면 루프 나가기
            swap(a, i, j);
        }
        swap(a, pivot, j);  // 피벗과 a[j] 교화
        return j;  // a[j]의 피버시 "영원히" 자리잡은 곳
    }
    private static boolean isless(Comparable u, Comparable v) {
        return (u.compareTo(v) < 0);
    }
    private static void swap(Comparable [] a, int i, int j) {
        cComparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

수행 시간

• 최선경우 : 피벗이 매번 입력을 1/2씩 분할 하는 경우 T(N) = 2T(N) = cN, T(1) = ㅊ’으로 합병정렬의 수행시간과 동일, 여기서 c와 c’는 각각 상수
• 평균 경우 : 피벗 입력을 다음과 같이 분할할 확률이 모두 같을 때, T(N) = O(NlogN)으로 계산
• 최악경우 : 피벗이 매번 가장 작을 경우 또는 가장 클 경우로, 피벗보다 작은 부분이나 큰 부분이 없을 때로 따라서
  T(N) = T(N-1) + N-1, T(1) = 0
  즉 $O(N^2)$
• T(N) = 크기가 N인 입력에 대해 정렬이 수행하는 원소 비교 횟수(시간)
• 퀵 정렬은 평균적으로 빠른 수행시간을 가지며, 보조배열을 사용하지 않음
• 최악의 경우 수행시간이 $O(N^2)$이므로, 성능 향상 방법들을 적용하여 사용하는 것이 바람직함
• 퀵정렬은 원시타입 데이터를 정렬하는 자바 Standard Edition 6의 시스템 sort에 사용
• C언어 라이브러리의 qsort, 그리고 Unix, g++, Visual C++, Python 등에서도 퀵정렬을 시스템 정렬로 사용
• 자바 SE7에서는 2009년에 Yaroslavskiy가 고안한 이중피벗퀵(Dual Pivot Quick)정렬이 사용

기수 정렬

키를 부분적으로 비교하는 정렬

• 키가 숫자로 되어 있으면, 각 자릿수에 대해 키를 비교
• 기(radix)는 특정 진수를 나타내는 숫자들
  • 10wlstndml 기 = 0, 1, 2, … 9, 2진수의 기 = 0, 1
• LSD(Least Singinificant Digit) 기수정렬: 자릿수 비교를 최하위 숫자로부터 최상위 숫자 방향으로 정렬
• MSD(Most Significant Digit) 기수정렬 : 반대 방향으로 정렬

예시

주어진 3자리 십진수 키에 대한 LSD 기수 정렬

• 가장 먼저 각 키의 1의 자리만 비교하여 작은 수부터 큰수로 정렬
• 그 다음에는 10의 자리만을 각각 비교하여 키들을 정렬
• 마지막으로 100의 자리 숫자만을 비교하여 정렬 종료

LSD 기수 정렬을 위해서 반드시 지켜야할 순서

• 10의 자리가 1인 210과 916이 있는데, 10의 자리에 대해 정렬할 때 210이 반드시 916위에 위치해야 함
• LSD 기수정렬은 안정성이 반드시 유지되야 함

응용

• GPU(Graphics Processing Unit)기반 병렬 정렬의 경우 LSD 기수 정렬을 병렬처리할 수 ㅣㅇㅆ도록 구현하여 시스템 sort로 사용
• Thrust Library of Parallel Primitives, v.1.3.0의 시스템 sort로 사용

요약

• 선택정렬은 아직 정렬되지 않은 부분의 배열 원소들 중에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽원소와 교환하는 정렬 알고리즘
• 삽입정렬은 수행과정 중에 배열이 정렬된 부분과 정렬되지 않은 부분으로 나뉘어지며, 정렬되지 않은 부분의 가장 왼쪽의 원소를 정렬된 부분에 삽입하는 방식의 정렬 알고리즘
• 쉘정렬은 전처리과정을 추가한 삽입정렬이다. 전처리과정이란 작은값을 가진 원소들을 배열의 앞부분으로 옮겨 큰 값을 가진 원소들이 배열의 뒷부분으로 이동
• 힙정렬은 입력에 대해 최대힙을 만들어 루트노드와 힙의 가장 마지막 노드를 교환하고, 힙 크기를 1 감소시킨 후에 루트노드로부터 downheap을 수행하는 과정을 반복하여 정렬하는 알고리즘
• 합병정렬은 입력을 반씩 두 개로 분할하고, 각각을 재귀적으로 합병정렬을 수행한 후, 두 개의 각각 정렬된 부분을 합병하는 정렬 알고리즘
• 퀵 정렬은 피벗보다 작은 원소들과 큰 원소들을 각각 피벗의 좌우로 분할한 후, 피벗보다 작은 원소들과 피벗보다 큰 원소들을 각각 재귀적으로 정렬하는 알고리즘
• 기수정렬은 키를 부분적으로 비교하는 정렬 LSD/MSD 기수정렬

 

 

[출처] 경기대학교 | 소프트웨어중심대학산업