[Data Structure] Chapter 10-1: 단순한 정렬 알고리즘

간단한 구조의 정렬 알고리즘인
버블 정렬, 선택 정렬, 삽입 정렬에 대해 이해하고 코드로 구현해보자.

 

 

버블 정렬

이해와 구현

• 버블 정렬(Bubble Sort): 인접한 두 개의 데이터를 비교해가며 정렬을 진행하는 알고리즘이다.

 

버블 정렬의 과정

 

#include <stdio.h>

void BubbleSort(int arr[], int n)
{
    int i, j;
    int temp;

    for(i=0; i<n-1; i++)
    {
        for(j=0; j<(n-i)-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                // 데이터의 교환 //
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }

        }
    }
}

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

    BubbleSort(arr, sizeof(arr)/sizeof(int));

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

    printf("\n");
    return 0;
}

1 2 3 4

 

성능 평가

• 정렬 알고리즘의 성능은 다음 두 가지를 근거로 판단하는 것이 일반적이다.
• 비교의 횟수: 두 데이터 간의 비교연산 횟수
• 이동의 횟수: 위치의 변경을 위한 데이터의 이동횟수

버블 정렬의 성능 평

 

 

선택 정렬

이해와 구현

• 선택 정렬(Selection Sort): 정렬 순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되는 알고리즘
• 정렬 순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 놓는다.

 

선택 정렬의 과정

 

#include <stdio.h>

void SelSort(int arr[], int n)
{
    int i, j;
    int maxIdx;
    int temp;

    for(i=0; i<n-1; i++)
    {
        maxIdx = i;

        for(j=i+1; j<n; j++)
        {
            if(arr[j]<arr[maxIdx])
                maxIdx = j;
        }

        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp; 
    }
}

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

    SelSort(arr, sizeof(arr)/sizeof(int));

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

    printf("\n");
    return 0;
}

1 2 3 4

 

 

성능 평가

선택 정렬의 성능 평가

 

 

삽입 정렬

이해와 구현

• 삽입 정렬(Insertion Sort): 정렬 대상을 둘로 나눠, 정렬이 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘이다.
• 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다.

 

데이터 삽입 위치를 찾고 삽입하는 과정

 

#include <stdio.h>

void InsertSort(int arr[], int n)
{
    int i, j;
    int insData;

    for(i=1; i<n; i++)
    {
        insData = arr[i];

        for(j=i-1; j>=0; j--)
        {
            if(arr[j]>insData)
                arr[j+1]=arr[j];
            else
                break;
        }

        arr[j+1] = insData;
    }
}

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

    InsertSort(arr, sizeof(arr)/sizeof(int));

    for(i=0; i<5; i++)
        printf("%d ", arr[i]);
    
    printf("\n");
    return 0;
}

1 2 3 4 5

 

코드 돌렸을 때 예상되는 과정!

 

성능 평가

• 비교연산, 이동연산 모두 최악의 경우에 안쪽 for문과 바깥쪽 for문의 반복횟수를 곱한 만큼 진행되므로, 비교연산과 이동연산에 대한 빅-오는 모두 $O(n^2)$이다.

 

 

---

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11