Skip to content
This repository has been archived by the owner on May 29, 2024. It is now read-only.

反転数アルゴリズムの安定性について #1630

Open
HotariTobu opened this issue Nov 9, 2022 · 0 comments
Open

反転数アルゴリズムの安定性について #1630

HotariTobu opened this issue Nov 9, 2022 · 0 comments

Comments

@HotariTobu
Copy link

反転数について、隣接互換との関係、分割統治法による数え上げ
こちらを拝見させていただきました。

マージソートをしながら反転数を数えるアルゴリズムのPythonによる実装で、11行目と32行目の比較の演算子を「<」ではなく「<=」にしなければ安定のソートにならず、返す反転数がソートするときの最小の交換回数にならないのではないでしょうか。

https://github.com/future-architect/tech-blog/blob/master/source/_posts/20210702a_%E5%8F%8D%E8%BB%A2%E6%95%B0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E3%80%81%E9%9A%A3%E6%8E%A5%E4%BA%92%E6%8F%9B%E3%81%A8%E3%81%AE%E9%96%A2%E4%BF%82%E3%80%81%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6%B3%95%E3%81%AB%E3%82%88%E3%82%8B%E6%95%B0%E3%81%88%E4%B8%8A%E3%81%92.md

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant