[algorithm] 정렬 4. 정리 및 응용

목차

• 어떤 정렬 알고리즘을 사용해야 하는가
• 환원 : 정렬 알고리즘 응용하기
• 정렬알고리즘 사용 사례

---

어떤 정렬 알고리즘을 사용해야 하는가

 

 

명제 : 퀵-정렬은 가장 빠른 범용 정렬 알고리즘이다.

위 가설은 퀵-정렬이 개발된 이래 수십 년간 수많은 컴퓨팅 시스템에서 수많은 방식으로 구현되어 왔다. 일반적으로 퀵 정렬이 빠른 이유는 내부 루프의 명령어 수가 적기 때문이다. 

 

결론 : 대부분의 실제 상황에서 퀵-정렬을 선택하는 것이 안전하다. 

그 선택이 올바른지는 예외 상황들을 토대로 살펴봐야 한다. 예를 들어 안정정렬이 중요하고 공간이 충분하다면 병합 정렬이 최선일 것이다.

 

기본형 데이터 타입의 정렬

성능에 매우 민감하거나 숫자의 정렬에만 집중한다면 int와 같은 기본형을 사용하는 것이 좋다. int는 후술 할 포인터 정렬이 아닌 숫자 자체를 배열에서 교환해 나가며 정렬한다. 따라서 Comparable 구현체와 같은 것이 필요 없다. 포인터 정렬의 경우 기본형 정렬과 달리 참조하는 비용 + 참조 변수를 정렬하는 비용이 추가로 발생한다.

 

java.util.Arrays.sort()

 자바에서 자체적으로 제공하는 정렬 메서드이다. 인수 타입별로 오버로딩되어 구현되어 있다. 기본형 타입, Comparable 구현체, Comparator 구현체를 인수로 받을 수 있다.

 

Java의 java.lang.Comparable 구현

 Java는 Comparable 구현체라면 정렬 가능하게 한다. Comparable 구현체는 compareTo()를 구현해야 한다. 기본 라이브러리 String, Integer, File, URL 등은 이미 Comparable를 구현하고 있다.  그러나 대다수 애플리케이션은 개발자가 직접 정의한 데이터 구조 (클래스)를 사용한다. 이 때는 개발자가 직접 Comparable을 구현해야 한다. 

 

응용 상황 : 전자상 거래 (eCommerce) 트랜잭션 처리

// 트랜잭션의 거래 날짜를 기준으로 정렬
public int compareTo(Transaction tr){
    return this.when.compareTo(tr.when); // when은 Date 타입
}

 

개발자가 작성한 클래스 Transaction 이 위처럼 Comparable을 구현했다면, 이제 Transaction 데이터 타입은 정렬이 가능해진다.

 

포인터 정렬

 고전적인 알고리즘 서적에서는 Java의 정렬을 포인터 정렬로 분류한다. 포인터 정렬이란 데이터의 참조변수를 옮길 뿐, 실제 데이터는 이동 (정렬)시키지 않는 정렬 방법이다. Java의 경우 암묵적으로 숫자 데이터 타입 외에는 포인터 정렬로 수행한다. C/C++ 같은 언어에서는 정렬 대상이 포인터인지, 데이터인지 명시적으로 지정할 수 있다.

 참조를 사용하면 데이터를 직접 교환하는 비용을 회피할 수 있는 장점이 있다. 항목이 많을수록 키의 크기가 작을수록 포인터 정렬의 효율은 증가한다. 

 

키 값은 변하지 않도록 하자

 만일 정렬된 객체 배열의 키 값을 클라이언트가 맘대로 바꿀 수 있다면 정렬 상태가 깨질 수 있다. 따라서 키 값은 불변 속성을 사용하여 변경되지 않도록 하는 것이 바람직하다. 예를 들면 Java의 String, Integer, Double, File과 같은 데이터 타입들은 모두 불변성을 지원하고 있다. 

 

정렬 기준을 자유롭게

같은 객체여도, 상황에 따라 서로 다른 정렬 기준으로 정렬해야 할 수 있다. Java는 Comparator의 구현체라면 하나의 클래스에서 여러 종류의 정렬 기준을 정의 가능하게 한다. 

 

public class Transaction {
    // ...

    private final Stirng who;
    private final Date when;
    private final double amount;

