[알고리즘] 버블 정렬 (bubble sort) 쉽게 이해하기

현재 중앙대학교 컴퓨터예술학부 재학중

들어가기 전) 정렬 개념정리

정렬은 기본적으로 배열과 같은 데이터 구조를 가진다

배열은 순서가 있고 첨자(index)가 있다.

이 첨자를 통해서 각각의 데이터 원소에 접근하게 되고 

그 데이터 원소를 키(key)로 여기고 정렬하게 된다.

• 첨자(index)가 어떻게 변하는지

• 비교연산자(<,>,≤,≥)는 무엇을 써야할지

정렬 알고리즘에선 위 두가지를 세세하게 살펴보아야 한다.

오름차순 정렬을 원칙을 한다.

01_왜 버블 정렬인가?

거품은 수면위로 떠오르는 특성을 지닌다.

한국말로는 거품이라는 말에서 알 수 있듯이

데이터 원소들이 수면으로 올라오는 것처럼 ^[각주:1]

동작하는 것이 바로 버블 정렬 알고리즘이다.

02_동작방식 쉽게 이해하기

(1) Step by Step

.gif

선택 > 비교 > 바꾸기 > 부분 정렬 > 정렬 완료

버블 정렬의 구현은 오직 2가지의 개념만 이해하면 되는데 바로 '선택'과 '비교'이다. 

아래는 [9,3,4,2,8] 배열을 오름차순으로 버블 정렬를 주기별로 정리한 것이다.

앞에서부터 두 개의 숫자를 비교 및 교환하였다.

4번의 교환이 이루어졌다.

이번 주기를 통해 8, 9는 완벽히 정렬되었다.

1번의 교환이 이루어졌다.

이번 주기를 통해 4,8,9은 완벽히 정렬되었다.

불필요한 정렬이 시행되었다.

0번의 교환이 이루어졌다.

이번 주기를 통해 2,3,4,8,9은 완벽히 정렬되었다.

불필요한 정렬이 시행되었다.

• 최악의 경우 총 4번의 주기가 필요하지만 3번의 주기만으로 정렬되었다. 

• 한 주기마다 최소 1개는 완벽히 정렬되었다.

• 위의 이유로 불필요한 정렬이 일어나게 되었다.

따라서 주기 별로 정렬이 한 번 덜 일어나게 할 필요가 있다.

02_동작방식 쉽게 이해하기

(2) 토너먼트

버블 정렬 알고리즘은 이웃한 두 데이터 원소에 대해

비교 및 교환을 반복하여 정렬하는 방식으로

순위가 가려질 때까지 "토너먼트"를 여러 번 치르는 것과 같다.

선수들의 피로도가 절대적인 토너먼트 경기방식이 있다고 가정해보자

경기에서 승리하기 위해서는 무조건 선수들의 피로도가 낮아야 한다.

6개의 조가 위 그림과 같이 한번의 토너먼트를 치르는 과정을 보면

5조와 6조가 처음 경기를 한 후 승리팀은 이후 4조와 경기를 한다.

4조와의 경기에서의 승리팀은 3조와 경기를 하며

3조와의 경기에서의 승리팀은 2조와 경기를 하고

2조와의 경기에서의 승리팀은 마지막으로 1조와 경기를 한다.

결과적으로 1위는 무조건 피로도가 가장 낮은 팀이 된다.

따라서 2~6조의 피로도를 비교하기 위해선 

앞으로 4번의 토너먼트를 더 치뤄야 하는 것을 알 수 있다.

-> n개의 조는 n-1번의 토너먼트를 치뤄야 한다.

1조의 경우)

1조는 1등이므로 이 경기는 피로도 2등이 누군지 알 수있는 경기가 될 것이다.

앞으로 3번의 토너먼트를 더 치뤄도 모든 조의 피로도 비교가 가능하다.

2~5조의 경우)

n조는 n-1번의 경기를 치뤄야 한다.

6조의 경우)

6조는 1등이 될 것이므로 모든 조와 한번씩 즉, 5번의 경기를 치뤄야 한다.

토너먼트 용어를 알고리즘 방식으로 치환시켜보면 

피로도는 데이터 원소를 의미한다.

경기는 데이터의 비교를 의미한다.

경기에서의 승리는 데이터의 교환을 의미한다.

02_동작방식 쉽게 이해하기

(3) 거꾸로 추적하기

항상 교환이 이루어지는 이상적인 배열을 가정하여

미리 결과를 인지한 후 거꾸로 추적하여 정렬을 시도해보자

내림차순 정렬이 된 배열을 버블 정렬할 때

데이터 원소 한 개의 위치를 반대로 추적하여

'교환'이 어떻게 이루어지는지 알아보자

(내림차순 배열임으로 '교환'은 항상 이루어진다.)

아래는 결과를 정리한 것이다.

