[알고리즘][버블정렬][BubbleSort][정렬][파이썬][Python]-정리 및 코드

Bubble Sort(버블 정렬)

 

버블 정렬은 삽입 정렬, 선택 정렬과 함께 가장 기본적인 정렬 알고리즘에 해당됩니다. 데이터를 처리하는 데 있어서 정렬은 가장 기본적이면서도 핵심적인 내용입니다.

 

아이디어

버블 정렬의 아이디어는 전체 데이터중 가장 큰 값을 맨뒤로 보내는 것입니다. 그렇기 때문에 버블 정렬의  전체 과정을 살펴보면 뒤에서부터 앞으로 정렬되는 과정을 보입니다. 전체 데이터 중 가장 값이 큰 데이터를 맨뒤로 보낸 후, 이미 정렬된 값을 제외한 데이터중 가장 값이 큰 데이터를 맨 뒤로 보냅니다. 이와 같은 과정을 계속해서 반복하면 데이터가 오름차순으로 정렬이 되는 것을 확인할 수 있습니다. 아래에서 구체적인 방법과 코드를 통해 알 수 있는데, 데이터를 비교하고 큰 값을 계속해서 뒤로 보내는데 이 과정이 마치 거품 같다고 하여 버블 정렬이라는 이름을 갖습니다. 

 

알고리즘

 

버블 정렬의 알고리즘은 다음과 같습니다. 정렬 되지 않은 무작위의 숫자가 리스트에 저장되어 있고 오름차순으로 정렬을 한다고 가정합니다. 

 

예 : [ 3, 2, 4, 5, 1 ] ( 정렬 되지 않은 리스트)

 

먼저 맨 앞의 3과 그 다음 값인 2를 비교합니다. 3이 더 큰 값이므로 3과 2의 위치를 바꿔 줍니다.

결과 1. [ 2, 3, 4, 5, 1 ]

 

이제  3과 그 다음 값인 4를 비교합니다. 4가 더 큰 값이므로 데이터는 그대로 유지됩니다. 

결과 2. [ 2, 3, 4, 5, 1 ]

 

이제 4와 그 다음 값인 5를 비교합니다. 5가 더 큰 값이므로 데이터는 그대로 유지됩니다. 

결과 3. [ 2, 3, 4, 5, 1 ]

 

이제 5과 그 다음 값인 1을 비교합니다. 5가 더 큰 값이므로 5와 1의 위치를 바꿔 줍니다.

결과 4. [ 2, 3, 4, 1, 5 ]

 

여기까지 한 사이클이 돌았습니다. 그 결과 전체 데이터중 가장 큰 값인 5가 맨 뒤로 이동한 것을 확인할 수 있습니다. 그다음 사이클을 살펴봅니다.

 

다시 맨 앞의 2와 그 다음 값인 3을 비교합니다. 3이 더 큰 값이므로 데이터는 그대로 유지됩니다.

결과 5. [ 2, 3, 4, 1, 5 ]

 

이제 3과 그 다음 값인 4를 비교합니다. 4가 더 큰 값이므로 데이터는 그대로 유지됩니다.

결과 6. [ 2, 3, 4, 1, 5 ]

 

이제 4와 그 다음 값인 1을 비교합니다. 4가 더 큰 값이므로 4와 1의 위치를 바꿔 줍니다.

결과 7. [ 2, 3, 1, 4, 5 ]

 

여기까지 두 번째 사이클이 돌았고, 4와 5가 정렬된 것을 확인할 수 있습니다. 이와 같은 과정을 계속해서 반복하면 전체 데이터가 오름차순으로 정렬된 것을 확인할 수 있습니다.

 

시간 복잡도 Big(O)

버블 정렬은 한 싸이클이 반복되면서 리스트의 처음부터 맨 마지막까지 비교를 진행하며 최대 O(N)의 시간 복잡도를 갖습니다. 여기에 사이클이 반복될 때마다 다시 비교를 진행하므로 각 사이클당 최대 약 O(N)의 시간 복잡도를 필요로 합니다. 즉 전체 데이터를 정렬하는 데는 최대 O(N) * O(N)= O(N^2)의 시간 복잡도를 갖습니다. 내림 차순으로 정렬되어 있는 경우가 가장 많은 스왑(Swap)이 필요하며 O(N^2)이 시간이 필요하게 됩니다. 만약 내림차순으로 정렬되어 있는 데이터를 정렬할 때는 O(N)의 시간 복잡도가 필요합니다.

 

영상으로 이해하기

이해가 안가시는 분들을 위해 버블 정렬을 눈으로 쉽게 이해할 수 있는 영상을 첨부하였습니다. 영상을 보면서 데이터가 이동하는 흐름을 살펴보면 알고리즘을 이해하는데 도움이 될 것이라 생각합니다.

 

 

 

 

소스코드

#Python

 

def Bubble_sort(li):
    for i in range(len(li)-1):
        print(li)
        for j in range(len(li)-i-1):
            if li[j]>li[j+1]:
                temp=li[j+1]
                li[j+1]=li[j]
                li[j]=temp
 
if __name__ =="__main__":
    list_a=[ 10-i for i in range(10) ]
    Bubble_sort(list_a)
    print(list_a)
 

 

중간 중간 print()를 추가하여 데이터가 스왑(Swap)하는 과정을 눈으로 확인할 수 있도록 작성하였습니다.

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.