TIL - 버블 정렬

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

배열을 오름차순으로 정렬한다면 왼쪽의 값(9)이 오른쪽의 값(8)과 같거나 작아야 한다.

[6, 4, 3, 7, 1, '9', '8']

따라서 9와 8을 교환하면 다음과 같이 된다.

[6, 4, 3, 7, 1, '8', '9']

이렇게 이웃한 원소를 비교하고, 필요하면 교환한다. 이때 원소 수가 n인 배열에서 n-1번 비교, 교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동한다.

이러한 일련의 비교, 교환하는 과정을 패스라고 한다.

---

패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어든다. 그러므로 두 번째 패스의 비교 횟수는 첫 번째 패스보다 1번 적은 n-1이다.

패스를 k번 수행하면 맨 앞부터 k개의 원소가 정렬된다. 모든 정렬이 끝나려면 패스를 n-1번 수행해야 한다.

수행하는 패스 횟수가 n번이 아니라 n-1번인 이유는 n-1개 원소의 정렬이 끝나면 마지막 원소는 이미 끝에 놓이기 때문이다.

---

Python 실습

def bubble_sort(a):
  n = len(a) 
  for i in range(n - 1): 
    for j in range(n - 1, i, -1): 
      if a[j - 1] > [j]:
        a[j - 1], a[j] = a[j], a[j - 1]

튜플 언패킹을 통해 값을 스왑하며 된다.

---

개선 방법이 여러가지 있고 대부분 정렬이된 부분을 제외한 정렬 방법이다.
특이하게 셰이커 정렬은 while > for * 2 형태로 홀수 패스일 때 큰 숫자를 뒤로, 짝수 패스일 때 작은 숫자를 앞으로... 0 -> n, n -> 0 번갈아가며 정렬한다.