버블정렬2

template <typename 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++)

{

if (arr[j] < arr[j-1]) {

T t=arr[j];
arr[j]=arr[j-1];
arr[j-1]=t;

Sorted = true;

}

}

}

}

약간의 트릭을 더해서 만든 정렬이다.

정렬을 한뒤에는 true를 만들어서 그 j에 대해서는 더이성 정렬을 안한다.

정렬이 거의 된 배열에서는 일반 버블보다 월등히 빠른 속도를 보이며,

임의 배열에서는 많은 속도의 향상이 있고

역순배열에서도 약간 속도 향상이 있었다.