정렬 알고리즘 1 (단순 정렬)

• 정렬 알고리즘이란?

 정렬은 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말합니다.

   

    1) 정렬 알고리즘의 안정성

  만약 학번순으로 나열된 성적들의 배열이 있다고 하자. 이를 성적순으로 정렬했을 때 성적이 같은 값들이 학번순으로 정렬했던 것이 유지가 되면 안정된 정렬이라 하고 반드시 학번순으로 정렬되지 않는 정렬을 안정되지 않은 정렬이라고 한다.

 

    2) 내부 정렬과 외부 정렬

  내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘이다.

  외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘이다.

 

    3) 정렬 알고리즘의 핵심 요소

  정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입으로 대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것이다.

 

• 버블 정렬 (= 단순 교환 정렬)

 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 하는 과정을 반복하는 알고리즘이다. 크기가 n인 배열 a의 a[n-2]와 a[n-1]의 값을 비교해 a[n-1]의 값이 더 작으면 오름차순 정렬을 위해 값을 서로 교환해 준다. 그다음은 a[n-3]과 a[n-2]의 값을 비교해 a[n-2]의 값이 더 작으면 서로 교환해 준다. 이를 a[0]와 a[1]까지 n-1번의 비교를 거치면 a[0]은 배열 내의 가장 작은 값으로 정해진다. 이렇게 비교, 교환을 통해 가장 작은 요소를 맨 앞으로 이동시키는 과정을 패스라 하고 n-1번의 패스를 통해 정렬을 끝내면 오름차순으로 배열이 정렬되는데 이를 버블 정렬이라 한다. 버블 정렬 알고리즘은 서로 이웃한 요솟값을 서로 비교, 교환하므로 안정적인 알고리즘이라 볼 수 있다.

static void swap(int[] a, int x, int y){
    int temp =a[x];
    a[x]=a[y];
    a[y]=temp;
}
static void bubble(int[] a, int n){
    for(int j=0;j<n-1;j++) {
        for (int i = n - 1; i > j; i--) {
            if (a[i] < a[i - 1]) swap(a, i, i - 1);
        }
    }
}

 bubble 메서드를 보면 내부 for문은 패스하는 코드이고 이 패스를 n-1번 반복시키는 것이 외부 for문이다. 그리고 swap 메서드는 a 배열의 x와 y번째 index의 값을 교환해 주는 메서드이다.

 

  버블 정렬은 위와 같이 구현이 가능하다. 하지만 이를 더 효율적으로 바꾸는 방법이 2가지 있다. 

 

 

    1번째 개선 알고리즘

 

 만약 크기가 7인 배열의 버블 정렬을 한다고 하자. 0, 1번째 요솟값을 정렬시켰고 다음 2번째 요솟값을 정렬시킬 때 만약 2, 3번째의 교환을 제외한 나머지 비교과정에서 교환이 일어나지 않았다 해보자.(3, 4비교 ~ 5, 6비교까지 교환 x) 그러면 2, 3번째 교환을 통해 2번째 요솟값을 고정시켰을 때 정렬이 끝난 것을 알 수 있다. 실제로 다음 패스과정에서 교환은 한 번도 일어나지 않는다.

 

   ex) [2번째 패스 후] 1 3 6 4 7 8 9    >>  [3번째 패스 후]  1 3 4 6 7 8 9  (사실상 정렬 끝)

 

 하지만 위에서 사용한 코드처럼 진행이 된다면 정렬이 끝났음에도 의미 없는 패스를 3번이나 더 해야 한다.(비교를 6번 더 해야 함) 그래서 생각한 것이 위의 경우처럼 패스가 진행될 때 교환이 한번도 일어나지 않는다면 정렬이 끝났다 보고 패스반복을 종료하는 방법이다. 코드는 다음과 같다.  

