버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)는 배열 속의 모든 값을 비교해서 서로 자리를 바꾸는 알고리즘이다.

인접한 원소와 인접한 원소의 크기를 비교해서 자리를 바꾸는 알고리즘이다.

ADL은 다음과 같다.

bubbleSort(a[],n)
	for (i <- n; i >= 1; i<- i-1) do
    	for (j <- 1; j<i; j <- j+1) do
        	if (a[j] > a[j+1]) then a[j]와 a[j+1] 교환;
end bubbleSort()

바로 예시를 들어서 진행과정을 봐보자

[3,2,5,1,4] 를 정렬하는 과정이다.

bubble sort

위 과정과 같이 하나하나씩 비교해가면서 끝자리(가장 큰 수)를 먼저 정렬하는 과정이다.

이는 selection sort와 동일하게 N개의 원소 각각에 대해 N-1 번 비교하게 되므로 \( O(N^{2} \) 이다.

python 코드는 다음과 같다.

def bubblesort(a,n):
    for i in range(n,0,-1):
        for j in range(1,i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

a = [-1,11,15,7,2,8,5,3,1,6,13,14,9,12,10,4]
print(bubblesort(a, len(a)-1))