버블 정렬

버블 정렬은 서로 붙어 있는 요소를 비교해가며 정렬하는 알고리즘이다

복잡도 : O(n^2)

이미 정렬이 되어 있든 안되어 있든 n개의 input이 있을 때 n개의 대해서 각각 n번, 즉 for문을 2번 돌기 때문에 (교환이 일어나지 않더라도 비교는 계속 진행하기 때문에) 최상, 최악, 평균의 경우 모두 O(n^2)의 시간복잡도를 갖게 된다.

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

arr = [64, 34, 25, 12, 57, 93, 1, 123]
bubbleSort(arr)

for 문의 n-1을 한 이유는 항상 2개의 원소를 비교하기 때문이다.
2개의 원소를 잡아서 도니까 맨 마지막에 도착할때는 배열 길이 -1 에서 사실상 필요한 모든 비교가 끝나게 된다. 그래서 -1을 해주었다.

두번째 for문의 n-i 는 맨 오른쪽 요소가 가장 큼을 확신할 수 있기 때문에 이미 정렬된 요소를 반복에 포함시키지 않기 위해 -i를 하는 것이다.

버블 정렬의 시간 복잡도는 언제나 n^2 이기 때문에 잘 사용하지 않는다.