static void swap(int[] a, int x, int y){
    int temp =a[x];
    a[x]=a[y];
    a[y]=temp;
}
static void bubble(int[] a, int n){
    for(int j=0;j<n-1;j++) {
        int exchg = 0;
        for (int i = n - 1; i > j; i--) {
            if (a[i] < a[i - 1]){
                swap(a, i, i - 1);
                exchg ++;
            }
        }
        if(exchg==0) break;
    }
}

 외부 for문을 시작할 때 exchg(교환 횟수)를 0으로 초기화 시키고 swap할 때마다 exchg를 1씩 늘린다. 만약 외부 for문이 끝났을 때, 즉 패스가 한번 완료되었을 때 exchg==0이면 패스반복을 중단하고 메서드를 종료한다.(정렬이 끝났다 판단)

 

 

    2번째 개선 알고리즘 

 

 1번째 개선 알고리즘은 패스 과정에서 교환이 일어나지 않았을때의 개선방법이다. 하지만 만약 초반에 교환이 1번만 일어나고 계속 비교만 하는 패스가 존재하면 어떨까? 크기가 7인 배열이 있고 그 배열이 { 1, 2, 9, 4, 7, 8, 6 }이라 하면 첫 번째 패스 중 (5, 6), (4, 5), (2, 3)에서 교환이 일어난다( 첫 번째 패스 결과 >> { 1, 3, 4, 9, 6, 7, 8 } ). 그리고 두 번째 패스를 하려 하는데 사실상 첫 번째 패스에서 (0, 1), (1, 2)의 교환이 이뤄지지 않아 오름차순인 것을 알 수 있고, (2, 3)은 교환을 했기 때문에 오름차순인 것을 알 수 있다. 따라서 (0 ~ 3)의 정렬은 사실상 끝난 것이다. 하지만 우리가 위에서 쓴 코드는 2번째 패스, 3번째 패스를 순서대로 진행할 것이고 이는 효율적이지 않다. 따라서 이렇게 굳이 할 필요 없는 패스를 생략하는 방법을 만든 것이 2번째 개선 알고리즘이다. 위의 예시를 요약하면 마지막 교환이 일어난 부분까지는 정렬이 끝났다고 보는 것이다. 이를 코드로 구현해 보자.

static void swap(int[] a, int x, int y){
    int temp =a[x];
    a[x]=a[y];
    a[y]=temp;
}
static void bubble(int[] a, int n){
    int k = 0; // a[k]보다 앞은 정렬이 끝난 상태
    while(k<n-1){
        int last = n-1; // last = 마지막으로 교환이 이루어진 위치
        for(int i = n-1; i>k; i--){
            if(a[i]<a[i-1]) {
                swap(a, i, i - 1);
                last = i ;
            }
        }
        k = last;
    }
}

 k 는 어디까지 정렬이 끝났는지 알려주고 last는 마지막으로 교환이 이루어진 위치를 알려준다. while문은 k < n-1일 경우에만 반복되는데 k = n-1일 경우 정렬이 n-1까지 끝났다는 뜻으로 메서드가 종료된다. k < n-1인 경우 반복은 실행되고 last는 n-1로 초기화된다. last = n-1로 초기화하는 이유는 1번째 개선 알고리즘처럼 교환이 이루어지지 않는 경우 정렬이 완성되어 메서드를 종료해야 하기 때문이다. 즉  last = n-1로 유지되고 내부 for문이 끝나면 k = last가 되므로 k = n-1이 돼서 다음 while 조건문을 통해 메서드가 종료되게 하기 위해서이다. 만약 교환이 1번이라도 이루어진 경우 그때의 i 값을 last에 저장하고 패스가 끝나면 이를 k에 저장해 다음 패스 시 정렬이 완료된 부분을 확인하여 그 부분부터 정렬을 시작한다.

 

  실제로 위 3개의 방법 중 2번째 개선 알고리즘이 가장 효율적이다.

 

• 단순 선택 정렬

 단순 선택 정렬에서의 교환은 아직 정렬하지 않은 부분에서 가장 작은 값을 선택하고 그 값과 맨 앞의 값을 바꿔주는 것이다. 그리고 이 과정을 반복하여 전체를 정렬하는 것이 단순 선택 정렬 알고리즘이다. 이 방법은 서로 떨어져 있는 요소를 교환하는 방법으로 알고리즘이 안정적이진 않다. 내용은 어려울게 없으니 코드를 보자.

static void select(int[] a, int n){
    for(int i = 0; i < n-1; i++){
        int min = i ;
        for(int j = i; j < n; j++)
            if(a[j]<a[min])
                min = j;
        swap(a,i,min);
    }
}

 배열의 맨 앞의 index를 i라 하고, 배열의 최솟값의 index를 min에 저장하여 a[i]와 a[min]의 값을 교환해 주는 내용의 코드이다. 내부 for문을 통해 정렬이 안된 배열의 전체를 순서대로 비교해 최솟값의 index를 찾아 min에 저장한다. 그리고 이를 swap메서드를 통해 a[i]와 a[min]을 교환을 해준다. 이 2개의 과정을 n-1번 반복하면 된다. 

 

• 단순 삽입 정렬

 단순 삽입 정렬은 크기가 n인 배열 a의 index가 1인값부터 n-1인값까지 순서대로, 정렬시킨 배열의 알맞은 부분에 삽입하는 알고리즘이다. 우선 index = 0인 값은 그냥 놔두고 index = 1인값을 정렬된 부분인 index = 0인 값과 비교하여 알맞은 곳에 삽입한다. index = 2인값도 앞에 정렬된 index = 0 ~ 1인 부분의 알맞은 곳에 삽입하고 이 과정을 index = n-1까지 하면 된다. 예를 들면 다음과 같다.

