[알고_이론 ] 버블정렬 ( bubble sort by python )

버블 소트란?

인접한 원소 간의 비교를 통해 정렬하는 알고리즘으로써, 시간복잡도는 O(n2)이다.

 

시간복잡도가 왜 O(n2) 인가요?

버블소트는 인접한 값과의 숫자 비교를 반복해나가며 정렬을 진행합니다.

 

궁극적으로 우리가 원하는 오름차순의 배열을 얻기 위해서는 N개의 값들을 비교하는 과정을 N번 반복 했을 때, 정렬이 완료 되기 때문에 O(n2)라고 칭할 수 있다.

 

인접한 수끼리의 비교가 이루어 지는 경우, 자연스럽게 가장 큰 수가 배열의 맨 뒤로 향하는 현상을 확인 할 수 있을 것인데, 그러한 이유로 위와 같은 작업을 배열의 길이인 N번 반복이 완료 됬을 때 비로소 정렬이 완료 되었음을 알 수 있는 것이다.

 

버블 소트 예제

# 최초 문자열 
arr = [ 7, 6, 5, 4, 3 ]

# task 1 [ 7 > 6 ]

arr = [ 6, 7, 5, 4, 3 ]

# task 2 [ 7 > 5 ]

arr = [ 6, 5, 7, 4, 3 ]

# task 3 [ 7 > 4 ]

arr = [ 6, 5, 4, 7, 3 ]

# task 4 [ 7 > 3 ]

arr = [ 6, 5, 4, 3, 7 ]

버블소트 _ 파이썬 코드

import random

def bubbleSort(arr):
    for i in range(len(arr)-1, 0, -1) : # 각 회차마다 가장 큰 수가 맨 뒤로 오기 때문에
                                        # 배열의 총 길이에서 -1 줄여가며 진행해준다.
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j] # 인접 값들끼리의 비교를 통해 정렬
    return arr


arr = random.sample(range(100), 10)
print(arr)
print(bubbleSort(arr))