Bubble Sort

# Sort

[ stable vs unstable ]

정렬은 안정(stable)정렬과 불안정(unstable)정렬로 구분할 수 있습니다.

정렬되어 있지 않은 리스트에 중복되는 값이 있을 때, 이 값들의 순서가 보장이 되면 안정 정렬, 보장되지 않으면 불안정 정렬이라고 합니다. 이런 stable의 여부는 정렬에 있어서 중요한 특징 중 하나입니다.

또 다른 예시로 보면, 이름 순으로 정렬되어 있는 파일들을 날짜 순으로 재정렬한다고 했을때, 파일 이름 순서로 보장이 되면 stable, 보장이 되지 않으면 unstable정렬입니다.

[ In-place vs Out-of-place ]

정렬은 구현 방식에 따라서 In-place정렬과 Out-of-place정렬로 구분할 수 있습니다.

In-place정렬은 원본 데이터 내에 정렬이 이루어지는 경우이고, 원본데이터가 아닌 새로운 배열로 정렬된 output 결과를 만들면 Out-of-place정렬입니다.

 

정렬을 볼 때에는, 정렬의 시간복잡도와 안정정렬 여부, 구현방식 세 가지 관점으로 볼 수 있습니다.

 

 

# Bubble Sort

정렬되어있지 않은 정렬을 오름차순으로 정렬한다하면, 우선 앞의 두 개 데이터를 비교하여 정렬을 해줍니다. 그리고 한칸씩 이동하면서 동일하게 두 개의 데이터 값을 비교하여 정렬을 합니다. 처음부터 끝까지 이 사이클을 한번 반복을 한다면, 이 리스트의 가장 끝에 오는 값은 이 리스트 안에서 가장 큰 값이 오게 됩니다. 하지만, 이 값을 제외한 나머지들은 여전히 정렬되지 않습니다. 그러면 다시 비교하여 위치를 바꿔주는 연산을 수행하게 됩니다.

이 과정을 반복하면, 한 사이클을 마무리할 때마다 현재 리스트에 위치한 데이터들 중 가장 큰 값이 뒤에 하나씩 쌓이게 됩니다. 그래서 마지막에 정렬해야하는 데이터의 크기가 하나가 된다면 배열 내의 모든 데이터가 정렬된 상태가 되게 됩니다.

 

[ 정리 ] 

- bubble sort는 인접한 두 element의 값을 비교하고, 두 값이 정렬되어 있지 않다면 위치를 교환합니다. 이 동작을 리스트의 처음부터 끝까지 반복을 하면 정렬이 완료된 element가 생깁니다. 정렬이 완료된 elements를 제외하고 또 위의 과정을 반복합니다.

- 총 N(N-1)/2번의 비교 연산을 하게 되는데, 상수항을 무시하고 O(N^2)의 시간복잡도를 갖게 됩니다.

- 직관적이고 단순한 알고리즘이라 이해하기는 쉽지만, 속도가 느리다는 단점이 있습니다

 

 

# 코드 구현(Python)

def BubbleSort(arr):
    for i in range(len(arr)-1):
        for j in range(len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

for i in range(len(arr)-1):            전체리스트에 대하여 비교연산이 이루어져야 합니다
    for j in range(len(arr)-1-i):      정렬된 element를 제외한 리스트에 대한 비교연산(사이클 한번 돌 때마다 가장 큰 값이 하나씩 정렬되니까 -i를 추가적으로 해줍니다)
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]        두 element를 비교했을 때 앞의 값이 더 크면, 서로 위치를 바꿔줍니다

 

[ Test code ] 

if __name__ == '__main__':
    arr = [9,1,6,3,7,2,8,4,5,0]
    BubbleSort(arr)
    print(arr)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

# 전체 코드

깃허브에서 테스트 코드를 포함한 전체 코드를 보실 수 있습니다.

GitHub - sonzwon/TIL: Today I Learned