4. 버블 정렬

출처: http://bitly.kr/9OkkSvw

---

버블 정렬(bubble sort) 알고리즘

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
선택 정렬과 기본 개념이 비슷하다.

---

버블 정렬(bubble sort) 알고리즘의 구체적인 개념

버블 정렬은 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, 

… 이런 식으로 (n-1)번째 자료와 마지막 원소와 비교하여 교환하면서 원소를 정렬한다.
1 싸이클을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2싸이클에서는 맨 뒤에 있는 큰 값은 정렬에서 제외되고, 2싸이클을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다.

이렇게 정렬을 1싸이클 수행할 때마다 정렬에서 제외되는 값이 하나씩 늘어난다.

---

출처: http://bitly.kr /q8LfgkF

버블 정렬을 실행했을 때 나오는 그림.

1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가

이번에는 n-2번째와 n-1번째까지, ...해서 최대  번 정렬한다. 

한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 거품 정렬이다.

https://youtu.be/lyZQPjUT5B4

이해를 위한 동영상(배속해서 보면 좋다.)

---

버블 정렬은 거의 모든 상황에서 최악의 성능을 보여준다.

단, 이미 정렬된 자료에서, 1번만 돌면 되기 때문에 최선의 성능을 보여준다.

이해하기 쉽고 코드가 짧은 덕에 각종 교습서에서 정렬 알고리즘의 예시로 많이 보여준다.

하지만. 실제 개발에서는 전혀 쓰이지 않는다고 봐도 무방하다.

https://youtu.be/k4RRi_ntQc8

버블 소트는 피해야 한다.

버블정렬과 같은 짜리 알고리즘은 데이터량에 비례해서 수행시간이 제곱으로 성장한다.

즉 1억 개의 데이터를 정렬한다고 치면 퀵정렬보다 무려 약 =천만 배 느리다.

---

예제 C 코드

# include <stdio.h>
# define MAX_SIZE 5

void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {7, 4, 5, 1, 3};

  // 버블 정렬 수행
  bubble_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

 

 

위 코드 구현시 결과와 진행.

1 싸이클

첫 번째 원소 7을 두 번째 원소 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다.

이 과정에서 원소를 네 번 비교한다.

가장 큰 원소가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 원소는 비교할 필요가 없다.

2 싸이클

첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 

세 번째의 5와 네 번째의 3을 비교하여 교환한다. 

이 과정에서 원소를 세 번 비교한다. 

비교한 원소 중 가장 큰 원소가 끝에서 두 번째에 놓인다.

3 싸이클
첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 

이 과정에서 원소를 두 번 비교한다. 

비교한 자료 중 가장 큰 원소가 끝에서 세 번째에 놓인다.

4 싸이클
첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

---

자료 참조

버블 정렬 - 나무위키

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#fn-1

정렬 알고리즘 - 나무위키

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

https://jongmin92.github.io/2017/11/06/Algorithm/Concept/basic-sort/

92Hz | Jongmin's Blog

---

추가...

버블 정렬 파이썬 구현

# Bubble Sort

a = [3, 2, 4, 1]

for i in range(len(a)):
  for j in range(len(a)-1-i):
    if a[j] > a[j+1]:
      a[j], a[j+1] = a[j+1], a[j]
    print(a)

print(a)

결과

출력 과정 + 결과

---

버블 정렬 with 재귀함수 파이썬 구현

# Bubble Sort with Recurrence

def bubble_sort(n = 0, i = 0):
  global a
  print(a)
  if i == len(a)-1:
    return
  else:
    if n < len(a)-1:
      if a[n] > a[n+1]:
        a[n], a[n+1] = a[n+1], a[n]
        
      bubble_sort(n+1, i)
    else:
      bubble_sort(0, i+1)
  

a = [3, 1, 2]

bubble_sort()

print(a)

출력 과정 및 결과