[정렬 알고리즘] 2. 버블 정렬 (Bubble Sort)

버블 정렬

버블 정렬은 인접해 있는 각 요소끼리 값을 비교하고, 대소관계에 따라 위치를 바꾼다. 위키 백과에 따르면 정렬되는 모습이 마치 거품이 올라오는 것아 지어진 이름이라고 한다.  선택 정렬과 더불어서 굉장히 간단한 알고리즘이다. 버블 정렬의 시간복잡도는 O(n2) 이며, 공간복잡도는 O(n)이다.

로직

  1. 1번째 요소와 2번째 요소의 대소관계를 비교하고, 1번째 요소가 더 크다면 위치를 바꾼다.
  2. n번째 요소와 n+1번째 요소의 대소관계를 비교하고, n번째 요소가 더 크다면 위치를 바꾼다.
  3. n+1이 배열이 끝이 될때까지 반복한다.
  4. n+1이 배열의 끝이라면 1단계부터 3단계까지 반복하되, 직전의 마지막 인덱스 요소는 제외하고 비교한다.

위와 같은 순서로 반복하면, 정말 거품이 수면위로 떠오르듯이 가장 큰값이 배열의 끝으로, 그다음 큰 값이 배열의 끝에서 두번째 자리로 오는 모습을 반복하며 정렬되는 것을 볼 수 있다. 큰 값을 하나하나 배열의 마지막으로 차근차근 옮기는 알고리즘이라고 생각하면 된다.

소스코드 (Python)

list = [33,5,76,1,7,17,23,29,8,9,2]

for i in range(len(list) - 1):
  for j in range(len(list) - (1 + i)):
    if list[j] > list[j + 1]:
      list[j], list[j + 1] = list[j + 1], list[j]

print (list)