[알고리즘] 버블 정렬 (bubble sort)

버블 정렬이란? What is bubble sort?

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다.
안정적인 정렬(Stable Sort)이다.

• 그림 1번) 1회전 : 5개의 정렬 아이템들이 있으면 4번만 교환하면 정렬이 완료된다. (n-1번)
• 그림 2번) 2회전 : 3번만 교환하면 정렬이 완료된다 (n-2번)
• 총 n-1번 회전을 돌고 회전이 늘어날 때마다 교환시도 횟수는 1번씩 줄어든다

a=[7,4,5,1,3] 
n = len(a) 
for i in range(n-1): 
	for j in range(n-1-i): 
    	if a[j] > a[j+1]: 
        	a[j+1],a[j] = a[j],a[j+1] 
print(a)

패스(pass)

정렬하며 비교하고 교환하는 과정을 패스라고 한다.

버블 정렬의 시간복잡도

버블정렬은 외부 루프를 N-1번 도는 동안, N-1, N-2, N-3, ... , 1 번 인접한 원소들을 비교한다.
따라서 T(n) = (n-1)+(n-2)+(n-3)+...+1 = (n-1)*n/2
O(n) = n^2 이다.

버블 정렬 개선 알고리즘

• 이미 정렬이 완료 되었을 때 = 패스가 원소 교환이 일어나지 않을 때
  • 이미 정렬이 완료되었을 때 굳이 남은 for문 반복문을 안 돌려도 된다.

1. 어떤 패스의 원소 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이다. 그 이후의 패스는 불필요하므로 정렬을 중단 시킨다.
2. 이미 정렬된 원소를 제외한 나머지만 비교, 교환하도록 스캔 범위를 제한하는 방법
3. 셰이커 정렬
   • [9,1,3,4,6,7,8] 일 경우 버블 정렬 알고리즘을 그대로 사용하면 (n-1)n/2 번 돈다.
   • 9가 빠르게 맨 뒤로 이동하면 반복 횟수를 확연하게 줄일 수 있을 것이다.
   • 그래서 나온게 셰이커 정렬이다!
   • 홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동시키고, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾸어 준다.
   • 같은 의미로 양방향 버블 정렬, 칵테일 정렬, 칵테일 셰이커 정렬이라고도 한다.