    public static class AmountOrder implements Comparator<Transaction> {
        public int compare(Transaction v, Transcation w) {
            return v.amount.compareTo(w.amount);
        }
    }

    public static class WhenOrder implements Comparator<Transaction> {
        public int compare(Transaction v, Transcation w) {
            return v.when.compareTo(w.amount);
        }
    }

    public static void main(String[] args) {
        // 거래 금액으로 정렬
        Insertion.sort(a, new Transaction.AmountOrder());
        // 거래 일시로 정렬
        Insertion.sort(a, new Transaction().WhenOrder());
    }
}

 

안정 정렬

 안정 정렬이란 정렬 후에도 같은 키들의 상대적인 순서를 정렬 이전과 동일하게 정렬하는 것을 말한다. 

• 안정 정렬 : 삽입 정렬, 병합 정렬
• 안정 정렬 아님 : 선택 정렬, 셸 정렬, 퀵 정렬, 힙 정렬

 안정 정렬이 아닌 정렬방법은 트릭을 추가해 안정정렬로 만들 수 있지만 실제 구현은 쉽지 않다. 따라서 안정성이 필요하다면 안정정렬을 지원하는 삽입 정렬, 병합 정렬을 이용하자.

---

환원 : 정렬 알고리즘 응용하기

 환원이란 어떤 문제를 위해 개발된 알고리즘을 다른 문제 해결에도 적용 (응용)하는 것을 말한다. 정렬 알고리즘을 사용해서 다음과 같은 문제에서 환원 가능하다. 

• 중복 제거
• 랭킹 (순열)
• 우선순위 큐
• 중앙값, 순위 통계

 

중복 제거

// 배열 a에서 서로 다른 유일한 키 값들을 출력
Quick.sort(a); // 정렬

int cnt = 1; 
for(int i = 1; i < a.length; i++)
    if(a[i].compareTo(a[i-1]) != 0)
        cnt++;

 

랭킹 (순열)

 랭킹 (순열)이란 N개의 정수로 이루어진 배열로, 0부터 N-1에 이르는 숫자가 정확히 한 번씩만 등장하는 것을 말한다. 캔달 타우 거리 (Kendalll tau distance)는 두 순열이 있을 때, 서로 다른 순서로 놓여있는 숫자 쌍의 개수로 정의한다.  예를 들어 순열 {0, 3, 1, 6, 2, 5, 4}와 {1, 0, 3, 6, 4, 2, 5}의 캔달 타우 거리는 4다. (0-1, 3-1, 2-4, 5-4) 

 어떤 순열 A에서 순서가 역전된 쌍의 개수를 구하는 문제를 A와 단위 순열 (각 항목의 숫자가 인덱스인 순열) 간의 캔달 타우 거리 문제로 환원이 가능하다. 

 

우선순위 큐

 크기가 M인 우선순위 큐를 이용하면 다음과 같은 문제들을 해결가능하다. TopM는 가장 큰 M개의 항목을 찾는 클라이언트이다.  어떤 배열이 주어졌을 때, 정렬 후 우선순위 큐로 간주하여 사용하면 해당 배열에서 가장 큰 M개를 찾을 수 있다. Multiway처럼 M개의 정렬된 입력 스트림을 하나의 정렬된 출력 스트림으로 병합할 수도 있다.

 

중앙값, 순위 통계

 어떤 키 집합에서 중앙값을 찾을 때 굳이 전체 배열을 정렬할 필요 없다. 같은 문제로 집합에서 k번쨰로 작은 키를 찾는 문제에서도 전체 배열을 정렬하지 않아도 된다.

// 배열 a에서 k번째로 작원 원소 선택
public static Comparable seelct(Comparable[] a, int k){
    StdRandom.shuffle(a);
    int l = 0, hi = a.length -1;
    
    while (hi > lo){
        int j = partition(a, lo, hi);
        if (j == k) return a[k];    // 찾음
        else if (j > k) hi = j -1;  // j 왼쪽에서 찾음 
        else if (j < k) lo = j + 1; // j 오른쪽에서 찾음 
    }
   
   return a[k];
}

 

 partition()을 실행하면 j 좌측에는 j보다 작거나 같은 항목이 있고, 오른쪽에는 j보다 큰 항목이 위치함을 이용한다.

---

정렬알고리즘 사용 사례

 

