modified bubble sort

質問

ソーティングについて教えてください．

　ソーティングの手法に，バブルソートというものがあります(隣接するふたつを入れ替える)．このソーティングでは，最大交換回数は要素数が n のとき， n(n-1)/2 となります．

　隣接する要素の交換に加え，先頭と最後の要素の入れ替えも可能だとすると(イメージとしては，サイクリックなバブルソートです)，最大交換回数は n^2/4 となるそうです．

　この n^2/4 になる，という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます)．どなたかご教授頂ければと思います．

回答No.2

jmh

No1.jmh です。
ごめんなさい。最初に頭とお尻を交換するんですね。
ｎ＝３のときは、３１２→２１３→１２３（など）の２回が最悪ですね…たぶん。
でも、これって初回でしか頭とお尻の交換ができないのだから、ｎのサイクリックバブルの最大交換回数は、（ｎ－１）のバブル＋１回ぐらいになるのではないでしょうか？
例えば（５^2／４＝６．２５ですが）２５４３１を昇順に並べ替えるには７回交換が必要だと思います。
２５４３１
　→１５４３２
　　→１４５３２
　　　→１４３５２
　　　　→１４３２５
　→１３４２５
　　→１３２４５
　→１２３４５

回答No.1

jmh

ｎ＝３のとき、３^2／４＝２.２５ですけど…。

３２１を、そのバブルの亜種で並べ替えるとき、
パス１
　→３と２を比較、交換する　→２３１
　→３と１を比較、交換する　→２１３
　→３と２を比較、交換しない→２１３
パス２
　→２と１を比較、交換する　→１２３
　→２と３を比較、交換しない→１２３
　→３と１を比較、交換しない→１２３
交換３回となりませんか？