1. 교환주기는 3회이다. (#1~#3)

2. 주기마다 교환이 1씩 덜 발생하였다. (3 > 2 > 1)

그럼 이제 데이터 원소 '7'을 추적해보자

결과적으로 7은 가장 오른쪽에 위치해야한다.

그러므로 7은 모든 교환주기마다 교환이 이루어져야 한다.

따라서 교환주기는 원소 이동이 가능한 최대 간격임을 알 수 있다.

주기마다 교환은 1씩 줄었다는 것은 

한 원소의 위치가 완전하여 교환이 이루어질 필요가 없음을 의미한다.

이는 교환주기를 한 번씩 실행할 때마다 

첫 번째 자료의 정렬은 완료된다는 것을 간접적으로 알 수있다.

03_버블 정렬 알고리즘의 특징

두 개의 데이터 원소를 첨자(index)로 지정해준 뒤 비교연산자로 비교하여 바꿔주면 된다.

• 간단한 구현으로 쉽고 빠르다

• but 시간 복잡성이 높다

아마 버블 정렬 만큼 구현하기 쉬운 정렬 알고리즘은 많이 없을 것이다.

시간 복잡성은 높다는 것을 간단하게 이야기하면 정렬 속도가 느리다는 것을 의미한다.

04_버블 정렬 알고리즘의 구현코드(Python)

arr=[6,4,3,7,1,8,9]
n=len(arr)

for i in range(1,n):
     for j in range(n-1,i,-1):
          if arr[j-1] > arr[j]:
               arr[j-1], arr[j]=arr[j], arr[j-1]

데이터의 크기가 7임으로

바깥 반복문에서 교환주기를 6번(데이터의 크기-1) 반복한다.

주기가 시작할 때마다 i값이 1씩 커진다.

따라서 안의 반복문에선 i값에 따라 교환이 한번씩 덜 이루어진다.

교환은 앞에 있는 값이 더 클 때 이루어진다.

 

개선의 필요성(1)

정렬이 완료된 것을 확인하면, 이후 패스를 진행하지 않기로 한다.

-> 정렬이 완료되면 이후 패스에서 교환이 한 번도 일어나지 않는다는 것을 이용해 확인한다.

arr=[6,4,3,7,1,8,9]
n=len(arr)

for i in range(1,n):
     for j in range(n-1,i,-1):
          if arr[j-1] > arr[j]:
               arr[j-1], arr[j]=arr[j], arr[j-1]

          if n_swap == 0:
	       break

개선의 필요성(2)

마지막으로 교환이 이루어진 이후로 이미 정렬이 완료되어있을 수도 있다.

패스의 진행을 완료한 이후 특정 지점 이후로 정렬이 완료된 것을 확인하면

해당 지점까지 정렬이 완료된 것으로 간주한다.

-> 특정 지점 이후로 정렬되어 있다면, 마지막 교환이 발생한 지점부터 교환이 한번도 일어나지 않는다.

arr=[6,4,3,7,1,8,9]
n=len(arr)

arr=[1,3,4,6,7,8,9]
n=len(arr)
k=0
while k<(n-1):
     print("Pass #%d" %(k+1))
     last = n-1
     for j in range(n-1, k, -1):
          if arr[j-1] > arr[j]:
               arr[j-1], arr[j]=arr[j], arr[j-1]
               last=j
          print(j, arr)
     print("The last swap index:", iast)
     k=last

05_버블 정렬 알고리즘의 시간 복잡성

>  시간 복잡성에 대해 궁금하다면 ? 바로가기

버블 정렬은 한 주기가 진행되며 n-1, n-2, …, 3, 2, 1 번의 비교가 이루어진다.

따라서 이를 전부 더하면 

따라서 버블 정렬의 평균 시간 복잡성은 이다.

최악의 경우 시간 복잡성은 이다.

가장 좋은 경우 버블 정렬의 시간 복잡성은 정렬이 이미 완료된 경우로 이다.

06_버블 정렬 응용하기

프로세싱으로 데이터 시각화하기

프로세싱이란 MIT 미디어랩에서 개발한 오프소스 툴중 하나로 

그래픽적인 요소를 쉽게 구현할 수 있다는 점에서 강점을 지니고 있다.

float[] values;

int i = 0;
int j = 0;

void setup() {
  fullScreen(P2D);
  //size(800, 300);
  values = new float[width];
  for (int i = 0; i < values.length; i++) {
    values[i] = random(height);
    //values[i] = noise(i/100.0)*height;
  }


  //for (int i = 0; i < values.length; i++) {
  //  }
  //}
}

void draw() {
  background(0);

  if (i < values.length) {
    for (int j = 0; j < values.length-i-1; j++) {
      float a = values[j];
      float b = values[j+1];
      if (a > b) {
        swap(values, j, j+1);
      }
    }
  } else {
    println("finished");
    noLoop();
  }
  i++;

  for (int i = 0; i < values.length; i++) {
    stroke(255);
    line(i, height, i, height - values[i]);
  }
}

void swap(float[] arr, int a, int b) {
  float temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

참조문헌

• "거품 정렬." (2020년 5월 3일). 위키피디아. 2020년 4월 17일 수정, https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC.

• "Bubble Sort Visualization." (2020년 5월 4일). coding-train. 2018년 8월 17일 수정, https://thecodingtrain.com/CodingChallenges/114-bubble-sort.html.

1. "수상-공기-방울-매크로-물-4905538",픽사베이,2020년 3월 20일 수정, 2020년 5월 3일 수정, https://pixabay.com/images/id-4905538/ [본문으로]