알고리즘의 작동 원리
Chapter 3 Sorting Algorithms

3장: 정렬 알고리즘

정렬은 일련의 객체를 논리적인 순서로 재배열하는 과정입니다. 예를 들어, 신용카드 명세서는 날짜순으로 거래내역을 제공하고, 책장에 책을 저자와 제목 순으로 정렬합니다. 정렬은 컴퓨터 과학의 기본적인 연산이며, 많은 응용 프로그램에서 중요한 역할을 합니다. 이 문제에 대한 다양한 접근법을 담은 고전적인 정렬 알고리즘이 있습니다.

이 장에서는 여러 가지 고전적인 정렬 방법과 우선순위 큐라는 중요한 자료 구조를 살펴봅니다. 먼저 선택 정렬, 삽입 정렬, 셸 정렬과 같은 기본적인 정렬 방법을 다룹니다. 이러한 방법은 많은 응용 프로그램에서 적절하게 사용되지만, 대규모 문제의 경우 병합 정렬과 퀵 정렬과 같은 재귀적 정렬 알고리즘을 사용합니다. 마지막으로 정렬과 다른 응용 프로그램에서의 우선순위 큐 사용에 대해 논의합니다.

기본 정렬

가장 단순한 정렬 알고리즘은 다음과 같은 작업을 수행합니다:

  • 선택 정렬: 가장 작은 항목을 찾아 첫 번째 항목과 교환하고, 그다음 작은 항목을 찾아 두 번째 항목과 교환하는 식으로 진행합니다.
  • 삽입 정렬: 각 항목을 차례대로 가져와 이미 고려된 항목들 사이의 적절한 위치에 삽입합니다(정렬된 상태 유지).

이러한 작업은 사람들이 일반적으로 정렬 작업을 수행하는 방식을 반영하며, 작은 문제 크기에서 효과적입니다. 그러나 이 방법들은 크기가 큰 배열을 정렬하는 데 적합하지 않습니다.

선택 정렬

선택 정렬은 다음과 같이 작동하는 간단한 정렬 알고리즘입니다: 먼저 배열에서 가장 작은 항목을 찾아 첫 번째 항목(자신)과 교환합니다. 그다음 두 번째로 작은 항목을 찾아 두 번째 항목과 교환합니다. 이런 식으로 배열 전체가 정렬될 때까지 계속합니다.

선택 정렬의 내부 루프는 다음과 같습니다:Here is the Korean translation of the provided markdown file, with the code comments translated:

정렬 알고리즘 선택 정렬(Selection Sort)

선택 정렬은 정렬되지 않은 부분 배열 a[i..N-1]에서 최소 요소를 찾는 데 사용됩니다. 최소 요소의 인덱스는 min에 저장됩니다. 그런 다음 a[i]와 a[min]을 교환하여 최소 요소를 최종 위치에 배치합니다. 인덱스 i가 왼쪽에서 오른쪽으로 이동함에 따라, 왼쪽의 요소들은 정렬된 상태이며 다시 건드리지 않습니다.

다음은 Java로 구현한 선택 정렬 코드입니다:

public static void selectionSort(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 (less(a[j], a[min])) min = j;
        }
        // 현재 요소와 최소 요소를 교환합니다
        exch(a, i, min);
    }
}

선택 정렬은 길이 N의 배열을 정렬하는 데 약 ~N^2/2 번의 비교와 N 번의 교환을 사용합니다. 입력 데이터에 관계없이 실행 시간이 일정하므로, 이미 정렬된 배열이나 모든 요소가 같은 배열을 정렬하는 것과 무작위로 정렬된 배열을 정렬하는 것이 비슷한 시간이 걸립니다.

삽입 정렬(Insertion Sort)

삽입 정렬은 또 다른 간단한 정렬 알고리즘으로, 최종 정렬된 배열을 하나씩 만들어 나갑니다. 퀵 정렬, 힙 정렬, 병합 정렬과 같은 더 발전된 알고리즘에 비해 큰 배열에서는 효율적이지 않지만, 다음과 같은 장점이 있습니다:

  • 작은 데이터 집합에 효율적입니다.
  • 선택 정렬보다 실제로 더 효율적입니다.
  • 안정적입니다. 즉, 키가 같은 요소의 상대적 순서를 유지합니다.
  • 제자리 정렬입니다. 즉, 추가 메모리 공간 O(1)만 필요합니다.
  • 온라인 정렬이 가능합니다. 즉, 데이터를 받는 대로 정렬할 수 있습니다.

다음은 Java로 구현한 삽입 정렬 코드입니다:

public static void insertionSort(Comparable[] a) {
    // 배열의 길이를 구합니다
    int N = a.length;
    // 두 번째 요소부터 순회합니다
    for (int i = 1; i < N; i++) {
        // 현재 요소를 적절한 위치에 삽입합니다
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // 현재 요소와 이전 요소를 교환합니다
            exch(a, j, j-1);
        }
    }
}

삽입 정렬의 내부 루프는 더 큰 요소를 한 칸씩 오른쪽으로 이동시켜 현재 요소를 적절한 위치에 삽입합니다.삽입 정렬의 실행 시간은 입력 항목의 초기 순서에 따라 달라집니다. 예를 들어, 배열이 크고 항목이 이미 정렬되어 있거나 (또는 거의 정렬되어 있는) 경우, 항목이 무작위로 정렬되어 있거나 역순으로 정렬되어 있는 경우보다 삽입 정렬이 훨씬 더 빠릅니다.

