Chapter 06. 정렬 (1)

 

 

chapter 06 - 1 정렬

 

 

정렬 (sorting)

핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

작은 것부터 큰 순서로 정렬한 경우 오름차순 정렬 (ascending order), 
큰 것부터 작은 순서로 정렬한 경우 내림차순 정렬 (descending order)

 

  정렬 알고리즘의 안정성

    - 같은 값의 key를 가진 요소의 순서가 정렬의 전후에도 유지된다면 안정된 정렬이라고 함. 

    - 안정되지 않은 경우, 예를 들어 같은 점수인 학생끼리 이름 순 혹은 학번 순으로 자연스럽게 정렬되지 않음. 

 

  내부 정렬과 외부 정렬

    - 내부 정렬 (internal sorting)

      - 정렬하고자 하는 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용

    - 외부 정렬 (external sorting)

      - 정렬하고자 하는 데이터가 너무 많아 하나의 배열에서 작업할 수 없는 경우 사용

 

  정렬 알고리즘의 핵심 요소

  : 교환, 선택, 삽입

 

 

 

chapter 06 - 2 버블 정렬

 

 

버블 정렬 (bubble sort)

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하며 정렬하는 알고리즘 (안정적)

패스 (pass) : 정렬하고자 하는 배열에서 비교, 교환하는 작업(과정)
  ( 수행하는 패스의 횟수는요소가 n개라면,  n - 1회)

시간 복잡도 = O(n2)

 

  버블 정렬 프로그램

import java.util.Scanner;

class BubbleSort {
    static void swap(int[] a, int index1, int index2) {
        int temp = a[index1];
        a[index1] = a[index2];
        a[index2] = temp;
    }

    // 버블정렬
    static void bubbleSort(int[] a, int n) {
        // 패스
        for (int i = 0; i < n - 1; i++)  
            for (int j = n - 1; j > i; j--)
                if (a[j - 1] > a[j])         
                    swap(a, j - 1, j);      
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.println("버블정렬(버전1)");
        System.out.print("요소 수 : ");
        int num = scanner.nextInt( );
        int[] x = new int[num];

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "]");
            x[i] = scanner.nextInt( );
        }

        bubbleSort(x, num);

        System.out.println("\n오름차순 정렬 결과");
        for (int i = 0; i < num; i++)
            System.out.println("x[" + i + "] = " + x[i]);
    }
}

    - 비교 횟수는 첫 번째 패스에서 n - 1회, 두 번째에서 n - 2회, ,,, 이므로, 총 비교 횟수는 n(n - 1) / 2회

    - 교환 횟수의 평균값은 비교 횟수의 절반인 n(n - 1) / 4회

    - swap 메서드에서 값의 이동 횟수 : 3회

    ∴ 이동횟수 평균 = 3n(n - 1) / 4회

 

 

  알고리즘 개선 (1)

// 버블정렬 메서드만 수정 (버전 2)
static void bubbleSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int exchange = 0;
        // 패스
        for (int j = n - 1; j > i; j--) 
            if (a[j - 1] > a[j]) {        
                swap(a, j - 1, j);       
                exchange++;           
            }                                
        if (exchange == 0)
            break;
    }
}

    - 교환횟수 확인하는 변수 추가하여 교환이 없다면 종료하도록 수정

 

 

  알고리즘 개선 (2)

// 버블정렬 메서드만 수정 (버전 3)
static void bubbleSort(int[] a, int n) {
    int k = 0; 
    while (k < n - 1) {
        int lastChange = n - 1;
        // 패스
        for (int j = n - 1; j > k; j--)
            if (a[j - 1] > a[j]) {           
                swap(a, j - 1, j);         
                lastChange = j;         
            }                                          
        k = lastChange;
    }
}

    - 마지막으로 교환한 위치를 lastChange 변수에 저장하여 다음 정렬 수행 시 해당 위치에서 수행하도록 수정

    - 교환할 때마다 가장 오른쪽 요소의 인덱스 값을 lastChange 변수에 저장

 

 

 

chapter 06 - 3 단순 선택 정렬

 

 

단순 선택 정렬 (straight selection sort)

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
    (서로 떨어져 있는 요소를 교환하기 때문에 불안정함)

교환 과정

① 정렬되지 않은 부분에서 가장 작은 값을 선택 (a[min])
② 정렬되지 않은 부분의 첫 번째 요소와 a[min]의 값과 교환

시간 복잡도 = O(n2)

 

  단순 선택 정렬 메서드

static void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        swap(a, i, min);
    }
}

    - 비교 횟수 : (n2 - n) / 2회

 

 

 

chapter 06 - 4 단순 삽입 정렬

 

 

단순 삽입 정렬 (straight insertion sort)

선택한 요소를 더 앞쪽의 알맞은 위치에 삽입하는 작업의 반복으로 정렬하는 알고리즘
  (떨어져 있는 요소들이 바뀌는 것이 아니라 안정적)

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입
  ( 2번째 요소부터 선택하여 진행함)

두 조건 중 만족하는 위치에 값 대입
① 정렬된 열의 왼쪽 끝에 도달
② temp값보다 작거나 같은 key를 갖는 항목 발견

시간 복잡도 = O(n2)

 

  단순 삽입 정렬 프로그램

import java.util.Scanner;

class InsertionSort {
    // 단순 삽입 정렬
    static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int j;
            int temp = a[i];
            for (int j = i; j > 0 && a[j - 1] > temp; j--)
                a[j] = a[j - 1];
            a[j] = temp;
        }
    }

    public static void main(Stirng[] args) {
        Scanner scanner = new Scanner(System.in);
   
        System.out.println("단순 삽입 정렬");
        System.out.print("요소 수 : ");
        int num = scanner.nextInt( );
        int[] x = new int[num];

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "] : ");
            x[i] = scanner.nextInt( );
        }

        insertionSort(x, num);

        System.out.println("\n오름차순 정렬 완료");
        for (int i = 0; i < num; i++)
            System.out.println("x[" + i + "] = " + x[i]);
    }
}    

    - 비교 횟수와 교환 횟수 : n2 / 2회