버블 정렬(Bubble Sort)

전개

1. 배열의 맨 앞에서부터 뒤로 이동하면서 이웃한 앞뒤 원소의 값을 서로 비교한다. 앞의 원소의 값이 더 크면 두 원소의 자리를 바꾼다.
2. 한 번 돌았으면 마지막 원소를 제외하고 나머지 원소들로 같은 과정을 반복한다.
3. 한 번도 자리가 교체되지 않았으면 원소가 순서대로 정렬되어 있으므로 정렬을 종료한다.

시간 복잡도

• O(${N^2}$)

구현 코드

def bubble_sort(numbers):
    """ 오름차순 버블 정렬을 실행합니다. """
    n = len(numbers) - 1

    swapped = False
    for i in range(n):
        for j in range(n - i):  # 인덱스 j와 j + 1의 값을 비교해주어야 하므로, n - i - 1이 end 값이 되게 한다.
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True

        if not swapped:
            break


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]

    bubble_sort(numbers)

    print(numbers)

'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
'''

Ref

• 모두의 알고리즘 with 파이썬