[잡담] 버블정렬에서 랜덤배열 정리가 역순배열 정리보다 오래걸리는 이유가 뭘까요..?

void BubbleSort(int DataSet[], int Length, int *cnt1, int *cnt2, int *cnt_compare)
{
int temp = 0;

for ( int i = 0; i < Length - 1; i++ )
{
for ( int j = 0; j < Length - (i + 1); j++ )
{
if ( DataSet[j] > DataSet[j + 1] )
{
temp = DataSet[j + 1];
DataSet[j + 1] = DataSet[j];
DataSet[j] = temp;

*cnt1 = *cnt1 + 1;

if (*cnt1 == 100000000) // 1억단위
{
*cnt1 = 0;
*cnt2 = *cnt2 + 1;
}
}

*cnt_compare = *cnt_compare + 1;
}
}
}

코드는 요따구로 생겼어요.

분명 역순배열일때가 최악이어야하는데 왜 이런결과가 나올까요!

[hapines]

5000만번이면 배열 길이가 얼마나 되는건가요?
너무 길어서 계산 외적인 시간이 들어간걸까요?

전체 개수를 확 줄여서 비교해보시면 기대한대로 나오지 않을까요?

[ArchAngelx]

교환횟수가 더 적은데도 느린 게 말이 안되는데요?

실수로 배열에 숫자 넣는 부분까지 실행시간에 포함시킨 건 아닌지요.

[유한량]

분기 예측 휴리스틱 때문으로 추측됩니다.
역순 정렬일 경우 초반에는 계속해서 비교가 일어나지만, 정렬이 되어 감에 있어서 초반부에는 항상 일정하게 false가 떨어지게 됩니다. 그래서 분기예측 휴리스틱이 동작하면서 필요한 위치로 처리되고, 랜덤하게 정렬된 경우보다 수행시간이 빠르게 나오는걸로 추측됩니다.
보다 학술적인 결과를 원하시면 컴파일러랑 하드웨어 최적화 옵션은 다 끄고 돌리시는걸 추천드립니다.

아 그리고 사족이지만 그래도 괜찮은 버블 소트 알고리즘이라면, 전체 검사 결과 정렬된 상태면 빠른 루프 종료 코드 정도는 넣어 주시는게 좋습니다...

[BlackAn]

CPU 최적화 중 if 를 직전에 탔는지를 기억해서 미리 계산하는 기법이 있던듯 한데 그게 의심되네요