Bubble Sort

Bubble Sort는 가장 기본적인 정렬 알고리즘 입니다.

 

맨 왼쪽의 Element를 순차적으로 인접 Element와 비교하여, 값이 큰 Element를 오른쪽으로 옮기는 방식입니다.

버블정렬의 1번 Cycle

매우 간단한 것을 알수 있습니다. 1번의 Cycle이 끝나면, 마지막 Element를 제외한

 

나머지 부분배열에서 동일한 정렬을 진행하면, 모든 Element가 정렬되게 됩니다.

 

해당 알고리즘은 n, n-1, n-2, n-3..... 2, 1번의 비교를 진행하게 되어, 총 n(n-1)/2번의 비교가 이뤄지는 알고리즘 입니다.

 

그래서 알고리즘의 시간복잡도는 O(n^2)의 시간복잡도를 보여주는 알고리즘이 되겠습니다 :)

(고정된 시간이 걸리며, 가장 성능이 안좋습니다 ㅠ)

 

원래는 정렬 알고리즘 에서 가장 처음 나오는 알고리즘인데, 조금 늦게 다루게 되었네요

 

Python으로 구현된 Bubble Sort 소스코드입니다

 

import random

def bubble_sort(DT_list):
    #List의 모든 Element의 개수만큼 Cycle을 진행합니다.
    for i in range(len(DT_list)):
        #N-1번째 Element와 N번째 Element가 비교가 끝나면
        #1번의 Cycle이 종료됩니다.        
        for j in range(len(DT_list)-i-1):
            #N번째 Element보다 N+1번째 Element가 작으면
            #두 값을 Swap해줍니다.
            if DT_list[j]>DT_list[j+1]:
                temp = DT_list[j]
                DT_list[j] = DT_list[j+1]
                DT_list[j+1] = temp
    #정렬된 List를 반환해줍니다.
    return DT_list

#무작위 순서의 List 생성
test = [i for i in range(10)]
random.shuffle(test)
==>[7, 6, 8, 0, 3, 1, 9, 2, 5, 4]
bubble_sort(test)
==>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]