왕초보의 알고리즘 정렬 종류 파헤치기 2 (버블정렬, 삽입정렬, 선택정렬 / 코드 구현 C)

시작하기 전에 이전 포스팅을 먼저 보고 오시는 것을 추천드립니다.

왕초보의 알고리즘 정렬 종류 파헤치기 1 (자료구조, 시간 공간 복잡도)

 

정렬들의 예제를 만들어보자. Push swap처럼 숫자의 크기 대로 정렬하는 것을 예로 들어 만들어 보겠다.

---

1. 버블정렬 (Bubble Sort)

버블 정렬 또는 거품 정렬(-整列, 영어: bubble sort 버블 소트[*], sinking sort 싱킹 소트[*])은 정렬 알고리즘 중 하나이다. 시간 복잡도가 O(n²)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 이를 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

가운데로 긁어모은다!

 

버블정렬은 두개의 크기를 비교하고 바꿔주면서 반복된다. 만약에 7, 2, 0, 1, 5, 6, 4라는 숫자의 배열을 입력한다고 가정해 보자.

그러면 코드로 한번 만들어보자!

#include <stdio.h>

int *bubble_sort(int *arr, int n);

int  main()
{
    int arr[7] = {7, 2, 0, 1, 5, 6, 4}; //정수가 들어있는 배열을 만들어준다.
    int *sorted; //새로 정렬될 배열을 하나 만들어준다.
    int i;

    sorted = bubble_sort(arr, 7); //버블정렬을 통해 자리를 바꿔준다.
    i = -1;
    while(++i < 7)
        printf("%d\n", sorted[i]); //한자리씩 출력해본다.
    return (0);
}

int *bubble_sort(int *arr, int n)
{
    int i;
    int j;
    int tmp;

    i = n - 1;
    while (i > 0)
    {
        j = 0;
        while(j < i)
        {
            if(arr[j] > arr[j + 1]) //앞자리가 뒷자리보다 클 경우!
            {
                tmp = arr[j]; //앞자리를 임시저장소에 넣고
                arr[j] = arr[j + 1]; //앞자리 숫자를 뒷자리로 바꿔주고
                arr[j + 1] = tmp; //뒷자리는 임시저장소의 숫자로 바꾼다.
            }
            j++; //반복
        }
        i--; //반복
    }
    return (arr); //새로 정렬된 배열을 보낸다.
}

 

$ ./a.out
0
1
2
4
5
6
7

---

2. 삽입정렬 (Insertion sort)

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다. 선택 정렬이나 거품 정렬과 같은 O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

이 정렬은 우리가 카드를 손에 쥐고 있을 때, 두번째 자리에서부터 앞으로 옮기면서 숫자를 비교해서 이동한다. 이게 무슨 뜻이냐, 아래의 그림을 보면 더 빠르게 이해될 것이다.

옆에서부터 맞은 정렬을 찾아 긁어 모은다!

삽입 정렬은 버블정렬보다 3배정도 빠른 속도로 자료를 처리한다. 위와 똑같이  7, 2, 0, 1, 5, 6, 4라는 숫자의 배열로 예를 보자.

그러면 한번 코딩을 해보까!

#include <stdio.h>

int *insertion_sort(int *arr, int n);

int  main()
{
    int arr[7] = {7, 2, 0, 1, 5, 6, 4};
    int *sorted;
    int i;

    sorted = insertion_sort(arr, 7); //선택정렬 함수로 이동
    i = -1;
    while(++i < 7)
        printf("%d\n", sorted[i]);
    return (0);
}

int *insertion_sort(int *arr, int n)
{
    int i;
    int j;
    int tmp;

    i = 0;
    while(i < n)
    {
        j = i;
        tmp = arr[i]; //일단 n번째 배열 숫자를 임시저장소에 저장해주고, (2 저장)
        while(--j >= 0 && tmp < arr[j]) //만약에 전 숫자가 앞 숫자보다 크다면? (7이 2보다 크다)
            arr[j + 1] = arr[j]; //앞 숫자는 전 숫자가 되고 (7이 2의 자리를 차지함)
        arr[j + 1] = tmp; //뒷숫자는 임시저장소의 숫자가 된다. (앞 숫자는 2가 됨)
        i++;
    }
    return (arr);
}

 결과는?

$ ./a.out
0
1
2
4
5
6
7

---

3. 선택정렬 (Selection sort)

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 O(n²) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

정렬의 과정을 그림으로 보면 더욱 쉽게 이해할 수 있다!

최솟값을 찾아서 차례로 정렬!

선택 정렬은 버블 정렬과 삽입 정렬보다 훨씬 효율적이고 우수하다! 

#include <stdio.h>

int *selection_sort(int *arr, int n);

int  main()
{
    int arr[7] = {7, 2, 0, 1, 5, 6, 4};
    int *sorted;
    int i;

    sorted = selection_sort(arr, 7); //선택정렬로 고고고!
    i = -1;
    while(++i < 7)
        printf("%d\n", sorted[i]);
    return (0);
}

int *selection_sort(int *arr, int n)
{
    int i;
    int j;
    int tmp;
    int index_min; //최솟값을 위한 변수를 만들어주고

    i = 0;
    while (i < n)
    {
        index_min = i; //최솟값은 항상 첫 수부터 시작한다.
        j = i + 1; //1회가 끝나면 숫자를 좁혀가야 하기 때문에 설정해 놓는다.
        while(j < n)
        {
            if(arr[j] < arr[index_min]) //만약에 arr[j]가 최솟값보다 작다면
                index_min = j; // j를 최솟값으로 다시 지정한다.
            j++; //계속 돌리면서 최솟값인지 확인해 본다.
        }
        tmp = arr[index_min]; //최솟값을 임시저장소에 넣고
        arr[index_min] = arr[i]; //가장 앞의 수와 최솟값을 바꾼다.
        arr[i] = tmp;
        i++;
    }
    return(arr);
}

$ ./a.out
0
1
2
4
5
6
7

 

출처

https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC

버블 정렬 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

삽입 정렬 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전