💎

Rubyのソートアルゴリズムについて

2023/08/08に公開

こんばんは、素敵な夜ですね。Rubyのソートアルゴリズムについて気になり、できる範囲で調べたので、自分用のメモを残します。

2.7.8

https://github.com/ruby/ruby/blob/v2_7_8/array.c
https://github.com/ruby/ruby/blob/v2_7_8/util.c

3.2.2

https://github.com/ruby/ruby/blob/v3_2_2/array.c
https://github.com/ruby/ruby/blob/v3_2_2/util.c

qsort_r、qsort_sについて

https://www.aihara.co.jp/~taiji/tp/?id=12
https://learn.microsoft.com/ja-jp/cpp/c-runtime-library/reference/qsort-s
http://www.kumei.ne.jp/c_lang/intro2/no_137.htm

結論

見る場所があっていればクイックソート。
コンパイラオプション次第で既存のものが使用される可能性有(ruby_q_sortが宣言され分けている)。
その使い分けはわからない。
そちらの内部もわからない(調べた範囲だと、どうも環境によってはqsortといいつつそもそもクイックソートでなかったりする模様)。

ご指摘・ご補足頂けますと幸いです。

Discussion