Bubble Sort - 공부하는 도비

Oblivious Sort : the sequence of comparisons is independent of the input 

 

버블 정렬은 입력된 데이터와 관계없이(oblivious sort) 입력 시퀀스를 오름차순으로 정렬하는 자료구조이다. 

 

n (= 5) 개의 데이터가 들어왔을 때, 정렬 방법은 아래와 같다.

* Step 1

* Step 2

* Step 3 

* Step 4

 

(n-1) + (n-2) + ... 1번 수행하기 때문에 

총 n (n-1) / 2 번을 수행한다. 

 

따라서, 시간 복잡도 상에선 O(n^2)이 소요된다.

 

(간단히 작성한 파이썬 코드)

import random

def bubble(start_list):
    length = len(start_list)
    
    for i  in range(0, length-1):
        print()
        for j in range(0, length-1-i):
            if start_list[j] > start_list[j + 1]:
                temp = start_list[j]
                start_list[j] = start_list[j+1]
                start_list[j + 1] = temp  
            else:
                pass
            print(start_list)

    return start_list


start_list = list(range(0, 7, 1))
random.shuffle(start_list)

print(start_list)

end_list = bubble(start_list)

print()
print(end_list)