[알고리즘] 버블 정렬, Bubble Sort

버블 정렬이란

버블 정렬이란, 인접한 두 요소를 비교해서 큰 값을 뒤로 보내는 방식으로, 데이터가 정렬될 때까지 이 과정을 여러 번 반복하는 정렬 방법이다.

예

위의 사진을 보면 알 수 있듯이, 버블 정렬은 인접한 두 요소를 비교하고, 더 큰 값을 뒤로 보내는 작업을 반복하는 정렬 알고리즘이다. 또한, 버블 정렬은 리스트 원소의 개수에서 1을 뺀 횟수만큼 pass(회차)를 수행하며, 각 pass가 끝날 때마다 가장 큰 값이 고정되어 정렬 범위에서 제외된다.

수도코드

procedure bubble sort (a1 , a2 , ..., an : real number, n ≥ 2, unsorted)
     for i = 1 to n-1 (pass의 횟수)
           for j = 0 to n - i - 1 (비교할 원소의 인덱스 값)
                 if aj > aj+1 then
                       swap aj and aj+1

{a1 , a2 , ..., an is in increasing order}

Python

A = [10, 8, 6, 2, 7, 4]
n = len(A)

for i in range(1, n): # pass 횟수

  print("\n")
  cnt = 0
  print(A, "i :", "{}-{}".format(i, 0))

  for j in range (0, n-i): # j : pass에서 비교할 인덱스 넘버 (i의 값이 증가함에 따라, j의 범위가 줄어들고, 이에 따라 시행마다 맨 끝 인덱스는 건들지 않음.)

    if A[j] > A[j+1]:
      tmp = A[j]
      A[j] = A[j+1]
      A[j+1] = tmp

    cnt +=1
    print(A, "i :", "{}-{}".format(i, cnt))

print('\n정렬된 A : ', A)

Every pair of elements that are found to be out of order are interchanged.