버블 정렬

정의

 

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

 

Process

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

https://wonjayk.tistory.com/219

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

 

시간복잡도

 

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.

또한, Bubble Sort는 배열 정렬 여부와 관계없이 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.

 

공간복잡도

 

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

 

Code

# 함수
def bubbleSort(arr):
    n = len(arr)
    # 이중 for문이 정석적
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j] # 서로 위치를 변환

# 배열
arr = [64, 34, 25, 12, 57, 93, 1, 123]

# 출력
bubbleSort(arr)
for i in range(len(arr)):
    print("%d " %arr[i]) # 문자열 포맷팅

1. 제외될 원소의 갯수를 의미한다. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다.
2. 원소를 비교할 index를 뽑을 반복문이다. j는 현재 원소를 가리키고, j+1은 다음 원소를 가리키게 되므로, j는 0부터 시작하게 된다.
3. 현재 가르키고 있는 두 원소의 대소를 비교한다. 해당 코드는 오름차순 정렬이므로 현재 원소보다 이전 원소가 더 크다면 이전 원소가 뒤로 가야하므로 서로 자리를 교환해준다.

 

Another Code

'''
2. swapped 사용
swapped 변수를 사용하여 배열을 순회하면서 스왑 작업을 하고, 
한 번의 순회에서도 스왑이 일어났을 경우 swapped를 True로 설정하여 다음 순회를 계속하도록 합니다. 
이렇게 하면 중첩된 for 루프를 사용하지 않고도 정렬을 수행할 수 있습니다.

핵심 집중사항
while문 안에서 동작하는 순서를 잘 파악할 것
특히 swapped과 관련해서.
'''

def bubbleSort(arr):
    n = len(arr)
    swapped = True # 버블 정렬의 핵심 작업

    while swapped:
        swapped = False
        for i in range(1, n):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                swapped = True
        n -= 1

arr = [64, 34, 25, 12, 57, 93, 1, 123]
bubbleSort(arr)

print("Sorted array:", arr)