[알고리즘] 버블 정렬(Bubble Sort)

정렬(sorting)이란?

• 정렬(sorting): 어떤 데이터들이 주어졌을 때 이를 순서대로 나열하는 것
• 정렬은 프로그램 작성시 빈번하게 필요로 한다.
• 다양한 알고리즘이 있으며, 알고리즘 학습의 필수이다.

 

버블 정렬(Bubble Sort)란?

• 두 인접한 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

버블정렬의 규칙찾기

• n개의 리스트가 있는 경우 최대 n-1번의 로직이 적용된다.
• 로직을 1번 적용할 때 마다 가장 큰 숫자가 리스트의 가장마지막에 위치하므로 비교해야할 숫자가 하나씩 줄어들음
• 로직이 경우에 따라 일찍 끝날 수도 있다. 로직을 적용할 때 데이터의 교환이 한번도 일어나지 않으면 이미 정렬된 상태이므로 더 이상 로직을 반복할 필요가 없다.

 

버블 정렬(Bubble Sort) 알고리즘 구현

def bubble_sort(data):
    swap = False
    for index in range(len(data) - 1):
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        if swap == False:
            break
    return data

 

버블 정렬(Bubble Sort) 알고리즘 시간 복잡도

• 버블정렬 알고리즘에는 for문이 두 개 들어가니까 시간복잡도는 O(n^2)
• 최악의 경우, n*(n-1)/2
• 완전 정렬이 되어있는 상태라면 최선은 O(n)