버블 정렬 알고리즘 최적화

복습을 목적으로 시작한 벨로그지만 깊이있게 글을 쓰려다 보니

이론을 학습하고 구현하며 실습하는 시간보다 글을 쓰는데에 더 노력하는 내 자신을 발견하게 되었다.

그러하여 이제부터는 간단한 이론과 함께 내가 실습중에 작성한 코드를 첨부하고 구현 중에 어려웠던 부분을 작성하며 실습에 더 집중하도록 하겠다.

대신에 코드를 구현할 때 한 눈에 보기쉬운 결과가 도출되도록 할 것이다.

이번 코드에서는 버블 정렬에서 요소가 어떻게 이동하는지도 보여지도록 printArray 함수를 만들어 잘 활용하였다.

버블 정렬(bubble sort)

버블 정렬은 앞선 글에서 다룬 적이 있다.
빅오(O) 표기법과 버블 정렬

앞의 글을 인용하자면

버블 정렬이란 인접한 두 원소를 비교하여 순서대로 정렬하는 방식이다.

쉽게 말해 위의 자료처럼 옆에 있는 자료보다 크면 위치를 바꾸고 작으면 냅두고 이 과정을 반복하여 자료를 정렬할 수 있다.

이 알고리즘은 이름 그대로 큰 값이 "올라가는(bubble up)" 것과 같은 원리로 동작한다.

아래 코드의 결과를 보면 이해가 될 것이다.

#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

void printArray(int a[], n){
  printf("{");
  for(int i=0; i<n-1; i++){
    printf("%d, ", a[i]);
  }
  printf("%d}\n", a[n-1]);
  puts("-------------------------------------");
}

void bubble(int a[], int n){
  for(int i=0; i<n-1; i++){
    for(int j=n-1; j>i; j--){
      if(a[j-1]>a[j]){ 
        printf("x[%d] : %d 와 x[%d] : %d 값의 위치를 변경\n\n", j-1, a[j-1], j, a[j]);
        swap(int, a[j-1], a[j]);
        printArray(a, n);
      } 
    }
  }
  printf("버블 정렬 완료 : ");
}

int main(void){
  int nx;

  puts("버블 정렬");
  printf("요소 개수: ");
  scanf("%d", &nx);
  int *x = calloc(nx, sizeof(int));

  for(int i=0; i<nx; i++){
    printf("x[%d] : ", i);
    scanf("%d", &x[i]);
  }
  printf("\n저장된 배열 : ");
  printArray(x, nx);

  bubble(x, nx);
  printArray(x, nx);

  free(x);

  return 0;
}


----------------------------------------------------
결과

버블 정렬
요소 개수: 5
x[0] : 5
x[1] : 4
x[2] : 3
x[3] : 2
x[4] : 1

저장된 배열 : {5, 4, 3, 2, 1}
-------------------------------------
x[3] : 2 와 x[4] : 1 값의 위치를 변경

{5, 4, 3, 1, 2}
-------------------------------------
x[2] : 3 와 x[3] : 1 값의 위치를 변경

{5, 4, 1, 3, 2}
-------------------------------------
x[1] : 4 와 x[2] : 1 값의 위치를 변경

{5, 1, 4, 3, 2}
-------------------------------------
x[0] : 5 와 x[1] : 1 값의 위치를 변경

{1, 5, 4, 3, 2}
-------------------------------------
x[3] : 3 와 x[4] : 2 값의 위치를 변경

{1, 5, 4, 2, 3}
-------------------------------------
x[2] : 4 와 x[3] : 2 값의 위치를 변경

{1, 5, 2, 4, 3}
-------------------------------------
x[1] : 5 와 x[2] : 2 값의 위치를 변경

{1, 2, 5, 4, 3}
-------------------------------------
x[3] : 4 와 x[4] : 3 값의 위치를 변경

{1, 2, 5, 3, 4}
-------------------------------------
x[2] : 5 와 x[3] : 3 값의 위치를 변경

{1, 2, 3, 5, 4}
-------------------------------------
x[3] : 5 와 x[4] : 4 값의 위치를 변경

{1, 2, 3, 4, 5}
-------------------------------------
버블 정렬 완료 : {1, 2, 3, 4, 5}
-------------------------------------

버블 정렬을 구현하는 함수에서 j>i의 의미만 잘 이해하면 크게 어려울 것이 없다.

for(int i=0; i<n-1; i++){
  for(int j=n-1; j>i; j--){...}
}

버블 정렬을 한 번 수행하고 나면 배열의 맨 앞에는 최솟값(오름차순)이 위치하기 때문에 더 이상 교체 작업이 필요하지 않다.

그러므로 j값이 i보다 큰 동안만 반복하면 버블 정렬을 완료할 수 있다.

효율성이 떨어지는 버블 정렬

버블 정렬은 인접한 두 원소를 비교하고, 만약 순서가 잘못되어 있다면 서로 교환하는 작업을 반복한다. 이때 전체 리스트를 훑어나가면서 가장 큰 원소가 마지막으로 이동하게 되므로, 총 N개의 원소가 있는 리스트에 대해 N-1번의 반복이 필요하다.

그리고 반복을 할 수록 전체 개수가 하나씩 줄기 때문에 전체 알고리즘의 비교 횟수는 대략적으로 (N-1) + (N-2) + ... + 1이 된다.

이는 등차수열의 합으로 나타내면 N(N-1)/2로 표현할 수 있다.

