버블정렬(Bubble Sort)

  버블정렬은 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬한 알고리즘이다. 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 '거품'처럼 위로 올라가는 것을 연상케 한다. 예제를 통해 버블 정렬의 수행 과정을 살펴보자.  

  [그림1-1] 에서 가장 먼저 첫 번째 숫자인 50과 40을 비교하고 40이 작으므로 40과 50을 바꾼다. 다음에는 두 번째 숫자인 50과 이웃하는 90과 비교하고, 90이 크므로 자리를 바꾸지 않는다. 마지막으로 세번째 숫자인 90과 이웃하는 10을 비교하고, 10이 작으므로 90과 자리를 바꾼다. 이렇게 입력을 전체적으로 처리하는 것을 패스(pass)라고 한다. 즉, 1번의 패스 후에 그 결과를 살펴보면, 작은 수는 버블처럼 위로 1칸씩 올라갔다. '무거운' 수(큰 수)의 측면에서 관찰해보면, 가장 큰 수가 '바닥'에 위치하게 된다.

  그 다음으로 두 번째로 큰 수인 50이 가장 큰 수인 90의 위로 '가라앉았다.'

  세 번째로 큰 수인 40이 50의 위로 '가라앉았다.'

  일반적으로 n개의 원소가 있으면 (n-1)번의 패스가 수행된다. 앞의 예제를 살펴 보면, 두 번째 패스에서 50과 90의 비교는 불필요하다. 왜냐하면 50이 두 번째로 큰 수이기 때문이다. 마찬가지로 세 번째 패스에서 40과 50, 50과 90을 비교할 필요가 없다. 40이 세 번째로 큰 수이기 때문이다. 다음은 앞에서 설명된 과정에 기반한 버블 정렬 알고리즘이다.

입력 : 크기가 n인 배열 A

출력 : 정렬된 배열 A

for pass = 1 to n-1
  for i = 1 to n-pass
    if(A[i-1]>A[i]) // 위의 원소가 아래의 원소보다 크면
      A[i-1]<->A[i] // 서로 자리를 바꾼다.
  return 배열 A

다음은 버블 정렬이 수행되는 과정이다.