[알고리즘] 버블 정렬에 대하여 알아보자-Python

전시온·2022년 6월 27일
1

Algorithm 공부

목록 보기
3/3
post-thumbnail

🤷왜 버블 정렬일까?

Bubble은 거품이라는 뜻으로 가장 가벼운 것이 위로 올라가는 거품의 움직임에 빗대어 붙여진 이름이다. 버블 정렬은 서로 이웃한 숫자들을 비교하여 가장 큰 수를 뒤로 보내면 정렬하는 방법을 말한다. 버블 정렬을 활용할 때 기준을 정한다음 오름차순 또는 내림차순 순서로 정리할 수 있다.

✍아이디어

  1. 배열의 i번째 인덱스와 i+1번째 인덱스의 키를 비교한다.
  2. i번째 인덱스의 키가 더 크다면 자리를 swap 한다.
  3. 위 과정을 반복수행한다.

👍장점
직관적이고 간단한 구현
데이터 하나씩 비교하기 때문에 정밀한 비교 가능

👎단점
데이터를 전부 비교해야하므로 효율이 좋지 않다.
최악의 경우 비교할 때 마다 교환이 발생하므로 O(N^2)만큼의 시간복잡도를 갖는다.

🧑‍💻구현

먼저 두개의 반복문이 필요하다. 내부 반복문에서는 첫번째 값부터 이전에 뒤로 보내놓은 값이 있는 위치 전까지 앞뒤 값을 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 swap을 한다. 외부 반복문에서는 뒤에서부터 앞으로 정렬범위를 n-1부터 0까지 -1씩 줄여나간다. 내부 반복문의 for문 범위는 떠올리기 쉬우나 외부 반복문은 헷갈릴 수 있으니 예시를 들어서 비교해보자.위 사진을 예를 들어 Pass 1 에서 5를 맨 뒤로 보내 놓았으면 그다음 Pass 에서는 그 앞 2까지 값을 비교해 나가면서 swap을 하는 방식이다. 따라서 외부 반복문의 범위는 n-1부터 0까지 -1씩 줄여나가는 형식이다.

Python 코드

arr = [4, 6, 1, 7, 2, 9, 3]

n = len(arr)

for i in range(n-1, 0, -1):
	for j in range(i):
		if arr[j] > arr[j+1]:
			arr[j], arr[j+1] = arr[j+1], arr[j]

🏃최적화, 더 나아가기

버블 정렬은 부분적으로 정렬되어 있는 배열에 대해서는 최적화를 통해서 성능을 대폭 개선할 수 있으며, 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있다.

각 패스의 swap 여부 확인

이전 패스에서 앞뒤 자리 비교(swap)이 한 번도 일어나지 않았다면 정렬되지 않는 값이 하나도 없었다고 간주할 수 있습니다. 따라서 이럴 경우, 이후 패스를 수행하지 않아도 된다.

Python 코드 (swap 여부 이용)

def bubble_sort(arr):
	n = len(arr)
    for i in range(n - 1, 0, -1):
        swapped = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

추가 최적화

이전 패스에서 앞뒤 자리 비교(swap)가 있었는지 여부를 체크하는 대신 마지막으로 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬해도 된다. 따라서 한 칸씩 정렬 범위를 줄여나가는 대신 한번에 여러 칸씩 정렬 범위를 줄여나갈 수 있다.

Python 코드(index 이용)

def bubble_sort(arr):
    end = len(arr) - 1
    while end > 0:
        last_swap = 0
        for i in range(end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap = i
        end = last_swap

🙇마치면서

지금까지 버블 정렬 알고리즘과 최적화에 대하여 알아보았다. 최적화된 버블 정렬 알고리즘을 사용했을 때 완전히 정렬된 배열이 들어올 경우, O(N)만큼의 시간복잡도를 향상시킬 수 있다는 것이 흥미로웠다. 다음 포스팅에서 또 다른 정렬 방식에 대하여 알아보자.

감사합니다.

참고 자료
utm_source=google&utm_medium=organic&utm_campaign=organic
https://www.daleseo.com/sort-bubble/
https://www.boredpanda.com/a-transparent-bubble-chair-but-for-your-cute-cat/?

profile
Computer Vision, ROS, ROS2, 3D Lidar, IoT

0개의 댓글