버블 정렬 (bubble sort)

 

* 버블정렬의 개념

 

• 두 인접한 원소를 검사하여 정렬하는 방법을 말한다. 시간 복잡도는 느리지만, 코드는 단순하다.
• 교환정렬의 일부에 속한다.
• 원소가 이동하는 모습이 거품이 수면위로 올라오는 듯한 모습과 같다고해서 붙여진 이름이라고 한다.

 

* 정렬의 과정

 

• 버블정렬로 정렬을 할때는, 원소의 갯수만큼의 순회를 하게된다.
• 1회차때는 가장 큰수가, 2회차때는 두번째로 큰수..... 이런식으로 가장 큰수부터 자기자리를 찾아가게 된다.
• 따라서, 회차를 거듭할수록 1회씩 정렬의 횟수가 적어지게된다. (자기자리를 찾은 부분은 정렬할 필요가 없으므로)
• array = [7,4,6,1] 이라는 배열을 버블정렬을 이용하여 작은수가 앞에 오도록 정렬한다면

 

 

---

 

 

* 1회차 : 가장 큰수(7)가 정렬된다.

정렬횟수 : 3회

* 2회차 : 두번째 큰수(6)이 정렬된다. (이미 정렬을 마친 맨 뒷부분은 방문하지 않는다.)

정렬횟수 : 2회

* 3회차 : 세번째 큰수(4)이 정렬된다. 

정렬횟수 : 1회

* 시간복잡도

 

원소가 4개인 배열을 버블정렬했을때(위의 예시)

n = 원소의 개수

n-1 = 3 번 회차가 존재했다.

각 회차마다 정렬횟수는 (n-1) + (n-2) + (n-3) = 3 + 2+ 1 이었다.

따라서 이를 일반화 해보면 ( n*(n-1) ) / 2

즉,O(n²)의 시간 복잡도를 가지게 된다.

 

 

* 파이썬 코드로 구현

def bubble(n, data):
    for i in range(n-1):
        for j in range(n-1-i):
            if data[j] > data[j+1]:
                data[j],data[j+1] = data[j+1], data[j] 
    for i in range(n):
        print(data[i], end = ' ')



n = int(input())
data = list(map(int,input().split()))

bubble(n, data)