[누구나 자료구조 알고리즘] Python 버블정렬

💡 Goal
- 버블정렬 알고리즘을 이해하기.
- 버블정렬 알고리즘을 파이썬으로 구현하기.
- 버블정렬 알고리즘 특징을 2가지 이상 말하기.

개념

---

• 서로 인접한(연속된) 두 원소를 확인해 정렬하는 알고리즘
  • 인접한 2개의 원소를 확인하여 조건에 맞는 순서로 교환
• 비교와 교환으로 이루어진 알고리즘

순서(오름차순 기준)

---

1. 연속된 두 항목을 가리킨 후 비교한다.
2. 두 항목의 값의 크기가 뒤바뀌어 있으면 값을 교환한다.
3. 비교 포인터를 오른쪽 한칸씩 이동한다.
4. 배열의 끝까지 또는 정렬된 항목까지 1~2단계를 반복한다.

특징

---

장점

• 구현이 간단하다

단점

• 순차적으로 확인하기 때문에 크기에 맞지 않는 비교가 일어남
• 순차적으로 확인하기 때문에 N개의 길이가 있다면 N번 교환이 발생

코드

---

def bubble_sort(input_list):
    unsorted_until_index = len(input_list) - 1 
    is_sorted = False

    while not is_sorted:
        is_sorted = True
        for i in range(unsorted_until_index):  
            if input_list[i] > input_list[i + 1]:  
                is_sorted = False
                input_list[i], input_list[i + 1] = input_list[i + 1], input_list[i]
        unsorted_until_index = unsorted_until_index - 1 
    return input_list

# 내가 직접 작성한 코드
def buble_sort(input_list):
    unsorted_until_idx = len(input_list) - 1
    is_sorted = False

    while not is_sorted:
        is_sorted = True
        for i in range(unsorted_until_idx):
            if input_list[i] > input_list[i + 1]:
                temp = input_list[i]
                input_list[i] = input_list[i + 1]
                input_list[i + 1] = temp
                is_sorted = False
    return input_list

시간복잡도

주어진 데이터의 원소 길이가 5일때 두수의 비교를 순차적으로 끝까지 하게 되면 총 4번의 횟수가 발생한다.

이때 끝까지 비교를 하면 4+3+2+1 = 10번이 발생한다. (n-1) + (n-2) ... + 1

교환도 마찬가지로 비교와 동일하게 10번이 발생하게 된다.

비교와 교환의 두 횟수를 최악의 상황에서 더하게 되면 20단계라고 볼 수 있다.

데이터 원소 N개	최대 단계수	N2
5	20	25
10	90	100
20	380	400
40	1560	1600
80	6320	6400