08/06/11 11:04:54
>>217
拾ってきたコードで試したら、比較回数はクイックソートより少し多かった。
>>218
引き分けがないとすると、140!通りの並べ替えがありうる。
140!通りに分岐させるためにはlog(140!)/log(2)回以上の比較が必要。
log(140!)/log(2)を計算すると801.01...。
だから、（比較のみによる）どんなに優れたソートアルゴリズムを使っても、
ワーストケースでは必ず802回以上の比較を要する。
08/06/11 11:04:54
>>217
拾ってきたコードで試したら、比較回数はクイックソートより少し多かった。
>>218
引き分けがないとすると、140!通りの並べ替えがありうる。
140!通りに分岐させるためにはlog(140!)/log(2)回以上の比較が必要。
log(140!)/log(2)を計算すると801.01...。
だから、（比較のみによる）どんなに優れたソートアルゴリズムを使っても、
ワーストケースでは必ず802回以上の比較を要する。