10. Sort #1 Basic sort Algorithm

정렬 단원에서는 여러 가지 정렬 알고리즘들을 나열하며 소개하고 있다.

따라서 각 방법들의 특징과 그에 따른 장단점을 비교하며 학습하면 좋을 것 같다.

10-1 단순한 정렬 알고리즘

1) Bubble Sort

(1) Implement

버블정렬은, 비교 기준을 순차적으로 이동해나가며, 기준과, 그 옆의 대상을 비교하여 정렬하는 알고리즘이다.

비교의 기준을 1번째 → 2번째 → 3번째로 이동하며 기준 중심으로 한 칸 오른쪽에 있는 값과 기준을 비교한다.

비교 후 우선순위가 낮은 값(현재는 오름차순 정렬이기 때문에 큰 값의 우선순위가 더 작다)을 뒤로 보내고, 이 과정을 계속해서 반복한다.

이후, 이미 자리가 결정된 4를 제외한, 앞의 세 개를 대상으로 다시 한 번 더 버블정렬을 시작한다.

#include <stdio.h>

//n=length of the array
void BubbleSort(int arr[], int n) {
    int i, j;
    int tmp;
    for (i = n;i>1 ;i--) {
        for (j = 0;j < i-1 ;j++) {
            if (arr[j] > arr[j + 1]) {//priority Error -> switch
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

int main(void) {
    int i;
    int a[4] = { 4,2,3,1 };
    BubbleSort(a, 4);
    for (i = 0;i < 4;i++) {
        printf("%d ", a[i]);
    }
}

(2) Evaluation

알고리즘의 성능을 판단하기 위해 핵심 연산을 생각해보자.

버블정렬에서 연산의 핵심은 비교와 이동이다.

• 비교 연산
• if (arr[j] > arr[j + 1])
• 이동연산
• for (i = n;i > 1 ;i--) for (j = 0;j < i-1 ;j++)

비교연산은 이동할 때 마다 발생하니, 효율성을 계산할 때는 이동연산의 횟수를 구해 2배를 해주면 된다. → 아니란다. 둘이 각각 비교해줘야 한다.

데이터의 개수가 n개라고 하면

1번째 시행에서 이동 횟수는 n-1회다.

2번째 시행에서 이동 횟수는 n-2회다.

계속해서 1회만 비교할 때 (n-1번째) 까지 비교를 진행한다.

결국 1~n-1의 값까지 더한 결과로 성능을 평가할 수 있다.

→ O(n²)

2) Selection Sort

(1) Implement

선택정렬에 대해 알아보자.

<사진>

이와 같이 대상 중에서 가장 우선순위가 높은 것들을 탐색하여 하나씩 배치하는 알고리즘이다.

이렇게만 보면, 결과를 저장할 새로운 배열을 만들어야 한다고 생각할 수 있다. 하지만, 별도의 배열 없이도 진행할 수 있다.

<사진>

이처럼 자리가 지정된 요소들을 제외한 나머지를 대상으로 가장 우선순위가 높은 요소와 ‘교환’하는 방법이 있다.

가장 우선순위가 높은 것을 계속 탐색하고, 이를 배치한다는 점에서 앞의 과정과 사실상 동일하다.

(2) Code

#include <stdio.h>

void SelSort(int arr[], int n) {
    int i, j;
    int tmpMin, minIndex;
    int tmp;

    for (i = 0;i < n - 1;i++){//setting'i'th element
        tmpMin = arr[i];
        minIndex = i;
        //find min value and it's index
        for (j = i + 1;j < n;j++) {
            if (tmpMin > arr[j]) {
                tmpMin = arr[j];
                minIndex = j;
            }
        }

        if (minIndex == i)//it was okay at the first time
            continue;

        else {//swtich arr[i], arr[minIndex]
            tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
}

int main() {
    int i;
    int a[4] = { 3,2,1,4 };
    SelSort(a, 4);
    for (i = 0;i < 4;i++) {
        printf("%d ", a[i]);
    }
}

(3) Evaluation

성능평가를 하기 위해 핵심이 되는 계산을 생각해보자.

마찬가지로 비교와 이동이 핵심 계산이다.

• 비교연산 = if (tmpMin > arr[j]) : 마찬가지로 1~n-1을 더한 횟수만큼 진행하니
• → O(n²)

• 이동 = (i = 0;i < n - 1;i++) : 비교만 보면, 성능상 버블정렬과 큰 차이가 없어보이지만, 선택정렬은 최외곽에서만 이동을 하기 때문에 그 횟수가 n회다.
• → O(n)

3) Insert sort

(1) Implement

<사진>

삽입 정렬은 선택정렬과 비슷해 보이지만, 정렬이 안되어 있는 부분의 데이터를 정렬된 부분에 하나씩 삽입하여 정렬하는 것이다.

이와 동일한 기능을 구현하는 다른 방법도 찾아보자.

<사진>

이처럼 정렬 안된 부분의 데이터를 하나 잡아 한 칸씩 숫자를 밀며 자리를 찾아가는 방식을 취할 수도 있다.

(2) Code, Debugging

1. 처음에 짰던 알고리즘

#include <stdio.h>

void InsSort(int arr[], int n) {
    int i, j;
    int move;
    for (i = 1;i < n;i++) {//start of unsorted array
        move = arr[i];
        for (j = i - 1;j >= 0;j--) {//first small element -> put move in the back 
            if(move < arr[j]){
                arr[j + 1] = arr[j];
            }
            else {
                arr[j + 1] = move;
            }
        }
    }
}

int main(void) {
    int i;
    int a[4] = {4, 2, 3, 1};
    InsSort(a, 4);

    for (i = 0; i < 4; i++)
        printf("%d ", a[i]);

    return 0;
}

for문이 잘 안돌아간다.

• 한 칸씩 뒤로 미루는 과정을 계속 하다가 → else에서 move을 대입하고 for문을 탈출해야 하는데 계속 돌아가고 있기 때문에 오류가 나고 있는 것이다.
• else에 break한 줄만 추가해도 되겠지만, for문의 조건문을 사용하여 조금 더 짧게 구성해보려고 한다.

1. 수정for문의 원리를 보면하지만 처음에 작성했던 for문은 탈출해서 나올 타이밍을 찾지 못했고 계속해서 값을 대입했기 때문에 문제가 되는 것이다.
   1. 한 칸씩 자리를 비켜주는 과정
   2. 삽입하는 과정또한, 자리 비켜주는 과정이 끝났을 때의 j값이 필요하니, 그대로 for문을 나와서 j값을 사용해주면 된다.
   3. 으로 나눈 후, 한 과정이 끝나면 뒤의 과정을 진행할 것이다.
2. 따라서, 과정을 분리하여
3. → move보다 작은 것 만날 때 까지 계속 한 칸씩 자리 비켜주다가, 작은 것 발견하면 바로 뒤에 삽입하고 탈출해야 한다.
4. #include<stdio.h> void InsSort(int arr[], int n) { int i, j; int move; for (i = 1;i < n;i++) {//start of unsorted array move = arr[i]; for (j = i - 1;j >= 0&& move < arr[j];j--) {//first small element -> put move in the back arr[j + 1] = arr[j]; } arr[j + 1] = move; } } int main(void) { int i; int a[4] = {4, 2, 3, 1}; InsSort(a, 4); for (i = 0; i < 4; i++) printf("%d ", a[i]); return 0; }

4) Sum

이로써 기본적인 정렬 알고리즘들에 대해 살펴보았다.

사실 세 알고리즘의 설명을 보며 가장 인상적이었던 부분은, 개념을 설명한 이후, 해당 개념을 구현할 것 까지 고려하여 한 번 더 수정하여 설명한다는 점이었다.

예를 들어 선택 정렬도 결과 값을 할당할 새로운 배열이 필요할 것이라 생각했는데, 굳이 메모리를 낭비하지 않고 ‘교환’을 이용하여 동일한 개념을 구현하였다

또한, 삽입 정렬에서도 삽입하는 과정을 어떻게 구현할 지 고민하고 있었는데, 삽입할 위치를 찾는 과정과, 삽입할 자리를 마련하는 과정을 합쳐서

→비교하고, 한 칸씩 값을 뒤로 미는 코드로 개념을 동일하게 구현하였다.

복습할 때는, 구현한 코드와 알고리즘의 개념이 어떻게 연결되는지를 중심으로 보면 좋을 것 같다.