📌 버블 정렬

• 2개의 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘이다.

---

📌 버블 정렬 구현하기

버블 정렬의 특이점 파악하기

• N개의 원소가 있는 경우 정렬은 N-1턴 일어난다.
• 정렬이 1턴 일어날 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
• 따라서 정렬이 1턴 일어날 때 해당 턴 안에서 swap은 N-1-(정렬된 턴 수) 번 실행된다.
• 만약 정렬을 한 턴 실행했는데 swap이 한번도 일어나지 않은 경우, 이미 완전하게 정렬된 상태이므로 더 이상 정렬을 반복할 필요가 없다. 따라서 경우에 따라 로직이 일찍 끝날 수도 있다.

대략적 코드

changed = False #swap이 일어났는지 검사하는 변수
for index1 in range(데이터 길이 - 1):
    for index2 in range(데이터길이 - 1 - index1):
    if list[index2] > list[index2 + 1]:
        swap(list[index2], list[index2 + 1])
        changed = True
    if not changed: # 해당 턴에 한번도 swap이 일어나지 않으면 이미 정렬이 완료된 상태임
        break

---

✅ Code

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data	

---

📌 버블 정렬 시간복잡도

• 반복문이 두 개이므로 $O(n^2)$

• 최악의 경우, $\frac { n * (n - 1)}{ 2 }$

• 완전 정렬이 되어 있는 상태라면 최선은 $O(n)$