버블정렬2

template <class T>
void BubbleSort2(T arr[], const int size)
{
  bool Sorted = true;
  for (int i=size; i>0 && Sorted; i--)
  {
    Sorted = false;
    for (int j=0; j<i; j++)<="" p=""> </i;>
    {
      if (arr[j] < arr[j-1]) {
        T t=arr[j];
        arr[j]=arr[j-1];
        arr[j-1]=t;
        Sorted = true;
      }
    }
  }
}

약간의 트릭을 더해서 만든 정렬이다.
정렬을 한뒤에는 true를 만들어서 그 j에 대해서는 더이성 정렬을 안한다.
정렬이 거의 된 배열에서는 일반 버블보다 월등히 빠른 속도를 보이며, 임의 배열에서는 많은 속도의 향상이 있고 역순배열에서도 약간 속도 향상이 있었다.