[자료구조] 5주차 - 정렬 (Sorting)

Sorting

리스트 연산은 정렬된 리스트일 때 성능이 더 좋음

정렬 : 데이터를 정해진 키에 따라서 크기 순으로 배열 하는 것

O(n^2) 정렬 알고리즘 : 버블, 삽입, 선택, ···

• 이동 기반 : 삽입 정렬
• 교환 기반 : 버블 정렬, 선택 정렬

O(n log n) 정렬 알고리즘 : 합병, 쾌속, ···

• 분할 정복 방식(divide&conquer) : 합병, 쾌속
• 트리 구조 이용 : 히입 정렬

O(n^2) 정렬 : 삽입, 버블, 선택

삽입 정렬(Insertion sort)

추가(insert) 연산에 기반한 정렬 알고리즘

정렬되지 않은 리스트의 원소들을 차례로 정렬된 리스트에 추가하며 정렬을 수행

배열의 가장 앞자리부터 정렬된 부분 배열을 생성하고 그 크기를 증가시킴

void insert( int x, int n, int a[]){
    int i, j;

    // x의 위치 선정
    for(i = 0; i < n; i++){
        if( a[i] > x)
            break;
    }
    // x뒤에 들어갈 원소들을 한 칸씩 미루기
    for(j = n-1; j >= i; j--)
        a[j+1] = a[j];

    // x의 삽입
    a[i] = x;
    return;
}

void insertion_sort( int n, int a[] ) {
    int i;
    for ( i= 1; i< n; i++ ) 
        insert ( a[i], i, a );
}

성능 분석

• insert() : O(n)
• insert()를 호출하는 횟수 : O(n)
• 시간 복잡도 : O(n^2)

버블 정렬 (Bubble sort)

교환을 통해서 더 작은 원소를 앞으로 보냄

서로 인접한 원소들 사이의 교환을 반복해서 정렬을 수행함

배열의 가장 뒷자리부터 원소들을 차례로 비교하면서 작은 값을 가장 앞 자리로 옮김

두 번째로 작은 원소는 앞에서 두 번째 자리로 옮김 이를 n-1번 반복

Sinking sort라고도 함

void swap (int &a, int &b) { int x; x = a; a = b; b = x; } 

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

성능 분석

• 안쪽 for-loop의 수행 횟수 : n(n-1)/2 = O(n^2)
• (n-1) + (n-2) + ··· + 1 = n(n-1)/2

단점 : 최악의 경우 O(n^2)번의 교환을 수행해야 함

선택 정렬(Selection sort)

최악의 경우에도 O(n)번 만 교환 - 버블 정렬의 단점 보완

i번째 자리에 i번째로 작은 원소 배치

i번째로 작은 원소를 찾아서 i번째 원소와 교환

//인덱스 s부터 e까지 중에서 가장 작은 원소를 찾는 함수
int select_min(int s, int e, int b[]){
    int min_idx = s;
    for(int i = +1; i <= e; i++){
        if(b[i] < b[min_idx])
            mind_idx = i;
    }
    return min_idx;
}

void selection_sort(int n, int a[]){
    int i;
    int min_idx;
    for(i = 0; i < n-1; i++){
        min_idx = select_min(i, n-1, a);
        swap(a[i], a[min_idx]);
    }
}

성능 분석

• select_min() : O(n)
• select_min() 함수를 O(n)번 수행
• 결과 : O(n^2)

O(n log n) 정렬 : 합병, 쾌속

분할 정복의 3단계

• 주어진 집합의 데이터를 적절한 크기의 부분 집합으로 나눔 (divide)
• 부분 집합에서 문제를 해결 (conquer)
• 해결된 부분 해를 합쳐서 주어진 집합의 해를 구함 (combine)

분할 정복 방식의 3가지 구성 요소

• 같은 형식으로 문제를 해결할 것
• 분할될 때마다 문제의 크기가 감소할 것
• 예외적인 경우에 대한 처리를 할 것

합병 정렬(Merge Sort)

합병 정렬의 근거

• 정렬된2 개의리스트(L & R)를 하나의 정렬된 리스트(M)로 합병하는데 걸리는 시간

  • L의 원소 또는 R의 원소 선택 : O(1)
  • M의 모든 원소 결정 : n * O(1) -> O(n)

  합병 정렬의 원리

• O(n)정렬을 log n 번 수행

  • O(n log n)

int n;
int*arr;

void merge_sort( int s, int e){
    if(s == e)
        return;
    mid = (s + e)/2;
    merge_sort(s, mid);
    merge_sort(mid+1, e);
    merge(s, mid, mid+1, e);
}

