버블소트
다음과 같은 [9, 8, 7, 6, 5, 4, 3, 2, 1] 배열이 있을 때 오름차순으로
정렬하고 싶을 때 버블소트를 사용한다.
버블소트의 핵심은 이중포문을 사용하여 한 사이클을 돌았을 때 배열 내 가장
큰 수가 마지막 인덱스에 안착한다는 것이다.
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
버블소트 코드는 위와 같고 한 사이클을 돌았을 때 결과 값을 print로 찍어
보면 [8, 7, 6, 5, 4, 3, 2, 1, 9] 와 같다. 초기 배열과의 차이를 살펴
보면 맨 앞의 9과 맨 뒤로 이동한 것을 볼 수 있다.
9의 이동은 한칸씩 옆으로 움직이면서 이루어졌는데 이 모양새가 거품이 올라
오는 모양을 닮았다고 해서 버블소트라고 한다.
포인트를 이해하는 것이 핵심이다. 한 사이클을 돌면 가장 큰 숫자가 가장 뒤
로 이동한다.