'삽입정렬'에 해당되는 글 1건

정렬 알고리즘

정렬 알고리즘은 알고리즘 과목 중에서 기초적으로 반드시 알고 지나가야되는 파트입니다. 단순히 작은 순, 또는 큰 순으로 순서를 정렬하는 데에도 여러가지 알고리즘이 존재하는데요. 우리가 바로바로 이해할 수 있는 알고리즘이 있는 가 하면 좀 복잡하게 정렬하는 알고리즘도 있지요. 우리는 그나마 쉬운 편에 속하는 정렬 알고리즘 3개를 같이 보겠습니다.

1. 선택정렬(Selection Sort)

선택 정렬은 일단 자리는 정해져있습니다. 첫번째 자리에 가장 작은 녀석을 집어넣으면 되죠. 그리고 난 후에 두번째 자리에 그 다음 가장 작은 녀석을 선택해 집어 넣습니다. 이 짓을 배열이 끝날때까지 합니다.

다음 배열 arr에는 9, 8, 1, 2, 3이 있습니다. 이것을 선택정렬로 정렬하도록 해봅시다.

우선 제일 첫번째 자리 , 즉 9가 있는 자리를 i라고 놓고 j는 i 다음부터 배열의 가장 작은 index를 뽑아 옵니다. 그것을 minIndex라고 하지요.

j는 8부터 배열을 검색하면서 가장 작은 index를 찾아보니 1이 있는 자리가 제일 작군요. 그러니 minIndex는 2(1이 있는 배열 원소의 위치!)가 됩니다. 그래서 가장 첫번째 자리는 1이 되겠습니다.

그 후 두번째 자리(8이 있는 자리)가 i가 되고, j는 그다음 가장 작은 원소의 index를 구하게 되니까 minIndex는 2가 있는 자리, 즉 4가 됩니다.

minIndex와 i를 바꿉니다.

다음은 9가 있는 자리입니다. i는 2가 되겠네요. 가장 작은 인덱스는 3이 있는 자리이므로 i와 바꾸어 줍니다.

다음 i가 하나 증가되어 9를 가리킵니다. 8이 더 작으니까 바꾸어 주어야겠죠??

이제 모든 비교와 교환은 끝났습니다. 오름차순으로 정렬이 된것을 볼 수 있습니다.

아래는 선택정렬을 구현한 코드입니다.

void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(&arr[i], &arr[minIndex]);
    }
}

인덱스를 j라고 표시하겠습니다. 우선 가장 앞 자리부터 그 다음 원소를 비교합니다. 9와 8을 우선 비교하는 것이죠. 9가 더 크니 8과 9를 바꿉시다. 

그 다음 j가 하나 증가하여 다음 자리를 가리키고 9와 1을 비교합니다. 9가 더 크니 1과 9를 바꿉시다.

느낌 오시나요? 가장 큰 요소를 끝으로 보내려고 하는 겁니다. 다음 j를 하나 증가시키고 9와 3을 비교합니다. 9가 더크네요. 3과 9를 바꾸어줍니다.

다시 j가 하나 증가하게 되고 9과 2를 비교해보니 9가 더 크니까 자리를 바꾸어줍니다.

이렇게 보니까 9(제일 큰 수)가 제일 뒤로 갔군요. 

그 다음은 4번째(인덱스 3)까지 이런 방식을 반복합니다. 하나씩 줄여가면서 이런 방식을 반복하여 가장 큰수를 오른쪽으로 보내면 정렬이 되는 것이죠. 버블 정렬을 코드로 구현한 것이 아래에 있습니다.

void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

삽입 정렬을 우선 배열의 한 원소인 key라는 값을 우선 가지고 있고, 이 key를 알맞은 자리에 삽입하면 됩니다. key보다 큰 값은 하나하니씩 밀어버리고 key보다 작은 값을 만났으때 그 뒷자리에 삽입하는 것입니다.

그림을 통해봅시다.

우선 배열이 이렇게 있구요. 사실 계속 이 배열을 썼었죠.

우선 key값은 배열 인덱스 1번부터 시작입니다. i 이전의 원소를 비교해야하는데, 인덱스가 0이면 비교할게 없으니까요. key는 8로 8보다 큰 값은 오른쪽으로 밀어버립니다. 8보다 작은 원소가 발견되면 그 원소 뒤에 8을 삽입해야하는 데 없으므로 제일 앞에 삽입합니다.

8이 맨앞에 삽입 되고 난 후 i가 하나 증가하여 계속 비교합니다. key는 1이 됩니다. 1보다 작은 원소가 없으므로 제일 앞에 위치하게 됩니다.

이후 i가 하나 증가하고 키는 3입니다. 3보다 작은 원소를 만날때 그 뒤에 삽입하는 과정을 아래 그림이 보여줍니다.

이제 i가 하나 증가하게 되고 마지막 원소인 2가 키가 됩니다. 2보다 작은 원소는 1이므로 1뒤에 2를 삽입하는 것이 되지요. 아래 그림이 그 과정을 보여줍니다.

최종적으로 정렬된 상태는 바로 이와 같습니다.

삽입 정렬에 대한 코드는 아래와 같습니다.

void insertionSort(int arr[], int size) {
    int i, j, key;

    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

시간복잡도

선택 정렬과 버블 정렬은 항상 n^2의 시간복잡도를 갖지만 삽입정렬은 조금 다릅니다. 삽입 정렬은 평균적으로 n^2이지만 만약 정렬된 원소들로 구성된 배열이 입력으로 들어오면 n^2의 시간 복잡도를 갖습니다. for 루프안의 반복문이 1회만 실시하고 말거든요. 바로 현재 키보다 작은 원소를 만나기 때문입니다. 아래의 표로 쉽게 확인해보세요.

전체코드

확인하기 쉽도록 전체코드를 올립니다.

#include <stdio.h>

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(&arr[i], &arr[minIndex]);
    }
}
void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

void insertionSort(int arr[], int size) {
    int i, j, key;

    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}


void printArr(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr1[] = { 9,8,1,3,2 };
    int arr2[] = { 9,8,1,3,2 };
    int arr3[] = { 9,8,1,3,2 };
    int size = 5;
    printArr(arr1, size);
    selectionSort(arr1, size);
    printArr(arr1, size);
    printf("\n");

    printArr(arr2, size);
    bubbleSort(arr2, size);
    printArr(arr2, size);
    printf("\n");

    printArr(arr3, size);
    insertionSort(arr3, size);
    printArr(arr3, size);

    return 0;
}

정렬 알고리즘에는 이 밖에도 병합정렬, 퀵정렬, 힙정렬 등이 있습니다. 일단 이것부터숙지하도록 합시다.