상용 컴퓨팅

 세상의 모든 정보, 데이터를 처리할 때는 정렬 알고리즘을 사용한다. 정보들을 대용량 데이터베이스에 조직화 (정렬)하여 저장한다. 정렬하여 저장한 데이터들은 효율적으로 탐색할 수 있다. 정렬 시에는 복수의 키를 기반으로 정렬된 상태를 유지한다. 데이터가 추가될 때는 복수의 키들을 기반으로 정렬시켜 기존의 데이터베이스에 병합시킨다. (RDBMS의 인덱스)

 

정보 탐색

 데이터를 사전에 정렬된 상태로 유지하여 전통적인 이진 탐색 알고리즘으로 특정 항목을 탐색한다. 특정 항목이 얼마나 많은 항목보다 적은가? 특정 항목이 주어진 범위 안에 드는가? 와 같은 문제를 해결할 수 있다.

 

Operation Research (OR) : 스케쥴링 문제

 전통적인 OR 문제로, 처리해야 하는 N개의 작업 목록이 있을 때, 작업 j는 tj초의 처리시간이 소요된다. 모든 작업을 처리하되 고객의 만족도를 최대화하기 위해 평균 완료시간을 최소화하려면 어떻게 해야 할까? 보통 SPTF (Shortest Processing Time First)를 사용한다. 작업에 필요한 시간들을 오름차순으로 나열하여 가장 적게 걸리는 작업부터 처리한다.

 

Operation Research (OR) : 부하 분산 (Load-Balancing)

 M개의 동등한 프로세서와 N개의 작업이 있을 때, 모든 작업을 완료하는데 드는 시간이 가장 짧도록 각 프로세서에 작업을 분산하는 문제다. 괜찮은 방법으로 LPTF (Longest Processing Time First)가 있다. 각 작업 소요시간을 내림차순으로 정렬한 뒤 가용한 프로세들에게 가장 앞 (오래 걸리는 작업) 작업부터 할당하는 방법이다.

 

수치 계산

 과학 연구에서 컴퓨팅 결과의 정밀도는 얼마나 실제 값에 가까운가?라는 뜻으로 매우 중요할 때가 많다. 특히 실수 표현 시 그 근삿값인 부동소수점의 표현이 많이 사용되는데 부동소수점 숫자로 수백만회의 계산이 발생하면 오차가 누적되어 정밀도에 큰 영향을 미칠 수 있다. 이때 어떤 수치 계산 알고리즘에서는 계산 과정의 정확도 확보를 위해 우선순위 큐를 사용한다. 예를 들면 곡선 아래 면적을 구할 때, 전체 구간을 이루는 부분구간을 우선순위큐에 넣은 다음 정밀도 순으로 정밀도가 떨어지는 구간들을 삭제해 나간다.

 

조합 탐색

 AI 분야에서 난해한 문제를 다루는 전통적인 방식이다. 상태 변화에 따른 경우의 수 전개 조건들을 정의한다. 각각의 전개 조건 단위 변화마다 사전에 주어진 우선순위로 평가하여 가장 점수가 높은 상태를 찾아낸다. 시작 상태와 최종 상태 (문제의 해답을 찾은 상태)도 같이 정의한다. 

 예를 들어 우선순위 큐에 시작 상태를 집어넣은 후 목적 상태에 도달할 때까지 가장 높은 평가 값의 상태를 꺼내어 한 개의 조건 변화로 도달 가능한 다른 상태들을 모두 큐에 집어넣는다. 이 과정을 목적 상태에 도달할 때까지 반복하면 된다. 

 

프림 (Prim) 알고리즘과 데이크스트라 (Diikstra) 알고리즘

 그래프 순회 작업에 기반한 알고리즘이다. 그래프  순회는 간선을 따라 항목을 찾아가는 동작 자체를 말한다. 우선순위 큐는 그래프 순회를 구조화하고 알고리즘 효율을 높이는데 기반이 된다.

 

Huffman 알고리즘

 전통적인 데이터 압축 알고리즘이다. 정숫값 가중치를 가진 항목 집합에서 가중치가 작은 두 개를 합쳐 하나의 항목을 만드는데 우선순위큐를 사용한다.

 

문자열 처리 알고리즘

 문자열 처리는 보통 정렬에 기반하는 경우가 많다. 가장 긴 반복 부분 문자열 찾기 알고리즘 (Longest Repeated Substinrg)은 접미사 기준으로 정렬된 문자열을 기반으로 동작한다.