알고리즘/실전알고리즘강좌(동빈나)

정렬(sorting) - 선택정렬(selection sort), 버블정렬(bubble sort), 삽입정렬(insertion sort), 퀵정렬(quick sort)

밀루루 2021. 12. 28. 22:12

선택정렬 

선택정렬은 말 그대로 '선택'하여 진행하는 정렬이다. 

선택정렬의 알고리즘은, 먼저 정렬할 배열을 순회하면서 가장 작은 숫자를 선택하고, 제일 앞에 있는 숫자와 순서를 바꾸는 것으로, 이와 같은 것을 배열의 크기 n 만큼 반복한다.

이해하기 쉽게 예를 들면 아래와 같다.

선택정렬

아래는 내가 짠 선택정렬의 코드이다. 강의에서는 가장 작은 수와 인덱스를 모두 저장하였지만 나는 인덱스만 저장하는 식으로 코드를 짰다는 것에서의 차이가 있었다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
int main() {
    int sort[10= { 1,3,5,8,9,6,2,4,10,7 };
    int small=0, index=0, temp, i;
    
    for (index; index < 10; index++) {
        //find small 
        small = index;
        for (i = index; i < 10; i++) {
            if (sort[i] < sort[small])
                small = i;
        }
        //swap small one and first one
        temp = sort[index];
        sort[index] = sort[small];
        sort[small] = temp;
    }
 
    //print sort
    for (int i = 0;i < 10;i++) {
        printf("%d ", sort[i]);
    }
    return 0;
}
cs

 

이러한 선택정렬의 한계에 대해서 살펴보면,

배열의 크기가 10(n=10)이라고 할 때, 10+9+8+...+1 만큼 반복하게 되는데, 이는 등차 수열로 10(10+2)/2 만큼 반복하게 된다. 즉, 배열의 크기가 n일때, n(n+1)/2 만큼 반복하게 되므로, 선택정렬의 시간복잡도는 O(n*n)이다.

 

버블정렬

 

 

 

삽입정렬

 

 

퀵정렬