[알고리즘] 기본적인 정렬 알고리즘 - 버블정렬

Intro

이 글에서는 기초적인 정렬 알고리즘인 버블정렬에 대해 정리한다.

버블 정렬은 평균적으로 $O(n^2)$의 시간복잡도를 갖고 있다.

 

혹시나, 시간복잡도에 대해 모른다면 아래 글을 읽고 오자.

https://stringju.tistory.com/7

[알고리즘 #1] 시간 복잡도와 점근 표기법

 

버블 정렬

버블 정렬의 개념은 순서가 잘못된 인접한 두 수를 교환하는 것이다.

 

[10,3,7,4,9] 가 저장되어 있는 배열이 있고, 이를 오름차순(값이 작은 것 부터 나열)으로 정렬하자.

 

첫 번째 순회에서는

1. 10과 3은 잘못된 순서이므로, 교환한다

2. 10과 7은 잘못된 순서이므로, 교환한다

3. 10과 4는 잘못된 순서이므로, 교환한다

4. 10과 9는 잘못된 순서이므로, 교환한다

결과적으로 가장 값이 큰 10이 맨 뒤로 오게 된다.

 

두 번째 순회에서는

1. 3과 7은 올바른 순서이므로, 아무것도 하지 않는다.

2. 7과 4는 잘못된 순서이므로, 교환한다.

3. 7과 9는 올바른 순서이므로, 아무것도 하지 않는다.

결과적으로 9가 그 다음에 위치하게 된다.

 

3번째, 4번째, 5번째 순회도 같은 방법으로 동작하여, 최종적으로 3,4,7,9,10 순서로 정렬된다.

 

Code

해당 알고리즘을 파이썬으로 구현하면 다음과 같다.

 

def bubble_sort(lists):
    n = lists.__len__()
    for i in range(0,n-1):
        for j in range(0, n-i-1):
            if lists[j] > lists[j+1]:
                temp = lists[j]
                lists[j] = lists[j+1]
                lists[j+1] = temp

# Test
l = [10,3,7,9,4]
bubble_sort(l)
print(l)

 

주석 아래 부분은 테스트를 위한 코드이다.

해당 코드를 실행하면 [3,4,7,9,10] 이 나오는 것을 확인할 수 있다.