셸 정렬

셸 정렬은 삽입 정렬의 단순한 확장으로, 배열 항목 간의 먼 거리 교환을 허용하여 속도를 높이고, 결국 삽입 정렬로 효율적으로 정렬할 수 있는 부분적으로 정렬된 배열을 생성합니다.

아이디어는 배열을 재배열하여 h번째 항목(어디서든 시작)을 선택하면 정렬된 부분 수열이 되는 속성을 갖게 하는 것입니다. 이러한 배열을 h-정렬된 배열이라고 합니다. 다른 말로 하면, h-정렬된 배열은 h 개의 독립적으로 정렬된 부분 수열이 서로 엮여 있는 것입니다. 큰 h 값으로 h-정렬을 수행하면 배열 내의 항목을 멀리 이동시킬 수 있어 작은 h 값으로 h-정렬하기 쉬워집니다. 이러한 절차를 1로 끝나는 h 값 시퀀스에 대해 수행하면 정렬된 배열이 생성됩니다. 이것이 셸 정렬입니다.

다음은 Java에서 구현한 셸 정렬 코드입니다:

public class MaxPQ<Key extends Comparable<Key>> {
    // 우선순위 큐를 저장할 배열
    private Key[] pq;
    // 배열에 저장된 항목 수
    private int N;
    
    public MaxPQ(int capacity) {
        // 배열 초기화
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        // 배열이 비어있는지 확인
        return N == 0;
    }
   
    public void insert(Key key) {
        // 새 항목 삽입
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        // 최대 항목 삭제
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        // 새 항목을 위로 이동
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        // 최대 항목을 아래로 이동
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolea
```여기는 한국어 번역본입니다. 코드 부분은 번역하지 않고 주석만 번역했습니다.
 
```java
n less(int i, int j) {
        // pq[i]가 pq[j]보다 작으면 true를 반환합니다.
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        // pq[i]와 pq[j]의 값을 교환합니다.
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

이 코드는 배열 pq를 사용하여 최대 지향 이진 힙을 구현합니다. insert() 및 delMax() 연산은 swim() 및 sink() 도우미 메서드를 사용하여 힙 순서를 복원함으로써 힙 불변량을 유지합니다. 부모가 자식보다 크거나 자식이 부모보다 큰 경우 각각 키를 교환합니다.

스톱워치

더 유용한 추상 데이터 유형은 맞은편 페이지에 나와 있는 간단하고 효과적인 스톱워치 추상화입니다. 사용하려면 타이머를 시작할 때 Stopwatch 객체를 만들고 elapsedTime() 메서드를 사용하여 객체가 생성된 이후 경과된 시간(초)을 가져올 수 있습니다. 구현에서는 Java의 System.currentTimeMillis()를 사용하여 1970년 1월 1일 자정 이후 현재 시간(밀리초)을 가져옵니다.

start 인스턴스 변수는 스톱워치가 생성된 시간을 기록하고, elapsedTime()은 start를 사용하여 경과 시간을 계산합니다. 표시된 클라이언트는 일반적인 경우입니다. 일부 계산을 수행하고 Stopwatch를 사용하여 계산에 걸린 시간을 측정합니다. Stopwatch 데이터 유형은 스톱워치의 개념(인터페이스)과 구현(Java의 System.currentTimeMillis() 사용)을 분리하므로 효과적인 추상화입니다. 이러한 인터페이스와 구현의 분리는 이 책에서 다루는 모든 ADT의 기본적인 특성입니다.

요약

추상 데이터 유형은 객체 지향 프로그래밍의 필수적인 요소이며 현대 프로그래밍에 널리 사용됩니다. 이 섹션에서 우리는 다음을 보았습니다:

  • Java 클래스로 추상 데이터 유형 정의하기, 데이터 유형 값을 정의하는 인스턴스 변수와 해당 값에 대한 작업을 구현하는 인스턴스 메서드.
  • 동일한 API에 대한 여러 구현 개발하기, 동일한 추상 데이터 유형에 대한 다른 표현 사용하기.데이터 타입
  • 추상 데이터 타입의 API, 클라이언트, 구현을 구분하기.
  • 추상 데이터 타입의 API 설계하기.
  • 테스트와 디버깅을 위한 클라이언트와 테스트 클라이언트 개발하기.
  • 어설션을 사용하여 추상 데이터 타입 구현의 정확성 추론하기.
  • 동일한 API의 다른 구현 간 성능 비교하기.

이러한 활동은 모든 Java 프로그램 개발의 필수적인 부분입니다. 우리가 작성하는 모든 Java 프로그램은 라이브러리의 추상 데이터 타입을 사용할 것이며, 많은 경우 새로운 추상 데이터 타입을 개발할 것입니다. 다음 섹션에서는 수많은 프로그램의 필수적인 구성 요소인 세 가지 기본적인 추상 데이터 타입을 살펴보고, 1.4절에서는 구현의 성능 특성을 분석하는 과정을 자세히 다룹니다.

Chapter 2 Algorithms FundamentalsChapter 4 Searching Algorithms