[알고리즘] 기본 정렬 알고리즘 (삽입 정렬, 선택 정렬, 버블 정렬)

- 선택 정렬 ( Selection Sort)

 

[ 개념 ]

 

선택 정렬은 현재 자신의 index보다 뒤에 있는 index들 중에서 배열의 원소 값이 가장 작은 원소랑 자리를 서로 바꿔줍니다.

이러한 방식으로 배열의 처음부터 끝까지 진행하여 정렬을 할 수 있습니다.

 

아래 그림은 선택 정렬의 예시로 다시 한번 설명해드리겠습니다.

 

먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다.

 

 

첫번째 index부터 시작하여 자신의 값보다 작은 값들 중에서 가장 작은 값을 찾습니다.

해당 배열에서는 '13'보다 작은 값 중에서 제일 작은 '2'를 택하게 됩니다.

제일 작은 값을 찾은 뒤 서로 자리를 swap합니다. 

 

 

 

다음 index로 넘어가 두번째 index를 기준으로 뒤에 있는 값들 중에서 가장 작은 값을 찾습니다.

해당 배열에서는 '7'보다 작은 값 중에서 가장 작은 값인 '3'이 되겠습니다.

마찬가지로 서로 자리를 바꿔줍니다.

 

 

마찬가지로 3번째 index를 기준으로 뒤에 있는 index 중에서 가장 작은 값을 찾습니다.

위의 배열에서는 5가 되고 '13'과 '5'의 위치를 서로 바꿔줍니다. 

 

위와 같은 방식으로 배열의 마지막 index까지 계속 진행합니다.

다음 index에 존재하는 값인 13를 기준으로 뒤에서 가장 작은 값을 찾습니다.

7이 가장 작으므로 '7'과 '13'의 위치를 서로 바꿔줍니다. 

 

 

마지막으로 16과 13까지 위치를 바꿔주면 배열이 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

 

 

[ 코드 ]

 

아래 코드와 같이 selection sort를 구현할 수 있다.

첫번째 index부터 시작하고

idx는 i부터 시작하여 자신보다 작은 값이 없을 경우 자리를 바꿔주지 않을 수 있다. 

 

void selection_sort(int arr[], int size)
{
    int idx =0;
    
    for(int i=0;i<size-1;i++){
        idx = i;
        
        for(int j=i+1;j<size;j++)
            if(arr[j] < arr[idx] )  idx = j;
        
        int tmp = arr[i];
        arr[i]= arr[idx];
        arr[idx]= tmp;
    }
}

 

위의 코드와 같이 전체 비교를 진행하므로 시간 복잡도는 O(N^2)이다.

 

 

- 삽입 정렬 ( Insertion Sort)

 

[개념]

삽입 정렬은 현재 index를 기준으로 앞에 있는 값들 중에서 현재 index에 존재하는 값이 들어갈 위치를 찾아서 삽입한다.

 

1. 현재 값이 들어갈 위치를 찾는다.

 

예시를 통해서 삽입 정렬을 다시 한번 설명하겠습니다.

 

 

먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다.

 

 

삽입 정렬은 현재 위치를 기준으로 앞에 있는 원소들과 비교하므로 배열 index로 1부터 시작합니다.

7을 기준으로 자신보다 앞에 있는 원소들 중에서 삽입될 자리를 찾습니다.

7은 13보다 작으므로 13 앞에 삽입됩니다.

 

 

 

 

다음 배열 값인 2는 7,13 보다 모두 작으므로 

제일 첫번째 자리에 삽입됩니다.

 

 

 

그 다음 4번째 index의 값인 5를 기준으로 5가 들어갈 자리를 찾습니다.

5는 2보다 크고 7보다 작으므로 2와 7사이에 들어갑니다.

 

 

 

5번째 index에 존재하는  16은 처음부터 16까지 모두 오름차순으로 정렬되어 있으므로 다음 index로 넘어갑니다.

 

 

마지막 index에 존재하는 숫자 3은 2보다 크고 5보다 작으므로 2와 5 사이에 삽입됩니다.

 

이와 같이 삽입 정렬을 통해 배열이 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

 

[코드]

 

아래 코드는 c언어를 사용해 insertion sort 함수를 구현한 것이다.

 

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

 

최악의 경우 시간 복잡도는 O(N^2)이다.

하지만 만약 배열이 처음부터 정렬되어 있었다면 while문을 실행하지 않게 되므로 시간 복잡도는 O(N)이다.

 

 

- 버블 정렬 ( Bubble Sort)

[개념]

버블 정렬은 인접한 두 원소를 비교해 정렬합니다.

1회전을 수행하면 가장 큰 값이 제일 뒤에 위치하게 됩니다. 

 

예시를 통해서 버블 정렬을 다시 한번 설명하겠습니다.

먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다.

 

 

 

위의 그림은 버블 정렬을 1회전 실행한 결과로 가장 큰 값이 제일 뒤에 위치한 것을 확인할 수 있습니다.

 

 

위의 그림은 버블 정렬 2회전을 하고 난 뒤의 결과로 첫번째 index부터 마지막 index까지 모두 정렬된 것을 확인할 수 있습니다.

 

 

 

[코드]

 

 

최상, 평균, 최악의 경우 모두 

N-1, N-2, ... ,1 = N(N-1)/2번 비교를 하게된다.

따라서 시간 복잡도는 O(N^2)이다.

 

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