[탐색과 정렬] 버블 정렬

버블 정렬 (Bubble Sort)

인접한 두 개의 자료를 비교하여 정렬하는 방법

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째 자료와 네 번째 자료 순으로 비교해가면서 마지막 자료까지 자료를 정렬하기를 반복한다.

이미지 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

버블 정렬은 한 회전을 마칠 때 자료 하나가 정렬됨을 보장하므로, 자료의 개수보다 한 번 적게 정렬을 반복한 뒤 완료한다. 또는 한 회전을 수행하는 동안 정렬한 횟수가 없으면 완료한다.

일반적인 경우, 계산 복잡도는 $$ \mbox{O}(n^2) $$

 

코드

• n - 1번 반복
  

  def bubbleSort(x):
  	length = len(x)-1
  	for i in range(length):
  		for j in range(length-i):
  			if x[j] > x[j+1]:
  				x[j], x[j+1] = x[j+1], x[j]
  	return x​

• 한 회전 내에 정렬이 없을 때까지 반복
  

  def bubble_sort(list):
      flag = False;
      
      while True:
          for j in range(0, len(list) - 1):
              if list[j] > list[j + 1]:
                  list[j], list[j + 1] = list[j + 1], list[j]
                  flag = True
          if flag:
              return list​