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

Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) 

컴퓨터 알고리즘의 가장 기본이 되는 것이 정렬 알고리즘이다.

그 종류는 여러가지가 있는데 위와 같은 특징이 있다.

이 중에서 3개의 기본적인 정렬 알고리즘을 살펴 보자

선택 정렬

먼저 선택정렬이다

이중에서 가장 큰 값을 찾는다

그 후에 가장 큰 값과 맨 마지막 값의 자리를 바꾼다.

그럼 결과적으로 가장 큰값이 맨 끝자리로 오게 된다.

그렇다면 마지막 값에 대해서는 더이상 신경쓰지 않아도 된다.

이후에 남아있는 4개의 데이터에 대해서

다시 가장 큰 값을 찾아 4번째 위치에 있는 값과 자리를 바꿔 준다.

이와 같은 알고리즘을 마지막 1개의 값이 남을 때까지 반복해준다면

결론적으로 오름차순, 작은값을 맨 끝자리로 보내면 내림차순의 순서로

정렬이 가능하다.

selectionSort(A[], n)
{
    for last <- downto 2{
        A[1...last] 중 가장 큰 수 A[k]를 찾는다.
        A[k]<-> A[last]; A[k]와 A[last]값을 교환                                                               
    }
}
 

슈도코드로 선택정렬을 나타내면 다음과 같다.

시간 복잡도를 계산하면

1) for문은 n-1번 반복 되며

2) 가장 큰 수를 찾기위한 비교 횟수는 n-1, n-2, ... , 2 ,1 까지 이며

3) 교환은 상수 시간 작업이므로

T(n)= (n-1)+(n-2)+...+2+1 = n(n-1)/2 = O(n^2)

시간 복잡도는 O(n^2)이 된다.

선택 정렬은 모든 데이터에 대해서 비교연산의 경우가 같기때문에 

최악/최선/평균의 경우 시간복잡도가 모두 동일하다.

버블 정렬

다음으로 살펴볼 기본 정렬 알고리즘은 버블 정렬이다.

버블정렬은 선택 정렬과 기본 개념은 비슷하다.

즉, 버블 정렬에서도 역시 정렬할 데이터중 가장 큰값을 찾아 

그것을 맨 마지막자리로 옮겨온 후에 그 데이터는 잊어버리고 

나머지 데이터에 대해 같은 작업을 반복한다는 것이다.

다만, 최대값을 찾아서 그 최대값을 맨 마지막으로 가져오는 세부적인 방법에 대해서 

선택정렬과 차이를 보인다.

일단 첫번째 값부터 시작해서 자신의 다음값과 비교한다.

자신이 다음값보다 크면 다음값과 자리를 바꾼다.

두번째 값을 자신의 다음 값과 비교해서 자신이 더 크다면 자리를 바꾼다.

세번째 값도 마찬가지로 다음 값과 비교해서 자신이 더 크다면 자리를 바꾼다.

그렇게 맨 마지막값 바로 앞까지 반복을 실행한다면 한 페이지가 마무리된다.

버블 정렬을 비유적으로 물고기를 잡을때 몰아서 잡는 것으로 이해하면 쉬울 수 있다.

잔챙이들은 그물 밖으로 빠져 나올수 있지만 가장 큰 녀석을 빠져 나가지 못한다.

이와같이 최대값은 버블 정렬을 빠져 나가지 못하고 

마지막 인덱스로 몰려갈수 밖에 없다는 것이다.

만약 최대값이 가장 앞쪽의 인덱스에 있었다면 한 페이즈당 한번씩 뒤로 밀리며

결국 마지막 인덱스에 위치하게 될것이다.

bubbleSort(A[], n){
    for last <- downto 2{
        for i <- 1 to last - 1
            if(A[i]>A[i+1]) then A[i] <-> A[i+1] // 교환                                                      
    }
}
 

다음은 슈도 코드로 표현된 버블 정렬이다.

