07_정렬 ① 버블정렬/단순선택정렬/단순삽입정렬

• 정렬(sorting): key의 대소 관계에 따라 데이터를 일정한 순서로 바꾸는 작업
• 같은 값을 가진 요소의 순서가 정렬 전/후에도 유지되면 → 『안정된 알고리즘』이라고 한다.
• 정렬 알고리즘의 핵심 요소: 교환, 선택, 삽입

① 버블 정렬(bubble sort)

- 안정적인 알고리즘 : 이웃한 요소를 비교하고 교환하는 작업을 반복

- O(n²): 효율 좋지 않음

- 모든 정렬이 끝나려면 n - 1회의 패스가 수행되어야 한다.

   1) version 1. 

static void bubbleSort(int[] a) {
    // 방법1. 배열의 뒷쪽부터 비교/교환 수행 → 각 패스에서 가장 작은 값의 요소가 앞으로 옮겨짐
    for (int i = 0; i < a.length-1; i++)
        for (int j = a.length-1; j > i; j--)
            if (a[j-1] > a[j])
                swap(a, j-1, j);

    // 방법2. 배열의 앞쪽부터 비교/교환 수행 → 각 패스에서 가장 큰 값의 요소가 끝으로 옮겨짐
    for (int i = 0; i < a.length-1; i++)
        for (int j = i; j < a.length-1; j++)
            if (a[j] > a[j+1])
                swap(a, j, j+1);
}

 

   2) version 2. 

- 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻

- 패스의 교환 횟수를 기록해서, 값이 0이면 계속 실행하지 않고 종료하게끔

static void bubbleSort(int[] a) {
    int exchg;                      
    for (int i = 0; i < a.length-1; i++) {
        exchg = 0;
        for (int j = a.length-1; j > i; j--)
            if (a[j-1] > a[j]) {
                swap(a, j-1, j);
                exchg++;
            }
        if (exchg == 0) break;     // 교환횟수가 0이면 종료
    }
}

 

   3) version 3. 

- 한 번의 패스에서 어떤 시점 이후에 교환이 수행되지 않는다면, 그보다 앞쪽의 요소는 이미 정렬을 마친 상태!

- 마지막으로 교환이 이루어진 오른쪽 요소의 인덱스를 저장해놓고 활용

static void bubbleSort(int[] a) {
   int k = 0;   // a[k]보다 앞쪽은 정렬을 마친 상태
   while (k < a.length - 1) {
       int last = a.length - 1;     // 마지막으로 요소를 교환한 위치
       for (int j = a.length - 1; j > k; j--)
           if (a[j-1] > a[j]) {
               swap(a, j-1, j);
               last = j;
           }
       k = last;
   }

 

   4) 양방향 버블 정렬, 칵테일 정렬, 셰이커 정렬 → 더 적은 횟수로 비교할 수 있음

       : 홀수 번째 패스에는 가장 작은 요소를 맨 앞으로 옮기고, 짝수 번째 패스에는 가장 큰 요소를 맨 뒤로 옮기는 방식

         (패스의 스캔 방향을 교대로 바꿈)

static void shakerSort(int[] a) {
    int front = 0;
    int rear = a.length - 1;  
    int last = a.length - 1;    // swap() 이 끝난 마지막 인덱스 위치
    int count = 1;              // 반복 횟수 세기 위한 변수
    boolean isSwap;             // swap 발생 여부 체크

    // 최대 n-1번 반복하니까
    while (count < a.length) {  
        isSwap = false;
        // 홀수: 가장 작은 요소를 맨 앞으로 옮김(뒤부터 스캔)
        if (count % 2 == 1) {
            for (int j = rear; j > front; j--)
                if (a[j-1] > a[j]) {
                    swap(a, j-1, j);
                    isSwap = true;
                    last = j;
                }
            front = last;
        }
        // 짝수: 가장 큰 요소를 맨 뒤로 옮김(앞부터 스캔)
        else {
            for (int j = front; j < rear; j++)
                if (a[j] > a[j+1]) {
                    swap(a, j, j+1);
                    isSwap = true;
                    last = j;
                }
            rear = last;
        }

        if (front == a.length - 1 || front == rear || isSwap == true) break;
    }
}

 

② 단순 선택 정렬

- 불안정적인 알고리즘: 서로 떨어져 있는 요소를 교환(같은 값을 가진 요소의 순서가 뒤바뀔 수 있음)

- O(n²): 효율 좋지 않음

: 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

<교환 과정>

1. 아직 정렬하지 않은 부분에서 가장 작은 값을 찾음

2. 가장 작은 값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

→ 이 과정을 n - 1회 반복하면 된다.

static void selectionSorting(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;        // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스 값 저장
        for (int j = i + 1; j < a.length; j++)
            if (a[min] > a[j])
                min = j;
        swap(a, i, min);    // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환
    }
}

 

③ 단순 삽입 정렬(셔틀 정렬, shuttle sort)

- 안정적인 알고리즘: 떨어져 있는 요소들이 서로 뒤바뀌지 않음

- O(n²): 효율 좋지 않음

- 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘

- 2번째 요소부터 선택하여 진행,

  아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입

  → 이 과정을 n - 1회 반복하면 된다.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int j;
        int temp = a[i];
        for (j = i; j > 0 && a[j - 1] > temp; j--)
            a[j] = a[j - 1];
        a[j] = temp;
    }
}