거품 정렬

현존하는 정렬 알고리즘들 중에서 가장 느리다.

이것은 일종의 잘 될 때까지 "무작정" 시도하는 알고리즘이라고 할 수 있다.

마치 거품이 물 위로 떠오르는 것처럼 정렬이 된다고 해서 거품정렬..

(오른차순으로 정렬을 할 경우)

* 거품 정렬의 최악의 경우

오른차순 정렬인데 내림차순으로 되어 있는 경우..

본질적으로 이중for루프 사용하고 정렬 알고리즘은 n^2에 속한다.

거품 정렬의 최적화

2가지 염두해야할 사항이 있다.

1. 함수가 하나의 반복에서 색인들을 한 번도 바꾸지 않았다면 이미 정렬된것이다.

2. 알고리즘이 ?번 반복되었다면 상위 ?개의 색인들은 이미 정렬된 상태이다.

알고리즘 의사코드

Bubblesort(Array)

int swaps=1

int top=Array.size-1;

int index

while(top!=0 AND swaps!=0)

swaps=0

for(index=0;index<top;index++)

if Array[index] > Array[index+1]

Swap(Array[index], Array[index+1])

swaps++;

end if

end for

top--;

end while

end function

이 함수는 각 반복에서 몇 번의 교환이 일어났는지 계산한다(swaps)

top--; 이것이 아직 정렬되지 않은 가장 큰 색인을 나타낸다. for루프에서 index > top인 이유는 위의 최적화 2와 같다.

#ifndef _SORT_H_
#define _SORT_H_

#include"Array.h"

template<class DataType>
void BubbleSort(Array<DataType>& p_array, int(*p_compare)(DataType, DataType))
{
 int top = p_array.Size();
 int index;
 int swaps = 1;

 while (top != 0 && swaps != 0)
 {
  swaps = 0;
  for (index = 0; index < top; index++)
  {
   if (p_compare(p_array[index], p_array[index + 1]) > 0)
   {
    // Swap(p_array[index], p_array[index+1]);
    swaps++;
   }
  }
  top--;
 }
}

#endif