[파이썬 알고리즘] 버블 정렬(bubble sort)이란?

알고리즘 이론의 정렬에 대한 내용입니다.
프로그램 작성시 정렬을 세우는 건 아주 중요하고 빈번한 일입니다. 간단한 프로그램을 만들 때는 파이썬 내장 함수로 정렬이 가능하니 큰 필요성을 못 느낄 수 있는데 큰 프로그램을 만들거나 새로운 문제가 나타날 때 정렬 알고리즘을 알고 있지 않으면 역량부족으로 한참 해맬 수도 있습니다.

정렬 알고리즘은 알고리즘 파트 중에서 쉬운 편에 속해서 기초로 알고리즘이라는 분야를 입문하기 좋은 파트이므로 시간을 내서 배워보시는 것을 추천드립니다.

 

 

 

 

 

이번 포스팅에서는 버블 정렬에 대해 소개하겠습니다.

버블정렬

정렬은 데이터가 있을 때 이를 정해진 순서대로 나열하는 것을 의미합니다. 손으로 쓰면 너무 쉽겠지만 컴퓨터는 그게 아니라서 알고리즘을 짜서 데이터를 정렬할 수 있게 해주어야 합니다.

숫자가 작은 것에서 큰 것으로 나열하는 것(오름차순)으로 설명하겠습니다.

버블 정렬은 인접한 데이터끼리 비교하는 방식입니다. 2개의 데이터를 $ a_1, a_2 $ 이라하면 $ a_2<a_1 $ 이면 서로 자리를 바꿉니다.
이를 옆으로 움직이면서 반복합니다.

출처 :&nbsp; https://en.wikipedia.org/wiki/Bubble_sort

로직 적용

실제 데이터에 로직을 적용해보면 다음과 같이 나옵니다.
data = [1,6,4,2]

• 1차 순회
  • 1,6 비교, 바꿈 없음 [1,6,4,2]
  • 6,4 비교, 바꿈 있음 [1,4,6,2]
  • 6,2 비교, 바꿈 있음 [1,4,2,6]
• 2차 순회
  • 1,4 비교, 바꿈 없음 [1,4,2,6]
  • 4,2 비교, 바꿈 있음 [1,2,4,6]
  • 4,6 비교, 바꿈 없음 [1,2,4,6]
• 3차 순회
  • 버블 정렬 전개 -> 전체 데이터 바꿈 없음 [1,2,4,6]
  • 알고리즘 끝

로직을 보면 제일 큰 수부터 하나씩 정렬되는 것을 알 수 있습니다. 그러니 4개의 데이터면 3번 순회를 하고 3번 비교를 하는 것을 알 수 있습니다. 제일 큰 수가 이미 끝에 있다면 순회 횟수는 줄 것 같습니다.

만약 데이터가 2개라면 순회는 1번만 일어날 1번 비교를 할 것이고 데이터가 3개라면 순회는 2번, 비교는 2번 일어날 것입니다. 그런데 맨 뒤수는 비교를 할 때마다 정해지니 뒤에는 비교를 안 해도 됩니다. 순회마다 비교 횟수는 1씩 줄어듭니다.

따라서 다음과 같은 횟수를 갖게 됩니다.

 

데이터길이	순회횟수	최대비교횟수
2	1	1
3	2	2
4	3	3

순회는 데이터길이 -1 만큼, 비교도 데이터길이-1 입니다.

하지만 최대비교횟수는 순회횟수마다 맨끝의 값을 비교하지 않아도 되니 비교횟수는 1씩 줄어듭니다.

데이터길이 4를 예로 들면 다음과 같습니다.

데이터길이	순회횟수	비교횟수
4	0	3
4	1	2
4	2	1

 

따라서 최종적으로 순회횟수는 데이터길이-1, 비교횟수는 데이터길이 - 순회횟수 -1 이 됩니다.

 

코드작성

로직 파악한대로 파이썬으로 이를 표현하겠습니다.

1. 데이터는 유한개니깐 for문으로 해야겠죠?
2. 순회를 할 for문과 비교 for문을 나눕니다.
3. 순회 횟수 (데이터길이-1), 비교(데이터길이-순회횟수 - 1)
4. 반복문 안에서 앞뒤 데이터 두개를 가져와 서로 비교를 합니다.
5. 정렬이 안되어 있다면 swapping 이용해 바꿉니다.
6. 모든 순회를 돈 후 알고리즘을 끝냅니다.

def bubblesort(data):
    for index1 in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index1 - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True

        if swap == False:
            break
    return data

실제로 되는지 확인하겠습니다.

import random
data = random.sample(range(100),50)
print(bubblesort(data))

 

알고리즘 분석

알고리즘은 시간이 얼마나 짧게 걸릴지 최악의 상황이 언제인지(시간복잡도)와 얼마나 많은 메모리를 쓰는지(공간복잡도)로 나눠서 분석하는데 현재는 공간을 따로 신경쓸 필요가 없으니 시간 복잡도만 확인하겠습니다.

시간복잡도

n개의 데이터에서 이미 모두 정렬이 되어있는 경우 순회만 하면 되므로 시간복잡도는 O(n) 이 됩니다.

최악의 경우, n개의 데이터일 때 시간복잡도는 $ O(n^2) $ 가 됩니다.

실제로, 로직에서도 보았듯이 n-1 루프를 도는 동안, 인접한 원소들과 비교를 하니 $ (n-1)+(n-2)+...+1=(n-1)*n/2 = (n^2 - n)/2 $ 이 됩니다.

 

함께보면 좋은 글

[Python] 속도 개선 -Loop편