bubble sort(optimized)

최적화된 버블 소트 코드

 

def bubble_sort(a):  # optimized
    n = len(a)
    for j in range(n):  # 반복용
        checked = False
        for i in range(0, n - 1):  # 처음부터 끝까지 앞뒤 비교하며 자리 바꾸기
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                checked = True
 
        if checked is False:  # 모두 정렬되었으면 그냥 종료
            break

 

버블 소트는 배열 처음부터 끝까지 앞뒤하고만 비교하며 정렬한다.

정렬된 경우는 swap이 일어나지 않기 때문에 bool로 체크해서 그 경우에는 정렬을 종료한다.

 

(평균)시간복잡도: O(n^2)

(최선)시간복잡도: O(n)