정렬/검색 알고리즘

● 선택 정렬

① 주어진 리스트 중에 최솟값을 찾는다.
② 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
③ 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

void selection_sort(int list[], int n) {
    int s, m, i;
    int temp;

    for ( s = 0 ; s < n-1 ; s++ )  {
        m = s;
        for ( j = s+1 ; j < n ; j++ )
            if ( list[j] < list[m]) m = j ;  //내림차순 시 부호 변경 (   <         ---->       >)
        temp = list[s]; list[s] = list[m]; list[m] = temp;
    }
}


● 버블 정렬

① 처리할 데이터를 배열 list에 저장한다.
② 인접한 두 개의 데이터 list[j]와 list[j+1]을 비교하여 오름차순이 아니면 두 수를 교환한다.
③ 모든 데이터가 정렬되지 않으면 ②를 계속한다.

void bubble(int a[], int n)
{
    int i = n-2, j, tmp, flag = 1;            // 상태변수 flag는 교환이 이루어지지 않으면 정렬과정을 끝낸다.
    while ( flag && i != 0 ) {
        flag = 0;
        for ( j=0 ; j <= i ; j++ ) {
            if ( a[j] > a[j+1] ) {
                flag = 1;
                tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp;
            }
        }
        i--;
    }
}

● 삽입 정렬

삽입 정렬은 이미 정렬되어 있는 데이터에 계속적으로 들어오는 데이터를 적절한 위치에 삽입하여 정렬을 유지하는 개념을 이용한 것이다. 처음에 데이터에 대한 정보가 없을 때 전체 데이터를 정렬하는 경우
이미 정렬된 데이터는 1개라고 가정하기 때문에 i의 값이 1에서 시작한다.

void insertion(int a[], int n)
{
    int i, j, idata;
    for ( i = 1 ; i <=  n-1; i++ ) {
        idata = a[i];
        j = i - 1;
        while ( a[j] > idata && j >= 0 ) {
            a[j + 1] = a[j];
            j--;
        }
        a[j+1] = idata;
    }
}

● 퀵 정렬

① 피봇이라고 불리는 제어값을 정한다.
② 전체 데이터를 피봇을 중심으로 그 값보다 작은 값과 큰 값으로 두 개의 집합으로 나눈다.
③ 과정 ②에서 피봇  데이터는 자신의 위치를 찾게 된다. 즉 전체 데이터에서 피봇이 
    i번째 데이터라면 i번째 위치하도록 한다.
④ 과정 ②에서 만들어진 두 데이터 집합에 대하여 같은 과정을 수행한다.

void quick_sort(int a[], int left, int right)
{
    int pivot, i, j, tmp;
    
    if ( left < right ) {
        i = left ; j = right + 1; pivot = a[left];
        while ( i < j ) {
            do
                i++;
            while (( a[i] <= pivot ) && ( i < right ));
            do
                j--;
            while (( a[j] >= pivot ) && ( j > left ));
            if ( i < j ) {
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp
            }
        }
        if ( j != left ) {
            tmp = a[j];
            a[j] = a[left];
            a[left] = tmp;
        }
        quick_sort(a, left, j-1);
        quick_sort(a, j+1, right);
    }
}

● 이진 합병 정렬

이진 합병 정렬은 정렬된 두 데이터 집합을 하나의 정렬된 데이터 집합으로 합병하는 정렬 방법이다.

int merge( int * a1, int * a2, int * a, int n1, int n2 )
{
    int i = 0, j = 0, k = 0;

    while ( i < n1 && j < n2 ) {
        if ( a1[i] < a2[j] )
            a[k++] = a1[i++];
        else if ( a1[i] > a2[j] )
            a[k++] = a2[j++];
        else {
            a[k++] = a1[i++];
            j++;
        }
    }
    if ( i == n1 )
        while ( j < n2 ) a[k++] = a2[j++];
    else
        while ( i < n1 ) a[k++] = a1[i++];

    return k;
}

● 이진 검색

기존의 프로그래밍 기법에서는 배열의 인덱스를 증가시켜가며 순차적으로 검색하는 방법이 많이 사용되지만 대부분의 데이터는 정렬되어 저장된다는 점을 활용하면 보다 성능이 향상된 다음과 같은 검색방법을 생각할 수 있다.

int bsearch(int a[], int n, int key)
{
    int mid;
    int left = 0, right = n-1;
    while ( left <= right ) {
        mid = ( left + right ) / 2;
        if ( key > a[mid] ) left = mid + 1 ;                     
        else if ( key < a[mid] ) right = mid - 1;
        else retrun mid;
        }
    }
}