알고리즘 내용에서 정렬에 대한 내용을 공부해보았습니다.

아래는 오늘 공부한 내용을 요약한 노트입니다.

정렬

데이터 집합을 정해진 순서로 재배열하는 것으로서 오름차순과 내림차순으로 구성되있습니다.

정렬은 비교와 교환의 기본 연산이며 비교와 교환의 조합이 정렬 알고리즘입니다.

많은 정렬 알고리즘이 존재합니다.

키 값과 레코드

키값 : 비교의 대상이며 정렬의 기준입니다.

레코드 : 교환의 대상이며 하나의 정보 단위입니다.

여러 정렬 알고리즘

복잡성에 따라서 단순한 선택, 삽입, 버블, 쉘정렬부터 복잡한 퀵, 기수, 힙, 병합정렬이 있습니다.

교환 방식에 따라서 레코드 전체를 이동하여 정렬하는 직접 정렬과 별도 키값의 인뎃그만 정렬하는 간접정렬이 있습니다.

선택 정렬

최소값을 찾아서 앞으로 오게합니다.

정렬되지 않은 부분에서 최소값을찾아 정렬된 부분의 뒤에 더합니다.

일단 저는 vector의 swap을 이용했습니다.

for (int j = 0; j < vecsize - 1; ++j) {
    int min = j;
    for (int i = j+1; i < vecsize; ++i) {
        if (sort.at(min) > sort.at(i)) {
            min = i;
        }
    }  
    if (min != j)
        swap(sort.at(j), sort.at(min));
}

삽입 정렬

현재 레코드를 일부 정렬된 부분의 알맞은 위치로 옮기는 것입니다.

void insertion_sort(int arr[], int length)
{
    for (int i = 1; i < length; i++) {
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }
}

버블 정렬

인접요소의 비교와 교환을 통해 최대값을 가장 뒤로 보냅니다.

삽입정렬과 반대의 모양을 띱니다.

void bubbleSort(vector<int>& a)
{
      bool swap_b = true;
      while(swap_b){
        swap_b = false;
        for (size_t i = 0; i < a.size()-1; i++) {
            if (a[i]>a[i+1] ){
                a[i] += a[i+1];
                a[i+1] = a[i] - a[i+1];
                a[i] -=a[i+1];
                swap_b = true;
            }
        }
    }
}

퀵 정렬

크기가 1보다 클 동안 분할을 재귀적으로 반복합니다. 멀리떨어져 있는 요소를 교환하기 때문에 효율적입니다.

분할 알고리즘 : 축값을 중심으로 왼쪽은 축값보다 작은 값, 오른쪽은 축값보다 큰값으로 배열시키는 알고리즘입니다.

qsort 메소드를 이용해서 구현할 수 있습니다.

재귀로 구현하면 스택 오버플로우 오류가 발생할 수 있다고 합니다.

힙 정렬

우선순위 큐 : 새로운 데이터를 넣을 수 있고, 가장 우선순위가 높은 데이터를 뽑아 낼 수 있는 자료구조입니다.

예시 : stack - push와 pop, queue - put과 get, 힙 - insert와 remove

우선순위 큐의 연산자 : 생성, 삽입, 제거, 대치, 변경, 삭제, 결합

힙 : 키 값의 크기가 우선순위가 되고, complete binary tree로 구성됩니다.

힙 정렬 : 힙을 생성하고, 힙에 자료가 하나도 남지 않을때까지 추출합니다.

쉘 정렬

삽입 정렬 문제(비교와 교환의 횟수)를 개선했으며, h-sort를 반복하여 정렬합니다.

병합 정렬

병합을 반복하므로서 전체 정렬을 하며, 순차적으로 작은 자료를 뽑아서 놓으면 됩니다.

기수 정렬

양의 정수만을 정렬할 수 있는 정렬 방법이며, 비트 조작을 통해 정렬합니다.

분포수 세기 : 같은 키가 많이 붕복되는 정수 집합에 적용하며 특정 키가 출현하는 빈도와 누적 분포를 이용합니다.

단일 루프여서 O(n)의 성능을 내고 메모리 낭비가 없습니다. 다만, 양의 정수만 취급하므로 장점만 있지는 않습니다.

기수 교환 정렬

퀵정렬과 유사한 분할의 재귀적 반복이며, 분할의 기준은 bit입니다.

퀵정렬과 유사하지만, 분할의 축값이 없습니다.

직접기수 정렬

분포수 세기를 최하위 비트부터 진행하며, 이 역시 O(n)의 성능을 가집니다.

메모리의 크기가 커질 수록 성능은 상승합니다.