DataStructure in Python[Bubble Sort]

출처 : http://onestep.tistory.com/44

버블 정렬은 인접한 요소를 비교, 교환을 반복해서 정렬하는 것으로 가장 느린 알고리즘이라고 한다.

처음에 원출처 안보고 한번 짜보았다가 저번에 짠 selection sort를 짜버려서 당황을 했었다.

버블 정렬의 가장 큰 특징은 현 [인덱스 -1] 값과 비교한다는 것이다.

물론 현 인덱스 +1 값과 비교하는 것도 좋겠지만 

짜다보니 인덱스 -1 값으로 짜게 되더라. 굳이 +1 로는 짜볼 생각이 나질 않았다.

이중 루프를 사용하는데 2번째 for 문에서 보면 len(list)-i을 하는 것을 볼수 있다.

버블 정렬은 처음 루트때 가장 큰 값이 가장 뒤쪽에 위치하게 된다.

따라서 len(list)-i를 함으로써 불필요한 횟수를 감소시키는 것이다.

또한 바로 전 인덱스 값을 비교해야하기 때문에 두번째 for문의 비교문을 보면 list[j-1]을 볼수 있다.

import random
 
def bubbleSort(list):
    for i in range(len(list)-1):
        for j in range(1, len(list)-i):
 
            for k in range(len(list)):
                if k == j or k == j-1:
                    print('[{}]'.format(list[k]),end='')
                else:
                    print(' {} '.format(list[k]),end='')
            if list[j-1]>list[j]:
                list[j-1],list[j] = list[j],list[j-1]
            print()
        print()
 
def Main():
 
    # 테스트 할 랜덤 넘버 리스트 생성
    list = []
    for i in range(0,21):
        list.append(random.randint(1,99))
 
    print('==============버블 정렬 전==============')
    for i in list:
        print('*'* i)
    print()
 
    bubbleSort(list)
    print('==============버블 정렬후==============')
    for i in list:
        print('*'* i)
 
Main()

비교를 한다음에 두 값을 서로 교환한 직전의 모습을 출력시켜보았다.

비교를 했을 때, 뒷값이 작으면 치환이 된다.

아래의 출력 하면은 서로 치환되기 전의 출력이 그 다음 라인에서는 치환되는 것을 보여준다.

1번째 루프를 도는 동안의 모습이므로 전체 모습이 궁금하면 직접 돌려보면 된다.

 
[88][15] 61  23  7  6  88  65  85  81  22  25  19  5  70  39  97  32  81  15  17 
 15 [88][61] 23  7  6  88  65  85  81  22  25  19  5  70  39  97  32  81  15  17 
 15  61 [88][23] 7  6  88  65  85  81  22  25  19  5  70  39  97  32  81  15  17 
 15  61  23 [88][7] 6  88  65  85  81  22  25  19  5  70  39  97  32  81  15  17 
 15  61  23  7 [88][6] 88  65  85  81  22  25  19  5  70  39  97  32  81  15  17 
 15  61  23  7  6 [88][88] 65  85  81  22  25  19  5  70  39  97  32  81  15  17 
 15  61  23  7  6  88 [88][65] 85  81  22  25  19  5  70  39  97  32  81  15  17 
 15  61  23  7  6  88  65 [88][85] 81  22  25  19  5  70  39  97  32  81  15  17 
 15  61  23  7  6  88  65  85 [88][81] 22  25  19  5  70  39  97  32  81  15  17 
 15  61  23  7  6  88  65  85  81 [88][22] 25  19  5  70  39  97  32  81  15  17 
 15  61  23  7  6  88  65  85  81  22 [88][25] 19  5  70  39  97  32  81  15  17 
 15  61  23  7  6  88  65  85  81  22  25 [88][19] 5  70  39  97  32  81  15  17 
 15  61  23  7  6  88  65  85  81  22  25  19 [88][5] 70  39  97  32  81  15  17 
 15  61  23  7  6  88  65  85  81  22  25  19  5 [88][70] 39  97  32  81  15  17 
 15  61  23  7  6  88  65  85  81  22  25  19  5  70 [88][39] 97  32  81  15  17 
 15  61  23  7  6  88  65  85  81  22  25  19  5  70  39 [88][97] 32  81  15  17 
 15  61  23  7  6  88  65  85  81  22  25  19  5  70  39  88 [97][32] 81  15  17 
 15  61  23  7  6  88  65  85  81  22  25  19  5  70  39  88  32 [97][81] 15  17 
 15  61  23  7  6  88  65  85  81  22  25  19  5  70  39  88  32  81 [97][15] 17 
 15  61  23  7  6  88  65  85  81  22  25  19  5  70  39  88  32  81  15 [97][17]
 

개인적으로는 selection sort랑 그다지 코드가 많이 다르지는 않는 거 같다. 이중 루프라서 O(N^2) 의 성능을 가지는 것도 유사하다.