Algorithm. Bubble Sort

버블정렬

우리는 흔히 데이터들을 보기 편하고 탐색하기 쉽게 내림차순 혹은 오름차순으로 정렬하곤 하다.
이렇게 데이터들을 정렬하기 위해 쓰이는 정렬 방식에는 여러 가지가 있다.

• 버블정렬
• 카운팅 정렬
• 선택 정렬
• 퀵 정렬
• 삽입 정렬
• 병합 정렬

이중에 가장 기본적인 버블정렬을 다뤄보려고 한다.

버블정렬은 인접한 두 개의 원소를 비교하며 자리를 계속 교환해 나가며 데이터를 정렬하는 방식이다.
첫 번째 원소부터 계속 자리를 교환해 가며 정렬을 하고 이게 마치 정렬된 숫자들이 물 위로 떠오르는 거품 모양과 같다 하여 버블 정렬이라 부른다고 한다.

시간복잡도 : O(n^2)

예로 [43, 5, 68, 10, 37]을 정렬해보면

이런 형태로 정렬이 된다고 보면 편할 것 같다.
빨간 박스자리의 숫자와 뒤의 노란 박스에 있는 숫자 중 낮은 숫자와 자리를 바꾸고,
같은 메커니즘으로 뒤로 한칸씩 빨간 박사를 옮기며 노란 박스 안의 작은 숫자와 자리를 바꾸는 형태다.

이 과정을 코드로 적으면

sample = [43, 5, 68, 10, 37]

for i in range(len(sample)-1):
    for j in range(i+1, len(sample)):
    	# i번째 값보다 j번째 값이 더 작으면 자리 바꿈
        if sample[i] > sample[j]:
            sample[i], sample[j] = sample[j], sample[i]

이렇게 적어 볼 수 있겠다.
위 코드에서 i가 빨간 박스, j가 노란 박스라고 생각하면 편할 것이다.
출력결과는,

이렇게 잘 정렬이 된다.