[알고리즘] - 버블 정렬

버블 정렬 (Bubble Sort)

정렬 과정

• 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환 하면서 맨 마지막 자리까지 이동한다.
• 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
• 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 해서 버블정렬!
• 시간 복잡도는 O(n2)

예시

# 오름차순으로 정렬하기
lst = [55, 7, 78, 12, 42] 

첫 번째 패스 - 55와 7 비교를 시작해서 큰 값을 오른쪽으로 계속 이동 시키면 가장 큰 값이 제일 오른쪽에 처음으로 정렬된다.

두 번째 패스 - 다시 7과 12 비교를 시작하여 큰 값을 오른쪽으로 정렬하면 2번째로 큰 값이 제일 큰 값 왼쪽으로 가게 된다.

위 과정을 반복하면,

코드로 구현

# 오름차순 정렬
lst = [55, 7, 78, 12, 42] 

for i in range(len(lst)-1):
    for j in range(i, len(lst)-1):
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]

# 함수로 표현
def BubbleSort(arr, n):		# arr: 정렬할 배열, n: 배열의 크기
    for i in range(n-1, 0, -1):
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]