[알고리즘-04] 정렬(Sorting) - 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬

1. 정렬(Sorting)

1) 정렬이란?

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

- 데이터를 정렬하면 검색을 더 쉽게 할 수 있음

 

- 오름차순(ascending order) 정렬 : 키 값이 작은 데이터를 앞쪽에 놓는 정렬

- 내림차순(descending order) 정렬 : 키 값이 큰 데이터를 앞쪽에 놓는 정렬

 

- 안정된(stable) 정렬 : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것

 

2) 내부 정렬과 외부 정렬

- 내부 정렬(internal sorting) : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용

- 외부 정렬(external sorting) : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용

 

 

 

---

 

 

2. 버블 정렬(bubble sort)

1) 버블 정렬이란?

- 요소의 개수가 n개인 배열에서 n-1번동안 패스(비교,교환을 하는 일련의 작업)을 하여 정렬하는 것

- 액체 안의 공기 방울이 보글보글 위로 올라오는 모습에서 착안

 

버블 정렬의 첫 번째 패스

 

[버블 정렬의 첫 번째 패스]

- 맨 끝의 두 요소부터 시작하여 왼쪽의 값과 오른쪽의 값을 비교함 (오름차순일 때)

- 왼쪽의 값이 더 크다면 두 값을 교환함

- 앞으로 한 칸씩 옮겨가면서 패스(비교,교환)를 반복함

- 가장 작은 수인 1이 맨 앞으로 가기 위해서 n-1회 패스를 반복함

 

- 위와 같은 과정을 n-1번 반복함

- 두 번째 패스에서는 첫 번째 패스보다 1회 적은 n-2회 패스를 반복함

 

2) 버블 정렬 구현

// 두 수를 교환하는 메서드
void swap(int[] a, int[] idx1, int[] idx2) {
    int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

// 버블 정렬 메서드
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);
}

 

3) 버블 정렬 구현 - 개선(1)

// 두 수를 교환하는 메서드
void swap(int[] a, int[] idx1, int[] idx2) {
    int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

// 버블 정렬 메서드 - 개선(1)
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라는 교환 횟수를 카운트하는 변수를 통해 쓸모없는 패스를 생략하여 알고리즘 개선

 

4) 버블 정렬 구현 - 개선(2)

// 두 수를 교환하는 메서드
void swap(int[] a, int[] idx1, int[] idx2) {
    int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

// 버블 정렬 메서드 - 개선(2)
void bubbleSort(int[] a, int n) {
    int k = 0;	// a[k]보다 앞쪽은 정렬을 마친 상태
    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;
    }
}

 

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

- k : a[k]보다 앞쪽의 요소는 이미 정렬을 마친 상태를 뜻함

- last : 각 패스에서 마지막으로 교환한 두 요소 가운데 오른쪽 요소(a[j])의 인덱스를 저장

- 하나의 패스를 마쳤을 때 last 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한

- 다음 패스에서 마지막으로 비교할 두 요소는 a[k]와 a[k+1]이 됨

 

 

 

---

 

 

3. 단순 선택 정렬(straight selection sort)

1) 단순 선택 정렬이란?

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

 

단순 선택 정렬 과정

 

- 가장 작은 값의 요소인 1을 선택하고 맨 앞의 요소 6과 교환

- 다음 작은 요소인 3을 선택하고 두 번째 요소 4와 교환

- 위와 같은 과정을 총 n-1회 반복

 

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소 교환

 

2) 단순 선택 정렬 구현

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

 

- 요솟값을 비교하는 횟수는 (n² - n) / 2회

- 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않음

 

 

 

---

 

 

4. 단순 삽입 정렬(straight insertion sort)

1) 단순 삽입 정렬이란?

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

- 2번째 요소부터 선택하여 앞쪽의 알맞은 위치에 삽입

 

단순 삽입 정렬 과정

 

2) 단순 삽입 정렬 구현

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

 

- 다음과 같은 작업으로 알맞은 위치를 찾음

 

1. 정렬된 열의 왼쪽 끝에 도달 (tmp = a[i])
2. tmp보다 작거나 같은 key를 갖는 항목 a[j]를 발견

 

 

- 드모르간 법칙을 적용하여 두 조건이 성립할 때까지 반복함

 

1. j가 0보다 큼
2. a[j-1] 값이 tmp보다 큼

 

- 요소의 비교 횟수와 교환 횟수는 n² / 2회

- 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적임

 

 

 

 

---

 

5. 단순 정렬의 시간 복잡도

- 지금까지 공부한 세 가지 단순 정렬(버블, 선택, 삽입)의 시간복잡도는 모두 O(n²)임

- 이러한 단순 정렬은 효율이 좋지 않음

- 이를 개선한 정렬들이 존재함 (다음 글에서)

 

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)