a = { 6, 4, 1, 7, 3, 9, 8 }일때 단순 삽입 정렬 과정

 

index = 1의 값 삽입   a = { 4, 6, 1, 7, 3, 9, 8 }

index = 2의 값 삽입   a = { 1, 4, 6, 7, 3, 9, 8 } 

... 

index = 5의 값 삽입   a = { 1, 3, 4, 6, 7, 9, 8 } 

index = 6의 값 삽입   a = { 1, 4, 6, 7, 3, 8, 9 } 

 

이제 단순 삽입 정렬이 진행되는 과정은 이해했지만 과연 삽입을 어떻게 할지 생각해봐야 한다. 삽입을 하는 메서드가 따로 없기 때문이다. 그러면 삽입하는 기능을 우리가 한번 구현해보자. 가령 a[i]의 값을 앞의 정렬된 부분에 삽입하려고 하면 a[i-1]부터 a[0]까지 순서대로 a[i]와 비교해 a[i]보다 작은 값 뒤에 삽입해야 한다. 따라서 a[i-1]부터 순서대로 a[i]와 비교해 a[i]보다 큰 값은 index값을 +1해 한칸씩 뒤로 밀고, a[i]보다 작은 값을 만나면 큰 값을 뒤로 미뤄 생긴 비어있는 자리에 a[i]를 삽입하는 방법을 구현해야한다. 근데 이때 혹시 a[i]가 본인보다 작은 값을 만나지 못하면 a[i]는 a[0]에 삽입하고 반복은 종료되어야한다. 예시를 보자.

 

a = { 6, 4, 1, 7, 3, 9, 8 }일때 삽입 구현

 

index = 1의 값 삽입

a = { 6, 6, 1, 7, 3, 9, 8 }

a = { 4, 6, 1, 7, 3, 9, 8 }

(a[0]까지 작은 값을 못 찾았으므로 a[0]에 삽입)

 

index = 2의 값 삽입

a = { 4, 6, 6, 7, 3, 9, 8 }

a = { 4, 4, 6, 7, 3, 9, 8 }

a = { 1, 4, 6, 7, 3, 9, 8 }

(a[0]까지 작은 값을 못 찾았으므로 a[0]에 삽입)

... 

index = 5의 값 삽입

a = { 1, 3, 4, 6, 7, 9, 8 } 

(a[4]가 작은 값이므로 원래 자리에 삽입)

 

index = 6의 값 삽입

a = { 1, 4, 6, 7, 3, 9, 9 }

a = { 1, 4, 6, 7, 3, 8, 9 }

(a[4]가 a[6]보다 작으므로 a[5]에 삽입)

 

그러면 코드로 작성해 보자.

static void insert(int[] a, int n){
    for(int i = 0; i < n; i++){
        int tmp = a[i];
        for(int j = i; j >=0; j--){
            if(j==0){        // 작은 값을 못 찾은 경우 a[0]에 a[i]삽입 후 break
                a[j]=tmp;
                break;}
            else if(tmp >= a[j-1]){ // a[i]>=a[j-1]인 경우 a[j]에 a[i] 삽입 후 break
                a[j] = tmp;
                break;
            }else{ a[j] = a[j-1]; } // a[i]<a[j-1]인 경우 a[j-1]을 a[j]로 미루기
        }
    }
}

 tmp 에 a[i]값을 저장해놓고 j를 i ~ 0까지 내부 for문을 반복한다. a[i]가 a[j-1]보다 크거나 작으면 자리를 찾았으니 a[j]에 a[i] 값인 tmp를 삽입하고 반복문을 탈출한다. 만약 a[i]가 a[j-1]보다 작으면 a[j-1]의 값을 a[j]로 미루고 다음 반복문을 진행한다. 만약 j = 0이 될때까지 tmp보다 작은 값을 찾지 못했다면 tmp를 a[0]에 삽입하고 반복문을 탈출한다.

 단순 삽입 정렬은 보시다시피 서로 떨어져 있는 요소들을 교환하는 것이 아니므로 안정된 알고리즘이라 할 수 있다.

 

• 단순 정렬 알고리즘

 지금까지 살펴본 단순 교환 정렬(버블 정렬), 단순 선택 정렬, 단순 삽입 정렬은 단순 정렬 알고리즘으로 묶을 수 있고 이들의 시간 복잡도는 모두 O(n^2)이다. 단순 정렬 알고리즘들은 시간 복잡도가 커서  효율적이지 못하다. 사람들은 이 알고리즘을 개선한 더 효율적인 알고리즘을 만들기 시작했고 다음엔 그러한 알고리즘들에 대해 공부해 보자.