3. 버블 정렬

버블 정렬은 인접한 두 원소를 검사해 정렬하는 알고리즘이다.

 

선택 정렬은 앞자리를 제하고, 남은 것 중 최소값을 찾는 방식으로 추출 했었으나,

버블 정렬에서는 모든 값을 다회 비교하기 위해 한 자리에서 두 번 이상의 교체가 이루어지는 경우가 있다.

 

1. 주어진 리스트의 첫번째 값과 인접한 값을 비교한다.

2. 두 값의 크기 순서가 일치하지 않을 경우, 교환한다.

3. 각 자리별로 순서대로 반복하며, 모든 자리의 값 크기 순서가 맞을 때 까지 순회한다.

 

리스트가 [ 5,4,2,1,0,3 ] 일 경우, 큰 수부터 정렬하는 예시

 

1순회

pass	table	자리교환
0	5,4,2,1,0,3
1	5,4,2,1,0,3	X
2	5,4,2,1,0,3	X
3	5,4,2,1,0,3	X
4	5,4,2,1,0,3	X
5	5,4,2,1,0,3	O
6	5,4,2,1,3,0	순회종료

 

2순회

pass	table	자리교환
0	5,4,2,1,3,0
1	5,4,2,1,3,0	X
2	5,4,2,1,3,0	X
3	5,4,2,1,3,0	X
4	5,4,2,1,3,0	O
5	5,4,2,3,1,0	X
6	5,4,2,3,1,0	순회종료

 

3순회

pass	table	자리교환
0	5,4,2,3,1,0	X
1	5,4,2,3,1,0	X
2	5,4,2,3,1,0	X
3	5,4,2,3,1,0	O
4	5,4,3,2,1,0	순회종료
		정렬완료

 

 

버블 정렬은 리스트의 크기만큼 계속해서 순회하기 때문에

시간복잡도가 O(n^2) , Ω(n^2)이 된다.

 

 

def bubbleSort(arr):
    
    length = len(arr) - 1
    
    for i in range(length):
        for j in range(length-i):
            if(arr[j] > arr[j+1]):
                arr[j], arr[j+1] = arr[j+1], arr[j]
                
    return arr

파이썬에서의 구현

출처: https://star-crab.tistory.com/22

[Python] 대표적인 정렬 알고리즘