버블 정렬

---

참고 사이트

• 두 개의 인접한 데이터를 비교하여, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 알고리즘이다.

시간 복잡도

• 반복문이 두 개이므로 시간 복잡도는 $O(n^2)$이다.
• 완전 정렬이 되어 있는 상태라면 $O(n)$이다.

구현

---

def BubbleSort(data_list):
    for i in range(len(data_list) - 1, 0, -1):
        swap = 0
        for j in range(i):
            if data_list[j] > data_list[j+1]:
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
                swap += 1
        if swap == 0:
            break
    return data_list