[Algorithms] 버블 정렬(Bubble Sort)

깃허브: https://github.com/PSLeon24/DataStructure/blob/main/Sorting%20algorithm.ipynb

기본 정렬(Sorting algorithms)

기본 정렬의 종류

선택 정렬, 버블 정렬, 삽입 정렬

지난 포스팅에서 선택 정렬을 다루었음(더보기: https://psleon.tistory.com/30)

본 포스팅에서는 버블 정렬을 다루고자 함

 

버블 정렬(Bubble Sort)

버블 정렬(bubble sort)은 액체 속의 공기 방울이 가벼워서 위로 보글보글 올라오는 모습에 착안해서 붙인 이름

버블 정렬도 앞서 학습한 선택 정렬과 유사한 아이디어에 기반함(제일 크거나 작은 원소를 옮기는 작업을 반복하지만 옮기는 방법이 다름)

버블 정렬: 이웃한 두 원소의 대소 관계를 비교해 필요에 따라 교환을 반복하는 알고리즘

https://gfycat.com/ko/exaltedinconsequentialdwarfrabbit

버블 정렬에서 교환 과정

https://dl1683.github.io/DataStructuresInJavaScript/ds/bubblesort/index.html

→ 이웃한 두 원소를 비교하고, 필요에 따라 교환을 반복

이때 원소 수가 n인 배열에서 n-1번 비교·교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동함

이러한 일련의 비교·교환하는 과정을 패스(pass)라고 함

ex) 위 이미지에서 첫 번째 패스로 가장 작은 원소인 -5의 정렬이 끝남, 그 후 두 번째 패스는 두 번째로 작은 원소인 1가 정렬이 끝남
두 번째 패스의 비교 횟수는 첫 번째 패스보다 1번 적은 n-2번임

따라서, 패스를 k번 수행하면 맨 앞부터 k개 원소가 정렬됨 → 모든 정렬이 끝나려면 패스를 n-1번 수행해야 함

패스를 n-1번 수행하는 이유: n-1개 원소의 정렬이 끝나면 마지막 원소는 이미 끝에 놓이기 때문에

파이썬 실습

위 코드에서 비교하는 두 원소의 인덱스를 arr[j - 1]과 arr[j]라 했을 때,

배열의 맨 끝에서 맨 앞을 향해 스캔하므로 j의 시작값은 n - 1

이때 두 원소 a[j - 1]과 a[j]의 값을 비교해 앞쪽 값이 뒤쪽 값보다 크다면 둘이 swap(오름차순 정렬을 위해)

그 이후의 비교·교환 과정은 맨 앞쪽을 향해 수행하므로 j값은 1씩 감소 → for j in range(n-1, i, -1) [6번 라인]

버블 정렬의 i번째 패스

Do it 자료구조와 함께 배우는 알고리즘 입문(파이썬 편) p.224

각 패스에서 앞쪽 i개 원소는 정렬이 끝난 상태이고, 정렬하지 않은 부분은 arr[i] ~ arr[n -1]이라고 가정

따라서 한 번의 패스에서는 j값을 i + 1이 될 때까지 비교함

버블 정렬은 1칸 이상 떨어져 있는 원소를 교환하는 것이 아니라 서로 이웃한 원소만 교환하므로 안정적(stable)

→ 반면, 단순 선택 정렬의 경우 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않음(unstable)

원소를 비교하는 횟수: (n-1) + (n-2) + ... + 1 = n(n-1) / 2

ex) 위 예시에서 n이 7이므로 7*6/2 = 21

그런데 실제 원소를 교환하는 횟수는 배열의 원솟값에 따라 영향을 받으므로 그 평균값은 n(n-1) / 4번임

ex) 위 예시에서는 n이 7이므로 7*6/4 ≒ 10

 

정렬 과정 출력하기

두 원소 사이에 값을 교환할 경우 +를, 교환하지 않을 경우 -를 출력하도록 작성

4번째 패스 과정을 보면, 이미 모든 원소가 정렬이 완료되었기 때문에 원소 교환(swap)이 전혀 발생하지 않음

따라서 어떤 패스의 원소 교환 횟수가 0이면 이미 정렬이 끝난 경우이므로 이후의 패스 과정은 불필요하다고 판단하고 정렬을 중단하도록 알고리즘을 개선하고자 함

 

알고리즘 개선 1

알고리즘을 개선하기 위해서 각 하나의 패스에서 몇 번의 교환(swap)이 발생했는가를 counting 해주는 exchange 변수를 가장 첫 for문에 0으로 초기화하였음

이전 코드와 다르게 패스 4에서는 swap이 발생하지 않음. 이는 이미 정렬이 끝난 것이므로 패스 5, 패스 6과 같은 불필요한 반복 처리를 하지않으므로 원솟값을 비교하는 횟수가 기존 21회에서 18회로 개선되었음을 확인할 수 있음