[알고리즘] 선택 / 버블 / 삽입 정렬

정렬은  n개의 원소를 순서대로 배열하는 것이다. 원소는 숫자, 문자, 문자열, 날짜 등 다양한 것이 될 수 있다. 정렬은 그 자체로도 매우 자주 사용되지만 알고리즘의 설계와 분석, 생각하는 방법 등을 훈련하기에도 더없이 적합한 주제인 것 같다. 이번 포스팅에서는 짧고 핵심만 간추려서 간단하고 기본적인 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬을 Java로 구현해보고 각 정렬이 완료되는데 걸리는 시간도 보도록 한다.

 

선택 정렬

선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나이다. n개의 원소를갖는 배열 A[a[1], a[2], ..., a[n]]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 맞바꾼다. 그러면 현재 A[n]에는 이 배열에서 가장 큰 원소가 있으므로 더 이상 맨 뒷자리는 신경쓰지 않아도 된다. 그냥 한 줄로 요약하면,

 

가장 작은 원소를 맨 앞으로 보낸다. 혹은 가장 큰 원소를 맨 뒤로 보낸다. 라고 생각할 수 있겠다.

 

배열 A의 원소 개수가 10개라면, 선택 정렬은 각 원소를 10번, 9번, 8번, 7번, ... 1번 비교하게 된다. 이는 10*(10-1)/2 = 55로 나타낼 수 있으며 N * (N - 1) / 2라고 쓸 수 있다. 알고리즘의 시간 복잡도는 O(N^2)가 되겠다.

  static void Selection_Sort(int[] arr){

        int temp, idx=0;

        for(int i=0; i<size; i++){
            int min = 99999;
            for(int j=i; j<size; j++){
                if(arr[j] < min){
                    min = arr[j];
                    idx = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
        }
    }

버블 정렬

버블 정렬도 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. 선택 정렬이 가장 큰 수를 찾은 다음 맨 뒤의 수와 바꾸는 것이라면, 버블 정렬은 앞쪽 부터 이웃한 수를 비교하며 순서가 제대로 되어있지 않으면(앞쪽 > 뒤쪽) 하나씩 바꾸어 나간다. 그렇게 안쪽 루프의 첫 번째 루프가 끝나면 가장 큰 수는 맨 뒤에 위치해 있다. 즉 안쪽 루프를 한 번 돌 때마다 맨 뒤에서 부터 한 칸씩 정렬이 되어 나가는 것이다.

 

이웃한 수를 비교해서 큰 수를 뒤로 보내자.

 

버블 정렬의 시간 복잡도 역시 선택 정렬과 동일하게 O(N^2) 이다.

    static void Bubble_Sort(int[] arr){

        for(int i=0; i<size; i++)
            for(int j=1; j<size-i; j++)
            
                if(arr[j] < arr[j-1]) {
                
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    
                }
    }

삽입 정렬

삽입 정렬은 이미 정렬되어 있는 i개 짜리 배열에 하나의 원소를 더 추가해 정렬된 i+1개 짜리 배열을 만드는 과정을 반복한다. 선택 정렬과 버블 정렬이 n개 짜리 배열에서 시작하여 그 크기를 하나씩 줄이는 데 반하여, 삽입 정렬은 한 개짜리 배열에서 시작하여 그 크기를 하나씩 늘리는 정렬이다.

 

풀어서 설명하자면, 각 숫자를 적절한 위치에 삽입한다는 뜻이다. 선택 정렬과 버블 정렬은 무조건 정렬이 일어났다면, 삽입 정렬은 필요할 때만 정렬이 일어난다. 삽입 정렬은 비교적 느린 정렬 알고리즘에 속하지만, 기본적으로 "정렬이 되어있다"고 가정한 상태에서는 굉장히 빠른 속도를 나타낸다.

 

    static void Insertion_Sort(int[] arr){

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

---

다음은 10개의 난수를 가진 배열을 정렬한 결과이다.

 

데이터의 개수를 100,000개로 했을 때의 시간을 보도록 하자.

정렬이 많이 되어있는 난수 배열이 들어왔었는지 삽입 정렬 시간이 제일 짧았다. 그러나 역시 이 정렬 방법들은 가장 간단하고 기본적이지만, 자원 소모가 심한 정렬 방법이므로 차라리 기본 제공되는 Arrays.sort 또는 Collections.sort (Java에서)를 쓰는 것이 간편하고 가독성도 높일 수 있다.

 

# References

쉽게 배우는 알고리즘

동빈나님 블로그

동빈나님 유튜브