따라서 전체 비교 횟수는 약 N^2/2에 해당하며, 앞서 설명하였듯이 빅 오 표기법에서는 상수항을 무시하므로 O(N^2)의 시간 복잡도를 가진다고 말할 수 있다.

이렇듯 비효율적이어서 대부분의 실무에서는 다른 정렬 알고리즘을 사용한다.

하지만 이렇게 비효율적인 버블 정렬을 조금이나마 최적화 시킬 수는 없을까 ?

버블 정렬의 개선

{1, 2, 3, 7, 4}

위 배열을 기준으로 버블 정렬의 알고리즘이 실행되는 과정에서 이미 정렬되어있는 숫자들(1, 2, 3)이 있다면 실제론 비교를 할 필요가 없다.

하지만 이를 모르는 컴퓨터는 입력된 값대로 모든 경우를 비교해보게 되고 비교할 필요가 없음에도 다음 반복에서도 똑같이 반복하여 비교하게 된다.

즉 요소의 순서에 상관없이 배열의 길이가 같다면 결국엔 똑같은 횟수의 비교연산을 거치게 된다.

교환 횟수를 저장해놓기

반복문이 진행되는 과정속에서 교환 횟수를 저장해놓는 방법이다.

컴퓨터 입장에서 이미 정렬되어있는 요소들이 앞에 있고 이를 한 번 겪는다면, 다음부턴 무시하도록 하는 학습 능력을 갖추게 하는거라고 생각할 수 있겠다.

void bubble(int a[], int n, int *count){
  for(int i=0; i<n-1; i++){
    int flag = 0;
    for(int j=n-1; j>i; j--){
      (*count)++;
      if(a[j-1]>a[j]){ 
        printf("x[%d] : %d 와 x[%d] : %d 값의 위치를 변경\n\n", j-1, a[j-1], j, a[j]);
        swap(int, a[j-1], a[j]);
        printArray(a, n);
        flag++;
      }
    }
    if(flag == 0) break;
  }
  printf("버블 정렬 완료 : ");
  printArray(a, n);
  printf("비교 횟수 : %d ", *count);
}

flag 변수에 swap를 반복한 횟수를 기록해 이미 정렬되어있는 부분을 거쳤으나 swap를 진행하지 않았음을 기억해

다음 반복부터는 앞 부분을 비교하지 않는 것이다.

개선 전

버블 정렬
요소 개수: 5
x[0] : 1
x[1] : 2
x[2] : 3
x[3] : 7
x[4] : 4

저장된 배열 : {1, 2, 3, 7, 4}
-------------------------------------
x[3] : 7 와 x[4] : 4 값의 위치를 변경

{1, 2, 3, 4, 7}
-------------------------------------
버블 정렬 완료 : {1, 2, 3, 4, 7}
-------------------------------------
비교 횟수 : 10 

개선 후

버블 정렬
요소 개수: 5
x[0] : 1
x[1] : 2
x[2] : 3
x[3] : 7
x[4] : 4

저장된 배열 : {1, 2, 3, 7, 4}
-------------------------------------
x[3] : 7 와 x[4] : 4 값의 위치를 변경

{1, 2, 3, 4, 7}
-------------------------------------
버블 정렬 완료 : {1, 2, 3, 4, 7}
-------------------------------------
비교 횟수 : 7 

마지막으로 교환을 수행한 위치를 저장하기

교환을 수행한 위치를 저장하며 버블 정렬을 하는 방법이다.

위에서 다룬 개선방법이랑 같아 보이지만 비교횟수가 줄어든 모습을 볼 수 있다.

void bubble(int a[], int n, int *count){
  int k = 0; //a[k]보다 앞쪽의 요소는 정렬을 마침
  while(k<n-1){
    int last = n-1; //마지막으로 교환을 수행한 위치를 저장
    for(int j=n-1; j>k; j--){
      (*count)++;
      if(a[j-1]>a[j]){
        printf("x[%d] : %d 와 x[%d] : %d 값의 위치를 변경\n\n", j-1, a[j-1], j, a[j]);
        swap(int, a[j-1], a[j]);
        printArray(a, n);
        last = j;
      }
    }
    k = last;
  }
  printf("버블 정렬 완료 : ");
  printArray(a, n);
  printf("비교 횟수 : %d ", *count);
}
------------------------------------------------
결과

버블 정렬
요소 개수: 5
x[0] : 1
x[1] : 2
x[2] : 3
x[3] : 7
x[4] : 4

저장된 배열 : {1, 2, 3, 7, 4}
-------------------------------------
x[3] : 7 와 x[4] : 4 값의 위치를 변경

{1, 2, 3, 4, 7}
-------------------------------------
버블 정렬 완료 : {1, 2, 3, 4, 7}
-------------------------------------
비교 횟수 : 4 

last 변수를 사용하여 마지막으로 교환한 위치를 저장하고, 다음 루프에서는 그 위치까지만 비교를 수행한다.

반면에 처음 개선한 알고리즘에서는 flag를 사용하고 있지만, flag가 항상 0으로 유지되기 때문에 조건에 달하더라도 루프에서 바로 빠져나가지 않고 모든 비교를 수행하고나서 조건이 맞을시 반복문을 탈출하게 된다.

그래서 두 함수 간에 비교 횟수 차이가 나게 된다.

아무래도 for문의 종료조건과 while문의 종료조건을 사용하는 타이밍 차이라고 이해하면 될 것 같다.

이제 당분간 휴가여서 글을 안 올리고 휴가가 끝난 후에 단순 선택 정렬부터 여러 정렬들을 다뤄보고서 문자열 검색으로 넘어가겠다.