[Algorithm] 버블 정렬 (Bubble Sort)

 

 

버블 정렬 (Bubble Sort)

버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘.

 

• 버블 정렬하면 배열의 뒤에서부터 정렬된다.
• 배열의 첫 번째 요소부터 n번째 요소까지 오름차순으로 버블 정렬을 수행하면 해당 범위의 최댓값이 n번째에 위치하게 된다.

 

 

배열의 n번째 요소를 정렬하는데 n-1번을 비교하므로 배열의 모든 요소를 정렬하려면 (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2 만큼 연산을 수행한다.

 

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

 

 

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