Algorithm - 버블 정렬(Bubble Sort)

0. 알고리즘 연습 방법

- 연습장과 펜을 준비한다.

- 알고리즘 문제를 읽고 분석 후 문제를 풀기 위한 순서를 생각한다.

- 각 순서 또는 절차마다 구현할 알고리즘을 나누고 세부 항목을 나누어 적어본다.

- 코드로 구현하기 위해 필요한 데이터 구조 또는 사용할 변수를 정리한다. 

- 각 문장을 코드 레벨로 적는다. 

- 코드의 흐름을 데이터 구조 또는 사용할 변수를 이용해 손으로 직접 적으면서 작동한다.

 

즉, 코드에 필요한 모든 순서/절차/흐름을 연습장에서 정리를 한 후 코드로 옮기기만 하는 것이다. 

---

1. 정렬(Sort) 이란?

- 데이터를 순서대로 나열하는 것 또는 어떤 규칙이나 기준을 기반으로 나열하는 것

 

a) 정렬을 알아야 하는 이유

- 정렬은 프로그램 작성 시 빈번하게 사용되는 가장 기본적인 알고리즘의 형태이다.

- 다양한 정렬 알고리즘의 이해를 통해 동일한 문제도 다양한 정렬 알고리즘으로 풀이된다는 것을 배우게 된다.

- 문제에 따른 정렬 방식의 차이가 알고리즘의 성능 차이를 만들며, 알고리즘 성능 분석에 대해서도 이해할 수 있다.

---

2. 버블 정렬(Bubble Sort) 

- 인접한 두 데이터의 크기를 비교해서 재정렬 하는 알고리즘이다. (아래 사진참고)

https://en.wikipedia.org/wiki/Bubble_sort

 

 

 

2-A) 어떻게 코드로 구현할까?

- 버블 정렬을 공책에 정리해본다.

- 규칙성을 찾는다. 

- 규칙성을 공식으로 만든다. 

- 코드로 작성한다. 

 

 

2-B) 버블 정렬의 규칙성

- n개의 데이터가 있는 경우, 최대 n-1번의 로직을 반복수행한다. 

- 로직을 1번 적용할 때마다 가장 큰 숫자가 맨 뒤에서부터 1개씩 결정된다. 

- 데이터가 기존에 어떻게 정렬되어 있는가에 따라 일찍 끝날 수도 있다. 왜냐면 이미 정렬된 순서를 갖고 있을 수 있기 때문이다.

 

 

2-C) 버블 정렬의 규칙성 - 코드구현

1) 버블 정렬의 코드 구현 - 최대 n-1번 로직을 반복수행 한다.

for index in range(자료구조의 길이 - 1):
    for index2 in range(자료구조의 길이 - 1):
        if 현재 데이터 > 다음 데이터:
            swap(현재 데이터, 다음 데이터)

*여기서 swap은 데이터의 순서를 바꾸는 것을 의미한다. 

 

 

 

2) 버블 정렬의 코드 구현 - 가장 큰 숫자가 맨 뒤에서부터 1개씩 결정된다.

- 마지막에 위치한 데이터까지 로직을 다시 적용할 필요가 없어진다. 이미 정렬되어있기 때문이다.

for index in range(자료구조의 길이 - 1):
    for index2 in range(자료구조의 길이 - index - 1):
        if 현재 데이터 > 다음 데이터:
            swap(현재 데이터, 다음 데이터)

*내부 for문에서 반복 횟수가 배열/리스트의 길이 - index - 1회로 수정된다.

 

 

 

3) 버블 정렬의 코드 구현 - 이미 또는 어느정도 정렬된 순서를 갖고 있다면

- 저장된 데이터가 이미 정렬된 순서를 갖고 있다면 로직을 적용할 필요가 없다.

- 또는 저장된 데이터가 어느정도(부분적으로) 정렬된 순서를 갖고 있다면 로직을 적용하는 횟수는 적어질 것이다.  

- 그렇다면 어떻게 이를 판단할 수 있을까?

 

→ 첫번째 로직을 적용할 때, swap이 한번도 일어나지 않았다면 이미 정렬된 구조를 갖고있는 것이다.

for index in range(자료구조의 길이 - 1):
    for index2 in range(자료구조의 길이 - index - 1):
        if 현재 데이터 > 다음 데이터:
            swap(현재 데이터, 다음 데이터
            swap_count += 1
    if swap == 0:
    	break

 

 

2-D) 버블정렬 코드구현

[구현 내용]

a) for num in range(len(data_list)) 반복

b) swap = 0 (교환이 되었는지를 확인하는 변수를 두자)

c) 반복문 안에서, for index in range(len(data_list) - num - 1) n - 1번 반복해야 하므로

d) 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면

e) data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]

f) swap += 1

g) 반복문 안에서, if swap == 0 이면, break 끝

 

def bubble_sort(data):
    swap_count = 0
    
    for index in range(len(data) - 1):

        for index2 in range(len(data) - 1):
            
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap_count += 1
                
        if swap_count == 0:
            break
            
    return data           

 

 

[테스트 및 결과]

---

3. 버블정렬의 시간복잡도

• n = 데이터를 담고있는 자료구조의 길이
• 첫번째 for문과 두번째 for문 모두 n번 반복 → n의 제곱승

- 그러므로 버블정렬의 시간 복잡도는 O(n^2)이다.

- 최악의 경우, {n x (n-1)} / 2의 시간복잡도를 갖는다. 

- 만약,  데이터가 이미 완전 정렬된 상태라면 O(n)의 시간복잡도를 갖는다.