시간 복잡도는 다음과 같다.

1) 바깥 쪽 for문이 n-1번 반복

2) 안쪽 for문이 n-1,n-2,...,2,1  번 반복

3) 마지막 자리 교환은 상수 반복

T(n) = (n-1)+(n-2)+....+2+1 = O(n^2)

역시 선택 정렬과 마찬가지로 시간복잡도는 O(n^2)이 된다.

삽입 정렬

마지막으로 살펴볼 정렬 알고리즘은 삽입 정렬이다.

삽입 정렬 알고리즘은 위의 두 알고리즘과 약간의 차이를 보인다.

우리가 정렬할 데이터가 6개라면

첫번째 데이터는 데이터가 한 개 이므로 그자체로 정렬되어있다고 볼 수 있다.

거기에 두번째 데이터를 추가해서 두개의 데이터가 정렬된 상태로 만들어주는것이다.

위의 그림에서 보자면

15와 12를 정렬된 상태로 만들어주려면 12를 15앞으로 끼워 넣으면 된다.

(페이즈 1)

현재 12와 15가 정렬된 상태인데 다음 데이터인 13을 넣어준다.

3개의 데이터를 정렬하기 위해서 13을 12와 15 사이에 삽입한다.

(페이즈 2)

이렇게 하나씩 데이터하나씩 정렬되게 삽입하는게 삽입 정렬의 알고리즘이다.

위의 그림은 삽입정렬이 진행되고 있는 임의의 한 페이즈를 나타낸다. 

현재 인덱스의 변수값이 4라고 했을 때 앞쪽의 데이터들은 정렬 되어있다고 가정한다.

추가할 데이터 4는 tmp 변수에 넣어놓고, 

앞쪽의 데이터와 비교하고 앞쪽의 데이터가 크다면 그 데이터를 뒤로 이동시킨다.

만약 tmp안의 변수가 더 크다면 비교한 변수 뒤에 데이터 값을 넣어주게 된다. 

insertionSort(A[], n){
    for i<- 2 to n{
        A[1...i]의 적당한 자리에 A[i]를 삽입한다.                                                                  
    }
}

슈도 코드로 표현한 삽입 정렬이다.

시간 복잡도는 다음과 같다.

1) for문은 n-1번 반복

2) 최악의 경우 데이터 삽입을 위한 비교는 i-1번 반복

최악의 경우 T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

이므로 시간복잡도는 O(n^2)이 된다.

    public static void sort(int[] array) {
        for(int i = 1; i<array.length; i++){
            int temp = array[i];
            int comp = i-1;
            while(comp>=0 && array[comp]>temp){                                                            
                array[comp+1] = array[comp];
                comp--;
            }
            array[comp+1] = temp;
        }
    }
 

삽입 정렬의 구현코드이다.

 여기서 주목해야할 점은 while문 내부의 comp>=0 이다.

등호의 사용에 따라 큰 차이를 보이는데

등호를 붙이지 않아도 정렬은 구현이 된다.

그러나 등호를 붙이면 안정 정렬으로 구현할수 있다.

안정 정렬과 불안정 정렬의 차이는 동률의 값에 대한 변화의 유무이다.

예를들어 3이라는 데이터가 3개가 있을 때, 각각의 데이터를 3, 3', 3'' 라고 하자

안정 정렬은 이 데이터가 바뀌지 않으나 불안정 정렬은 데이터가 바뀌며

불필요한 연산으로 인한 오버 헤드가 발생하게 된다.

따라서 등호를 사용해서 안정 정렬으로 구현해주도록 하자.

위의 예제들을 통해 기본적인 정렬 알고리즘 3개를 분석해보았다

기본 정렬 알고리즘의 경우 간단하지만 속도가 느린 단점이있다.

다음은 복잡하지만 속도가 빠른 알고리즘에 대해 알아보도록 하자

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