[Python]Bubble Sorting

버블정렬은 거품이 올라오는 모양처럼 정렬한다고 해서 붙여진 이름이다.

 

장점은 구현하기 가장 간단하다는 특징을 가지고 있다

단점은 성능이 좋진 않다는 것. 평균 시간 복잡도 O(N^2)

 

정리

• 인접한 값과 비교 후 교환
• 스와핑 위한 공간 1개 필요
• 총 n-1번 루핑

def bubble_sort(arr):
    for _ in range(len(arr)-1):
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr