[버블 정렬] Bubble sort - python

출처: https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

Buuble Sort

---

시간복잡도: 

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다.

시간복잡도가 ${\displaystyle O(n^{2})}$로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

(시간복잡도: 문제를 해결하는데 걸리는 시간)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

def swap(x,i,j):     x[i], x[j] = x[j], x[i]   def bubble_sort(a):     for size in reversed(range(len(a))):         for i in range(size):             if a[i]>a[i+1]:                 swap(a, i, i+1)     return a   a = [3, 5, 8, 1, 2, 0]   print(bubble_sort(a)) Colored by Color Scripter

cs

5

[3, 5, 1, 8, 2, 0]

[3, 5, 1, 2, 8, 0]

[3, 5, 1, 2, 0, 8]

4

[3, 1, 5, 2, 0, 8]

[3, 1, 2, 5, 0, 8]

[3, 1, 2, 0, 5, 8]

3

[1, 3, 2, 0, 5, 8]

[1, 2, 3, 0, 5, 8]

[1, 2, 0, 3, 5, 8]

2

[1, 0, 2, 3, 5, 8]

1

[0, 1, 2, 3, 5, 8]

0

[0, 1, 2, 3, 5, 8]