버블 정렬
개념
버블 정렬은 뒤에서 앞으로 정렬하는 구조입니다.
(오름차순) 즉, 배열에서 인접한 값을 앞뒤로 비교하여 가장 큰 값을 마지막 비트로 보내 자리를 맞바꿉니다.
정방향으로 정렬하면서 큰 값을 하나씩 뒤로 보내 배열을 작은 것부터 큰 것까지 오름차순으로 정렬하는 정렬이다.
계속해서 큰 값을 뒤로 보내는 것은 거품이 움직이는 것처럼 보이므로 이름이 거품 정렬입니다.
이제 배열을 예로 들어 위에서 설명한 버블 정렬이 어떻게 작동하는지 살펴보겠습니다.
다음과 같이 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))
결론적으로
코드를 최적화하고 변경할 때, 시간을 측정했을 때 실행 속도가 훨씬 빨라졌다는 느낌을 받지 못했습니다.
다만, 코드가 조금 최적화된 것 같고, 실행 시간도 최적화 전보다 훨씬 짧아졌습니다.