[Algorithm] Bubble sort

What is bubble sort? 

첨부 영상에 따르면, 버블 정렬은 캘리포니아에 위치했던 세계 최초의 소프트웨어 회사 System Development Corporation에서 두 명의 과학자가 공식적으로 작성한 문서에 기반한다. 버블 정렬은 서로 인접한 두 원소를 검사해서 정렬하는 알고리즘으로 알려져있다. 아래 gif를 계속 쳐다보고 있으면 가장 큰 막대가 가장 뒤로 옮겨지는 것을 알 수 있다. 
이를 큰 그림에서 보았을 때, 뒤에서부터 앞으로 정렬해 나가는 형태를 띈다고 한다. 
참조한 영상에서는 가장 상징적인 정렬 알고리즘이라고 하는데, 이는 가장 단순한 원리를 따르는 정렬 알고리즘이기 때문이 아닐까 추측해본다. 
아래 gif는 최종 정렬 상태를 보여주고 있지는 않지만, 모든 라운드를 거쳐 정렬 과정을 순회하면 왼쪽에서 오른쪽으로 갈수록 막대의 높이가 높아지는 우상향 삼각형 형태가 나온다. 

이 gif를 반시계방향으로 90도 회전시키면 위에서 아래로 내려올수록 막대의 길이가 짧아지는 형태를 띄게 된다. 버블이 위로 올라가는 성질이 있듯, 가장 긴 막대가 위로 올라가게 된다. 

 

https://velog.io/@jminkyoung/AL-%EA%B1%B0%ED%92%88-%EC%A0%95%EB%A0%AC-Bubble-Sort-JavaScript

 

 

 

반시계 방향 회전 시킨 모양

 

참고 영상의 내용이 단순해 하나의 예제를 통해 bubble sort를 살펴보면 다음과 같다. (with the help of the chat gpt)

 

1. 원본 리스트: [5, 3, 8, 4, 2]
2. 첫 번째 패스:
   • 결과: [3, 5, 4, 2, 8]
3. 두 번째 패스:
   • 결과: [3, 4, 2, 5, 8]
4. 세 번째 패스:
   • 결과: [3, 2, 4, 5, 8]
5. 네 번째 패스: (최대 n-1번 패스 수행하되, 더 이상 swap이 일어나지 않는다면 조기 종료하도록 코드 설정 가능)
   • 결과: [2, 3, 4, 5, 8]
6. 패스를 더 이상 수행할 수 없을 때 정렬이 완료됩니다. 
   
   • 결과: [2, 3, 4, 5, 8]

 

파이썬으로 구현한 bubble sort(with the help of the chat gpt)
https://chat.openai.com/share/2eefa04f-cf90-443a-9fc9-7d6077955617 

ChatGPT

 

기본 bubble sort 구현 방식

import time 

def bubble_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements(모든 배열의 원소에 접근해야 하므로 for문 돈다) 
    for i in range(n):
        
        # Last i elements are already in place(버블정렬은 뒤에서부터 정렬되는 꼴을 띈다.)
        for j in range(0, n-i-1):
            
            # Swap if the element found is greater than the next element
			#(앞의 원소가 인접한 뒤의 원소보다 클 경우 swap한다.)
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]



start = time.time()
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
end = time.time()
print("Sorted array:", numbers)
print("time: {0}".format(end-start))

 

SWAP flag를 이용한 방식

import time 

def bubble_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        # Flag to check if any swaps are made in the current iteration 
		# Flag를사용해 현재 라운드(iteration)에서 swap을 해야 하는 상황인지 체크한다. 
		# default값은 당연히 False. 
        swapped = False
        
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        
        # If no swaps were made in the current iteration, the array is already sorted
        # 아예 정렬이 되어 있는 상태일 경우(만약 정렬 상태가 최선일 경우 첫 iteration만에 여기서 break한다.)
        if not swapped:
            break


start = time.time()
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
end = time.time()
print("Sorted array:", numbers)
print("time: {0}".format(end-start))

 

 

위 두 방식의 속도 차이를 비교해보았자, 0.0s로 뜨니까 비교할 수 없다. 

math.factorial(100000)

따라서 중간에 위와 같은 연산을 추가해 시간을 늘린 후, 시간을 비교해보자. 

 

기본 bubble sort 구현 방식 ver.2 (time: 0.1922297477722168)

import time 
import math

def bubble_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        
        # Last i elements are already in place
        for j in range(0, n-i-1):
            
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]



start = time.time()
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
math.factorial(100000)
end = time.time()
print("Sorted array:", numbers)
print("time: {0}".format(end-start))

 

 

 

SWAP flag를 이용한 방식 ver.2 (time: 0.16645431518554688)

import time 
import math

def bubble_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        # Flag to check if any swaps are made in the current iteration
        swapped = False
        
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        
        # If no swaps were made in the current iteration, the array is already sorted
        if not swapped:
            break


start = time.time()
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
math.factorial(100000)
end = time.time()
print("Sorted array:", numbers)
print("time: {0}".format(end-start))

확실히 두번째 방식의 실행시간이 줄어들었음을 볼 수 있다.  

 

 

마지막으로 시간복잡도에 대해 다뤄보자. 
bubble sort의 시간복잡도는 코드에서 간단히 생각가능하다. 
bubble sort는 외부 루프 for문을 통해 모든 원소에 접근해야 한다. 비교해야 하는 두 원소 중 앞에 위치한 원소만을 따지면 외부루프를 도는 횟수는 N-1이라고 볼 수 있다. N-1번 루프를도는 동안, 첫 라운드(iteration)에서는 N-1번 인접한 원소들을 비교, 다음은 N-2번 비교, N-3,N-4,...1번의 인접한 원소들을 비교한다. 따라서 시간복잡도는 
O(n) = (n-1)+(n-2)+(n-3)+...+1 = (n-1)*n/2   n^2의 시간복잡도를 가진다는 사실을 알 수 있다. 이는 다른 정렬 방법에 비하면 매우 효율이 떨어지는 방식임을 알 수 있다. 
최선(정렬된 상황),평균,최악(역정렬된 상황)에서 모두 n^2의 시간복잡도를 가진다. 기본적으로 정렬되어 있는 최선의 상황에서도 계속 비교 연산을 수행하게 되기 때문. 

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

 

참고문헌: https://www.youtube.com/watch?v=kiFfp-HAu64