버블 정렬 (Bubble sort)

알고리즘 연습 방법

1. 연습장과 펜을 준비하자.
2. 알고리즘 문제를 읽고 분석한 후에,
3. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다.
4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고,
6. 각 문장을 코드 레벨로 적는다.
7. 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지를 손으로 적으면서, 임의 데이터로 코드가 정상 동작하는지를 연습장과 펜으로 검증한다.

---

1. 정렬 (sorting) 이란?

• 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 정렬은 프로그램 작성시 빈번하게 필요로 함
• 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

 

다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음

 

---

2. 버블 정렬 (bubble sort) 이란?

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
• 반복해서 두개씩 앞뒤로 계속 비교하고 바꿔준다.

 

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

 

데이터 길이가 2일 때는 1번 비교

데이터 길이가 3일 때는 4번 비교

데이터 길이가 4일 때는 9번 비교

 

패턴 :

for i in range(데이터길이 -1):
    for j in range(데이터길이 -1):
        if 앞데이터 < 뒤데이터:
            swap(앞데이터, 뒤데이터)

---

 

사실 맨 뒤에건 체크를 안해도 된다.

for i in range(데이터길이 -1):
    for j in range(데이터길이 -i -1):
        if 앞데이터 < 뒤데이터:
            swap(앞데이터, 뒤데이터)

---

 

만약 이미 정렬된 데이터라면?

한번 돌렸을 때 swap이 한번도 안 일어날 것이다.

그러면 그 다음부터 실행할 필요도 없어진다.

 

def bubblesort(data):
    for i in range(len(data) -1):
        swap = False # 텀이 실행 될때마다 swap은 초기화 된다.
        for j in range(len(data) -i -1):
            if data[j] < data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                swap = True 
        
        if swap == False: # swap이 한번도 안 일어난다면 비교할 필요없다.
            break

 

import random

data_list = random.sample(range(100), 50)
print (bubblesort(data_list))

> 0, 1, 2, 3, 6, 7, 10, 11, 12, ...

---

3. 알고리즘 분석

반복문이 두 개 : O(𝑛^2)

• 최악의 경우, 𝑛∗(𝑛−1)/2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)