void merge(int ls, int le, int rs, int re){
    int lptr = ls, rptr = rs, bptr = 0;
    int *brr = (int*)calloc((le-ls)+re-rs)+2, sizeof(int));

    while(lptr <= le && rptr <= re){
        if(arr[lptr] < arr[rptr])
            brr[bptr++] = arr[lptr++];
        else
            brr[bptr++] = arr[rptr++];
    }
    if(lptr > le){
        for(int i = rptr; i <= re; i++)
            brr[bptr++] = arr[i];
    }
    if(rptr > re){
        for(int i = lptr; i <= le; i++)
            brr[bptr++] = arr[i];
    }

    arr <- brr;
}

성능 분석

• 분할 : O(n)
• 정복 : O(1)
• 결합 : O(n log n)
• 시간 복잡도 : O(n log n)
• 점화식 표현 : T(n) = 2T(n/2) + O(n)

쾌속 정렬(Quick Sort)

분할 정복 구조의 정렬 알고리즘

결합을 요구하지 않는 분할 정복 구조 - 리스트를 적절하게 분할하여 결합할 필요 X

쾌속 정렬의 근거

• 분할 (split) 사용
  • 기준이 되는 값(Pivot)을 중심
  • Pivot의 왼쪽에는 더 작은 값이 오도록 배치
  • Pivot의 오른쪽에는 더 큰 값이 오도록 배치

int split(int s, int e, int A[]){
    int pivot, left, right, pivot = A[s];
    left = s+1, right = e;

    while(left <= right){
        while((A[right] >= pivot) && (left <= right))
            right--;
        while((A[left] <= pivot) && (left <= right))
            left++;
        if(left <= right)
            swap(A[left], A[right]);
    }
    swap(A[right], A[s]);
    return right;
}

void quick_sort(int s, int e, int A[]){
    if(s >= e)
        return;
    int m = split(s, e, A);
    quick_sort(s, m-1, A);
    quick_sort(m+1, e, A);
}

성능 분석

• T(n) = (n+1) + (1/n)[ {T(0) + T(n-1)} + {T(1) + T(n-2)} + ··· + {T(n-1) + T(0)}]
• T(n) = O(n log n)

Worst case

• 오름차순 또는 내림차순일 경우 : O(n^2)

기타 정렬

내부 정렬(internal sort)

• 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
• 지금까지 배운 정렬들은 모두 내부정렬

외부 정렬(external sort)

• 대용량의 보조 기억 장치를 이용해서 정렬하는 방식
• 데이터가 매우 많을 경우

쉘 정렬(shell sort)

• 일반화된 삽입 정렬
• 배열을 부분 배열로 분할하여 각각 삽입 정렬 수행
• 정렬된 부분 배열을 통합 하면서 삽입 정렬을 반복해서 수행

기수 정렬(radix sort)

• 버킷(bucket)을 이용한 분배 방식의 정렬
• 정렬할 원소를 버킷에 분배하는 과정을 반복해서 수행

하이브리드 정렬(hybrid sort)

• 팀 정렬(tim sort)
  • 합병 + 삽입
  • 데이터의 크기가 16 or 32보다 작으면 삽입, 크면 합병
• 인트로 정렬( intro sort)
  • 쾌속 + 힙
  • 쾌속 정렬을 하다가 너무 깊이 내려가면 힙 정렬을 사용

카운트 정렬

• k개의 count를 배열로 설정
• 데이터에 대한 count를 증가
• O(n+k)

보고 정렬(bogo sort, stupid sort, mokey sort)

• 데이터의 순서를 랜덤으로 바꾸며 정렬이 됐는지 판단
• 가장 비효율적 - O(n*n!)

슬립 정렬(sleep sort)

• 쓰레드의 슬립을 이용한 정렬
• 슬립이 빨리 끝난 순서대로 저장, O(k)

버켓 정렬(bucket sort)

• n개의 데이터를 k개의 버켓에 저장
• 버켓 내부의 데이터 정렬 O(1)
• k개의 버켓을 합병 O(n)
• 데이터가 균등하게 분포 되어있을 때만 효과적, O(n)을 추구

정렬의 성질

1. Comparison : 데이터를 비교해서 정렬하는가?
   • 비교 정렬이 아닌 정렬 : 기수, 슬립, 보고 등..
2. Adaptive : 부분적으로 정렬된 데이터에 대해서 더 좋은 성능을 보이는가?
   • Adaptive하게 발전시킬 수 있는 정렬 : 버블 정렬
     • 스왑을 한번도안할 경우 정렬을 마치도록 수정
3. Stable : 같은 값을 갖는 원소들이 자리를 바꾸는가?
   • 선택 정렬은 Stable하지 않음
4. In-place : 추가적으로 요구하는 메모리가 O(1)인가?
   • 삽입/버블/선택 정렬 : 요구하는 메모리 없음
   • 쾌속/합병 정렬 : 추가 메모리 요구(합병 정렬은 In-place로 개선 가능)
5. Online : 계속 증가하는 데이터에 대해서 정렬이 가능한가?
   • 삽입/버블 정렬 : Online하다
   • 선택 정렬 : 데이터가 추가되면 처음부터 다시 정렬해야 됨