정렬 알고리즘 1 : 버블 정렬

정렬 알고리즘을 정리하는 시간을 갖고자 한다.

첫 번째로 정리할 정렬 알고리즘은 바로 버블 정렬이다.

가장 기초적인 알고리즘으로 원소의 이동이 거품이 수면으로 떠오르는 모습이랑 비슷하여 지어진 이름이다.

버블 정렬을 실행하면 이러한 모습으로 정렬이 되게 된다.

 

실질적으론 사용하지 않는 알고리즘이다. 왜 사용하지 않는지는 아래 동작 예시를 보면 알게 된다!

방법

n개의 배열이 들어왔을 때 1번째와 2번째 원소를 비교하고, 2번째와 3번째,... , n-1번째와 n번째까지 정렬한다.

이를 n번 반복하면 된다.

이미 정렬되어있는 배열이 입력된다면 O(n)의 시간이 걸리겠지만 그게 아니라면

최대 O(n^2)의 시간이 걸린다.

예시

 5  4  3  8  9  10  2  이러한 배열을 정렬한다면

 

첫 번째 사이클

(4  5) 3  8  9  10  2 

 4 (3  5) 8  9  10  2

 4  3 (5  8) 9  10  2

 4  3  5 (8  9) 10  2

 4  3  5  8 (9  10) 2

 4  3  5  8  9 (2  10)

 

두 번째 사이클

(3  4) 5  8  9  2  10

 3 (4  5) 8  9  2  10

 3  4 (5  8) 9  2  10

 3  4  5 (8  9) 2  10

 3  4  5  8 (2  9) 10

 3  4  5  8  2 (9  10)

 

세 번째 사이클

 (3  4) 5  8  9  2  10

  3 (4  5) 8  9  2  10

  3  4 (5  8) 9  2  10

  3  4  5 (8  9) 2  10

  3  4  5  8 (2  9) 10

  3  4  5  8  2 (9  10)

 

네 번째 사이클

 (3  4) 5  8  2  9  10

  3 (4  5) 8  2  9  10

  3  4 (5  8) 2  9  10

  3  4  5 (2  8) 9  10

  3  4  5  2 (8  9) 10

  3  4  5  2  8 (9  10)

 

다섯 번째 사이클

 (3  4) 5  2  8  9  10

  3 (4  5) 2  8  9  10

  3  4 (2  5) 8  9  10

  3  4  2 (5  8) 9  10

  3  4  2  5 (8  9) 10

  3  4  2  5  8 (9 10)

 

여섯 번째 사이클

 (3  4) 2  5  8  9  10

  3 (2  4) 5  8  9  10

  3  2 (4  5) 8  9  10

  3  2  4 (5  8) 9  10

  3  2  4  5 (8  9) 10

  3  2  4  5  8 (9  10)

 

일곱 번째 사이클

 (2  3) 4  5  8  9  10

  2 (3  4) 5  8  9  10

  2  3 (4  5) 8  9  10

  2  3  4 (5  8) 9  10

  2  3  4  5 (8  9) 10

  2  3  4  5  8 (9  10)

 

이처럼 매우 비효율적이기 때문에 실무에선 거의 사용하지 않는다ㅠㅠ

---

구현

파이썬

# https://teching.tistory.com
def bubbleSort(list):
    for _ in range(len(list)):
        for i in range(len(list)-1):
            if list[i] > list[i+1] :
                tmp = list[i]
                list[i] = list[i+1]
                list[i+1] = tmp
    return list

nums =[5, 4, 3, 8, 9, 10, 2]
sortedNums = bubbleSort(nums)
print(sortedNums)

결과