자료구조 - 정렬 알고리즘 (1)

여러 정렬 알고리즘 (삽입, 퀵, 병합)

1. 삽입 정렬(Insertion Sorting)

정렬하고자 하는 원소의 개수가 작은 경우에 효율적이다.
(주로 배열의 크기가 n <= 20인 경우)
stable sorting (기존 배열에서 동일한 값인 원소의 key order가 변하지 않음)

• 즉, n = 1인 경우에는 원소가 1개이므로 이미 정렬이 되어있다. 따라서
  n > 1인 경우부터 고려하여 a[1:n-1] 인 배열을 정렬해나가는 방식이다.

• 이미 정렬되어 있는 a[1:n-1] 에 a[n] 값을 삽입하면서 순서대로 정렬

• 구현 코드

void insert(int a[], int e, int i) // 정렬되어있는 배열에 a[j] 값을 삽입
{
	a[0] = e; 
    while(a[i] > e)
    {
     	a[i + 1] = a[i];
        i--;
    }
    a[i + 1] = e;
}

void insertionSort(int a[], int n) // 삽입 정렬 함수, a[1:j-1] 은 이미 정렬되어 있음
{
	int j, temp;
    for(j = 2; j <= n; j++)
    {
    	temp = a[j];
        insert(a, temp, j - 1);
    }
}

• 시간복잡도 (Time Complexity)
  average case (worst) : O(n^2)
  best case : O(n) (이미 정렬되어 있는 최적의 데이터인 경우)

2. 퀵 정렬(Quick Sort)

시간복잡도는 평균적으로 O(nlogn) 으로 삽입정렬에 비해 속도가 빠르다. 배열에서 특정한 값을 pivot(피벗)으로 정하여 부분적으로 정렬을 하는 정렬 (재귀호출 활용)
unstable sorting (기존 배열에 속한 같은 값 원소들의 key 순서가 변함)

• 구현 코드

void quickSort(int a[], int left, int right)
{
	int i, j, pivot;
    if(left < right)
    {
    		i = left;
            j = right + 1;
            pivot = a[left];
            do 
            {
            	do 
                {	
                	i++;
                } while (pivot > a[i]);
                do 
                {
                	j--;
                } while (pivot < a[j]);
                if (i < j)
                {
                	swap(a, i, j); // swap 함수 필요
                }
            } while (i < j);
            swap(a, left, j); // a[j] 값과 pivot 값 swap
            quickSort(a, left, j - 1);
            quickSort(a, j + 1, right);
}            

• 시간복잡도 (Time Complexity)

1. best case (average) : O(nlogn)
2. worst case : O(n^2) (초기 배열이 오름차순 또는 내림차순 정렬인 경우)

3. 병합 정렬(Merge Sort)

분할 정복 알고리즘으로서, 정렬하려는 배열을 분할하여 정렬을 수행한 다음에 정렬된 배열을 병합
삽입 정렬과 같은 stable sorting 방식
재귀함수 또는 반복문 활용

1. Iterative merge sorting (반복 병합 정렬)

• mergepass 라는 함수를 활용해서 size 를 2배씩 늘려가며 분할 정복
• 추가적인 공간이 필요하므로 공간은 힙 정렬에 비해 많이 차지함

• 분할 정복 알고리즘

void merge(int initList[], int mergedList[], int i, int m, int n)
{
	int j, k, t; // 구간 인덱스 정의
    j = m + 1;
    k = i;
    
    while(i <= m && j <= n)
    {
    	if(initList[i] <= initList[j])
        {
        	mergedList[k++] = initList[i++];
        }
        else
        {
        	mergedList[k++] = initList[j++];
        }
    }
    
    if(i > m)
    {
    	for(t = j; t <= n; t++)
        {
        	mergedList[t] = initList[t];
        }
    }
    else
    {
    	for(t = i; t <= m; t++)
        {
        	mergedList[k + t - i] = initList[t];
        }
    }

• mergepass 구현 코드

void mergePass(int initList[], int mergedList[], int n, int s)
{
	int i, j;
    for(i = 0; i < n - 2 * s + 1; i += 2 * s)
    {
    	merge(initList, mergedList, i, i + s - 1, i + 2 * s - 1);
    }
    if(i + s - 1 < n)
    {
    	merge(initList, mergedList, i, i + s - 1, n);
    }
    else
    {
    	for(j = i; j <= n; j++)
        {
        	mergedList[j] = initList[j];
        }
    }

• Iterative merge sort (반복 병합 정렬) 구현 코드

void mergeSort(int a[], int n)
{
	int s = 1; // 초기 분할 segment 크기를 1로 지정
    int e[MAX_SIZE]; // 추가 공간을 배열로 할당 
    
    while(s < n)
    {
    	mergePass(a, e, n, s);
        s *= 2;
        mergePass(e, a, n, s);
        s *= 2;
    }
}

• 시간복잡도 (Time Complexity) : O(nlogn)
  best case (average) : O(nlogn)
  worst case : O(nlogn)

2. Recursive merge sorting (재귀 병합 정렬)

• 재귀함수를 이용하여 분할 정복을 수행한 후, 두 배열을 병합하여 다시 다른 배열과 같은 과정 수행

• 연결리스트 활용을 위해 link 배열을 따로 설정

• 전체 배열 크기 n일 때의 분할 크기
  한 분할 요소 길이 : ceil(n / 2) (올림 함수)
  다른 분할 요소 크기 : floor(n / 2) (내림 함수)

• 분할 정복 구현 코드

int listMerge(int a[], int link[], int start1, int start2)
{
	int last1, last2, lastResult = 0;
    for(last1 = start1, last2 = start2; last1 && last2)
    {
    	if(a[last1] <= a[last2])
        {
        	link[lastResult] = last1;
            lastResult = last1;
            last1 = link[last1];
       	}
        else
        {
        	link[lastResult] = last2;
            lastResult = last2;
            last2 = link[last2];
        }
    }
    if(last1 == 0)
    {
    	link[lastResult] = last2;
    }
    else
    {
    	link[lastResult] = last1;
    }
}

• 반복 병합 정렬 구현 코드

int r_mergeSort(int a[], int link[], int left, int right)
{
	if(left >= right)
    {
    	return left;
    }
    int middle = (left + right) / 2;
    return r_mergeSort(a, link, listMerge(a, link, left, middle), listMerge(a, link, middle + 1, right);
}

• 시간복잡도 (Time Complexity) : O(nlogn)
  best case (average) : O(nlogn)
  worst case : O(nlogn)