알고리즘 - 버블 정렬

버블 정렬

개념

버블 정렬은 뒤에서 앞으로 정렬하는 구조입니다.

(오름차순) 즉, 배열에서 인접한 값을 앞뒤로 비교하여 가장 큰 값을 마지막 비트로 보내 자리를 맞바꿉니다.

정방향으로 정렬하면서 큰 값을 하나씩 뒤로 보내 배열을 작은 것부터 큰 것까지 오름차순으로 정렬하는 정렬이다.

계속해서 큰 값을 뒤로 보내는 것은 거품이 움직이는 것처럼 보이므로 이름이 거품 정렬입니다.

이제 배열을 예로 들어 위에서 설명한 버블 정렬이 어떻게 작동하는지 살펴보겠습니다.

다음과 같이 1~에서 5까지 총 5개의 숫자를 포함하는 배열이 있습니다.

(3, 2, 4, 5, 1)

먼저 3과 2를 비교하십시오. 3은 2보다 크기 때문에 위치를 변경하고 더 큰 값을 다시 보냅니다.

(3, 2, 4, 5, 1)
 ↑  ↑
3 > 2 => switch 
(2, 3, 4, 5, 1)

그런 다음 3과 4를 비교하고 4보다 크지 않으므로 3을 유지합니다.

(2, 3, 4, 5, 1)
    ↑  ↑
3, 4 => keep

그런 다음 4와 5를 비교하고 4가 5보다 크지 않으므로 유지하십시오.

(2, 3, 4, 5, 1)
       ↑  ↑
4, 5 => keep

그런 다음 5와 1을 비교하십시오. 5는 1보다 크기 때문에 위치를 변경하고 더 큰 값을 다시 보냅니다.

(2, 3, 4, 5, 1)
          ↑  ↑
5 > 1 => switch
(2, 3, 4, 1, 5)

이와 같이 처음부터 값을 비교하는데 앞의 값이 두 번째 값보다 크면 자리를 바꾸어 최대값을 끝까지 보낼 수 있다.

위의 과정은 끝까지 최대값을 보내고 다음으로 큰 값을 최대값으로 계속 보내는 것입니다.

origin: (3, 2, 4, 5, 1)
-----------------------
loop 1: (2, 3, 4, 1, 5)
                     *
loop 2: (2, 3, 1, 4, 5)
                  *  *
loop 3: (2, 1, 3, 4, 5)
               *  *  *
loop 4: (1, 2, 3, 4, 5)
            *  *  *  *
loop 5: (1, 2, 3, 4, 5)
         *  *  *  *  *

버블 정렬을 GIF로 이해하기

특징

버블 정렬은 큰 값이 뒤에서 앞으로 쌓일수록 정렬 범위가 1씩 감소합니다.

다음 루프에서 마지막 최대값을 비교할 필요가 없기 때문입니다.
정렬을 선택하고 가장 작은 값을 앞으로 이동한 다음 반대 방향으로 정렬합니다.
선택 정렬보다 위치가 더 많이 변경됩니다.
위의 루프 4와 루프 5를 보면 최적화를 위한 불필요한 과정이 있습니다.

복잡한

버블 정렬은 추가 공간을 사용하지 않고 배열에서 값의 위치를 변경합니다.

0(1)공간 복잡도는
시간 복잡도는 기본적으로 모든 인덱스가 반복문을 통해 위에서부터 앞으로 액세스되기 때문입니다.

0(N) 시간 낭비,
루프에서 인접 값에 대한 대소문자 비교 및 위치 이동 0(N) 시간이 걸리다
그래서 버블 정렬은 0(N^2)시간복잡도는
이미 정렬된 배열의 경우 시간 복잡도는 0(N)입니다.

파이썬 코드

선택 정렬과 마찬가지로 두 번의 반복이 필요합니다.

내부 반복문에서 첫 번째 값부터 이전 라운드에서 거꾸로 보낸 값의 위치까지 전후 값을 계속 비교합니다.

이전 값이 다음 값보다 큰 경우 숫자 변경(토글)을 수행합니다.

외부 반복 문에서 정렬 범위는 뒤에서 앞으로 정렬됩니다.

n-1~에서 1 다음으로 축소

def bubbleSort(array):
    length = len(array)-1

    for i in range(length):
        for j in range(length-i):
            if array(j) > array(j+1):
                array(j),array(j+1) = array(j+1), array(j)

    return array

bubble_arry = (10, 1, 9, 2, 8, 3, 7, 4, 6, 5)

print(bubbleSort(bubble_arry))

최적화

이전 루프에서 스위치가 발생하지 않았다면 정렬되지 않은 값이 없다고 할 수 있습니다.

따라서 이 경우 루프를 수행할 필요가 없습니다.

origin: (1, 2, 3, 5, 4)
------------------------
 loop 1: (1, 2, 3, 4, 5) => switch 있음
                      *
 loop 2: (1, 2, 3, 4, 5) => switch 없음
                   *  *
=> 이전 패스에서 loop이 한 번도 없었으니 종료

import timeit

def time_decorator(func):

    def exec_func(*args, **kwargs):
        start_time = timeit.default_timer()
        result = func(*args, **kwargs)
        print(timeit.default_timer() - start_time)
        return result
    return exec_func

@time_decorator
def bubbleSort(array):
    length = len(array)-1

    for i in range(length):
        switch = False
        for j in range(length-i):
            if array(j) > array(j+1):
                array(j), array(j+1) = array(j+1), array(j)
                switch = True
        if not switch:
            break

    return array

bubble_arry = (10, 1, 9, 2, 8, 3, 7, 4, 6, 5)

print(bubbleSort(bubble_arry))

결론적으로

코드를 최적화하고 변경할 때, 시간을 측정했을 때 실행 속도가 훨씬 빨라졌다는 느낌을 받지 못했습니다.

다만, 코드가 조금 최적화된 것 같고, 실행 시간도 최적화 전보다 훨씬 짧아졌습니다.