[자료구조] 선택/버블 정렬

1) 정렬의 개요

실행 방법에 따른 분류

• 비교식 정렬(Comparative Sort)
  • 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법
• 분산식 정렬(Distributive Sort)
  • 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

정렬 장소에 따른 분류

• 내부 정렬(Internal Sort)
  • 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
  • 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨
  • 교환 방식 : 키를 비교하고 교환하여 정렬하는 방식(선택 정렬, 버블 정렬, 퀵 정렬)
  • 삽입 방식 : 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 쉘 정렬)
  • 병합 방식 : 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)
  • 분배 방식 : 키를 구성하는 값을 여러 개의 부분 집합에 분배하여 정렬하는 방식(기수 정렬)
  • 선택 방식 : 이진 트리를 사용하여 정렬하는 방식(히프 정렬, 트리 정렬)
• 외부 정렬(External Sort)
  • 정렬할 자료를 보조 기억장치에서 정렬하는 방식
  • 대용량의 보조 기억장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능
  • 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 정렬 방식(2-way 병합, n-way 병합)

안정성에 따른 분류

• 1차 키: 학점
• 2차 키: 학년
• 안정 정렬에서는 1차 키로 정렬하더라도 이전의 2차 키 정렬 순서가 유지됨

정렬 대상에 따른 분류

2) 선택 정렬

• 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬
• 전체 원소 중 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환함
• 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환함
• 그 다음 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환함
• 이 과정을 반복하면서 정렬을 완성함

selectionSort(a[], n)
{
    for (int i=1; i<n; i++) 
    {
        a[i], …, a[n-1] 중에서 가장 작은 원소 a[k]를 선택하여,
        a[i]와 교환한다.
    }
}

메모리 사용 공간

• n개의 원소에 대하여 n개의 메모리 사용

비교 횟수

• 1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
• 2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
• 3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교

• i단계 : i번째 원소를 기준으로 n-i개의 원소 비교

• 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n^2)이 된다.

3) 버블 정렬

• 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
• 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
• 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(Bubble) 정렬이라 함

bubbleSort(a[ ], n)
{
    for (int i=n-1; i>=0; i--) {
        for (int j=0; j<i; j++) 
        {
            if (a[j] > a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp
            }
        }
    }
}

메모리 사용 공간

• n개의 원소에 대하여 n개의 메모리 사용

연산 시간

• 최선의 경우 : 자료가 이미 정렬되어있는 경우
  • 비교 횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2번
  • 자리 교환 횟수 : 자리 교환이 발생하지 않음
• 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우
  • 비교 횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2번
  • 자리 교환 횟수 : i번째 원소를 (n-i)번 교환하므로, n(n-1)/2번
• 평균 시간 복잡도는 O(n^2)이 된다.