[python]버블 정렬

버블 정렬(Bubble sort)이란?

---

버블 정렬이란, 두 인접한 원소를 검사하여 정렬하는 방법이다. 거품 정렬이라고도 불리며 원소의 이동하는 모습이 거품이 수면으로 올라오는 듯한 것처럼 보이기 때문에 지어진 이름이다.

버블정렬의 특징

---

장점

• 구현이 간단하다.

단점

• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 다른 요소들과 교환해야하는 필요 이상의 교환이 생긴다

 

시간 복잡도

---

시간 복잡도가 O(n²)로 상당히 느린편이지만 코드가 단순하기 때문에 자주 사용된다.

 

코드

---

#버블 정렬
#리스트 a를 버블 정렬로 정렬함
def bubble_sort(a):
    n = len(a)
    for i in range(0,n-1):
        for j in range(n-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a
a = [7,3,20,5,12,1]
print(bubble_sort(a))

[7, 3, 20, 5, 12, 1] 7과 3을 비교한다
[3, 7, 20, 5, 12, 1] 7이 더 크므로 둘을 교환한다
[3, 7, 5, 20, 12, 1] 20과 5를 비교해서 20이 더 크므로 교환한다
[3, 7, 5, 12, 20, 1] 20과 12를 비교해서 20이 더 크므로 교환한다
[3, 7, 5, 12, 1, 20] 20과 1을 비교해서 20이 더 크므로 교환한다
[3, 5, 7, 12, 1, 20] 7과 5를 비교해서 7이 더 크므로 교환한다
[3, 5, 7, 1, 12, 20] 12와 1을 비교해서 12가 더 크므로 교환한다
[3, 5, 1, 7, 12, 20] 7과 1을 비교해서 7이 더 크므로 교환한다
[3, 1, 5, 7, 12, 20] 5와 1을 비교해서 5가 더 크므로 교환한다
[1, 3, 5, 7, 12, 20] 3과 1을 비교해서 3이 더 크므로 교환한다