버블 정렬

앞에서부터 2개씩 크기를 비교하여 정렬하는 "버블" 정렬

 

 

패턴 파악

데이터 2개 (턴 한번, 비교 1번)

1. 턴 한번

5

2

2

5

 

데이터 3개  (턴 두번, 비교 2번)

1. 턴 한번

5

4

2

4

5

2

2. 턴 두번

4

2

5

2

4

5

 

데이터 4개까지 해보면 패턴이 보일 것이다.

1. 한 턴에서 비교 횟수 : [데이터 길이 -1]번 진행

2. 턴 횟수 : [데이터 길이 -1]번 진행

3. 한 턴이 마무리되면 가장 큰 값은 맨 뒤에 위치하게 된다. -> 매 턴마다 비교 횟수를 줄여도 된다.

 

 

psudo 코드

for index in 데이터 길이 -1 만큼 반복:

  for 데이터 길이 -1 -index 만큼 조건 체크:

      if 앞데이터 > 뒤데이터:

         swap(앞, 뒤)

 

* 스왑이 일어났는지 체크해서, 이미 정렬된 배열이라 스왑이 일어나지 않았다면 break하는 것이 효율적이다.

방법 1) swap = 0 으로  매 턴마다 초기화. swap 시에 +1 해준 후, 0인지 체크

방법 2) swap= False로 매 턴마다 초기화. swap 시에 true 해준 후, false인지 체크

(위 psudo에는 포함되지 않은 로직이다.)

 

 

파이썬 코드

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        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

import random

data_list = random.sample(range(100), 50)
print (bubblesort(data_list))

 

 

시간 복잡도

반복문이 2개인데, N만큼 반복하기 때문에, O(N^2).

 

만약 완전 정렬이 되어있는 최선의 경우는 한개의 for문만 돌기 때문에 O(N) 이 된다.