버블 정렬(Bubble Sort)

버블 정렬은 매우 간단한 정렬이지만 어떻게 설정하느냐에 따라서 수행횟수가 달라질 수 있다. 매번 수행될때마다 마지막에 위치한 배열의 원소가 정렬된다는 특징을 갖는다.

첫번째 방식은 위 특징을 고려하지 않고 매번 수행때마다 처음부터 끝까지 모두 비교한 방법이다.

arr = [3,6,1,2,9,0,35,12]
count = 0

def bubbleSort(A):
    global count
    for i in range(0,len(A)-1):#n-1(0~n-2)번 수행
        for j in range(0, len(A)-1):#n-1번 수행 
            count += 1
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                

bubbleSort(arr)

print(arr);
print("%d" %count)
//[0, 1, 2, 3, 6, 9, 12, 35]
//49번 수행

두번째 방식은 매번 마지막 원소가 정렬된다는 특징을 고려하여 작성한 방법이다.

arr = [3,6,1,2,9,0,35,12]
count = 0

def bubbleSort(A):
    global count
    for i in range(0,len(A)-1):#n-1(0~n-2)번 수행
        for j in range(0, len(A)-1-i):#순차적으로 n-1, n-2, ..., 2, 1번 수행
            count += 1
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                

bubbleSort(arr)

print(arr);
print("%d번 수행" %count)
//[0, 1, 2, 3, 6, 9, 12, 35]
//28번 수행

수행횟수가 꽤 차이나는 것을 확인할 수 있다. 버블 정렬의 시간복잡도는 두 방식 모두 최선, 평균, 최악 모두 O(n^2) 이다.