정렬 -1

정렬이란?

정렬은 이름, 학번, 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다.

 

안정된 정렬이란?

같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다.

 

내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

 

1. 버블 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.

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

어떤 패스에서 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이기 때문에 정렬을 멈추면 된다.      exchg = 한 번의 패스에서 시도한 교환 횟수 (0이면 정렬을 마친 것)

 

static void bubbleSort2(int[] a, int n) {
        int k = 0;
        while (k < n - 1) {
            int last = n - 1;
            for (int j = n - 1; j > k; j--) {
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    last = j;
                }
            }
            k = last;
        }
    }

각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각해도 좋다.

last = 각 패스에서 마지막으로 교환한 두 요소 가운데 오른쪽 요소의 인덱스 값

k = 수행할 패스의 범위를 제한하는 용도

 

2. 선택정렬

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

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);
        }
    }

선택 정렬 알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않습니다.

 

 

3. 삽입정렬

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

static void insertionSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int j;
            int tmp = a[i];
            for (j = i; j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

 

4. 셸 정렬

셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘이다.

 

-단순 삽입 정렬의 특징

장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.

단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 해야 하는 횟수가 많아진다.

 

셸 정렬은 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법

여러개의 그룹으로 나누어 정렬하는 이유 : 정렬이 된 상태에 가까운 배열로 만들어 놓기 위해서.

static void shellSort(int[] a, int n) {
        for (int h = n/2; h >0 ; h/=2) { // 증분값 3, 1....
            for (int i = h; i < n ; i++) {
                int j;
                int tmp =a[i];
                for (j = i -h; j>= 0 && a[j] > tmp; j-=h) {
                    a[j +h] = a[j];
                }
                a[j+h] = tmp;
            }
        }
    }

그룹을 나누고 합칠 때 섞이지 않으면 다시 처음 단계와 다를게 없다.

이런 문제를 해결하기 위해서는 h값이 서로 배수가 되지 않도록 해야 한다.

static void shellSort2(int[] a, int n) {
        int h;
        for (h=1; h<n/9; h=h*3+1);
 
        for ( ; h >0 ; h/=3) {
            for(int i =h; i<n; i++) {
                int j;
                int tmp = a[i];
                for (j=i-h; j>=0 && a[j] > tmp; j-=h) {
                    a[j+h] = a[j];
                }
                a[j+h] = tmp;
            }
        }
    }

h의 초깃값은 너무 크면 효과가 없기 때문에, 배열의 요솟수 n을 9로 나눈 값을 넘지 않도록 정한다.

 

셸 정렬의 시간 복잡도는 O(n^1.25) 으로 기존의 단순 정렬보다는 빠르지만, 

이 알고리즘도 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.

 

---

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]