정렬과 탐색

자주 쓰이는 정렬

1. 버블 정렬

배열의 첫 원소보다 그 다음 원소를 비교해가며 두 원소를 바꾸는 작업을 계속한다.

평균 및 최악 실행 시간 O(n^2), 메모리 O(1)

2. 선택 정렬

선형 탐색을 하며 매 탐색마다 가장 작은 원소를 맨 앞으로 보내는 방식을 반복한다.

평균 및 최악 실행 시간 O(n^2), 메모리 O(1)

3. 병합 정렬

배열을 절반씩 나누어 각각 정렬한 후, 둘을 합하여 다시 정렬하는 방법.

평균 및 최악 실행 시간 O(nlogn), 메모리는 상황에 따라 다름

4. 퀵 정렬

무작위로 선정한 한 원소를 이용해, 작은 원소는 앞으로, 큰 원소는 뒤로 보낸다.

평균 실행 시간 O(nlogn), 최악 실행 시간 O(n^2), 메모리 O(logn)

5. 기수 정렬

각 자릿수를 순회해 나가며 각 자리의 값에 따라 기준으로 정렬한다. 상당히 재밌는 방식.

실행 시간 O(kn)

여기서 k는 자릿수의 개수이다.

위 정렬들 예시

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
void bubble(int rnum[], int n);
void selection(int rnum[], int n);
void merge(int rnum[], int n);
void mergeCode(int rnum[], int n);
void quick(int rnum[], int n);
void quickCode(int num[], int left, int right);
void radix(int rnum[], int n, int maxCipher);
int main()
{
    srand(time(NULL));
    int num[10];
    for (int i = 0; i < 10; ++i)
    {
        num[i] = rand()%100;
        printf("%d   ", num[i]);
    }
    printf("\n\n");
    bubble(num, 10);
    selection(num, 10);
    merge(num, 10);
    quick(num, 10);
    radix(num, 10, 2);
}
void bubble(int rnum[], int n)
{
    int *num = new int[n];
    copy(&rnum[0], &rnum[n], &num[0]);
    bool a = 1;
    for (int nn = n; 1 < nn; --nn, a = 1)
    {
        for (int i = 0; i < nn-1; ++i)
            if (num[i] > num[i + 1])
            {
                swap(num[i], num[i + 1]);
                a = 0;
            }
        if (a)
            break;
    }
    for (int i = 0; i < n; ++i)
        printf("%d   ", num[i]);
    printf("\n\n");
}
void selection(int rnum[], int n)
{
    int *num = new int[n];
    copy(&rnum[0], &rnum[n], &num[0]);
    for (int i = 0, min = 2147483647, p = i, j; i < n - 1; ++i, min = 2147483647, p = i)
    {
        for (j = i; j < n; ++j)
        {
            if (min > num[j])
            {
                p = j;
                min = num[j];
            }
        }
        swap(num[p], num[i]);
    }
    for (int k = 0; k < n; ++k)
        printf("%d   ", num[k]);
    printf("\n\n");
}
void merge(int rnum[], int n)
{
    int *num = new int[n];
    copy(&rnum[0], &rnum[n], &num[0]);
    mergeCode(num, n);
    for (int k = 0; k < n; ++k)
        printf("%d   ", num[k]);
    printf("\n\n");
}
void mergeCode(int num[], int n)
{
    int left = n / 2, right = n - left, l = 0, r = left, *copies, i = 0;
    if (n <= 1)
        return;
    mergeCode(num, left);
    mergeCode(num + left, right);
    copies = new int[n];
    copy(num, num + n, copies);
    for (;(l < left) && (r < n);++i)
        if (copies[l] <= copies[r])
            num[i] = copies[l++];
        else
            num[i] = copies[r++];
    while (l < left)
        num[i++] = copies[l++];
    while (r < n)
        num[i++] = copies[r++];
    delete[] copies;
}
void quick(int rnum[], int n)
{
    int *num = new int[n];
    copy(&rnum[0], &rnum[n], &num[0]);
    quickCode(num, 0, n-1);
    for (int k = 0; k < n; ++k)
        printf("%d   ", num[k]);
    printf("\n\n");
}
void quickCode(int num[], int left, int right)
{
    int index, pivot = num[(left + right) / 2], l=left, r=right;
    while (l <= r)
    {
        while (num[l] < pivot)
            ++l;
        while (num[r] > pivot)
            --r;
        if (l <= r)
            swap(num[l++], num[r--]);
    }
    index = l;
    if (left < index - 1)
        quickCode(num, left, index - 1);
    if (index < right)
        quickCode(num, index, right);
}
void radix(int rnum[], int n, int maxCipher)
{ // https://www.cs.usfca.edu/~galles/visualization/RadixSort.html 참조
    int *num = new int[n], *foot = new int[n], *count = new int[n];
    copy(&rnum[0], &rnum[n], &num[0]);
    int maxTen = 1, ten = 10;
    for (int i = 1; i++ < maxCipher;)
        maxTen *= 10;
 
    fill_n(count, 10, 0);
    for (int i = 0; i < n; ++i)
        ++count[num[i] % 10];
    for (int i = 0; i < 9; ++i)
        count[i + 1] += count[i];
    for (int i = n - 1, j; i > -1; --i)
    {
        j = num[i] % 10;
        foot[(--(count[j]))] = num[i];
    }
    copy(foot, foot + n, num);
 
    for (; ten <= maxTen; ten *= 10)
    {
        fill_n(count, 10, 0);
        for (int i = 0; i < n; ++i)
            ++count[num[i] / 10];
        for (int i = 0; i < 9; ++i)
            count[i + 1] += count[i];
        for (int i = n - 1, j; i > -1; --i)
        {
            j = num[i] / 10;
            foot[(--(count[j]))] = num[i];
        }
        copy(foot, foot + n, num);
    }
    for (int k = 0; k < n; ++k)
        printf("%d   ", num[k]);
    printf("\n\n");
}

--

탐색 알고리즘

대표적으로 이진 탐색이 있다.

이진 탐색은 정렬된 배열에서 원소 x를 찾을 때 사용한다.

#include<cstdio>
int bin(int a[], int x, int len);
int main()
{
    int a[100];
    for (int i = 0; i < 100; ++i)
        a[i] = i + 100;
    for (int i = 0; i < 100; ++i)
        printf("%d ", a[i]);
    printf("\n\n");
 
    printf("%d\n",bin(a, 199, 100));
}
int bin(int a[], int x, int len)
{
    int low = 0, high = len, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] < x)
            low = mid + 1;
        else if (a[mid] > x)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}