sort: improve average quicksort performance · golang/go@6f6b2f0
- change way of protection from O(N^2) on duplicate values. Previous algorithm does additional comparisons and swaps on every split pass. Changed algorithm does one ordinal quicksort split pass, and if distribution is skewed, then additional pass to separate pivot's duplicates. Changed algorithm could be slower on very ununique slice, but it is still protected from O(N^2). - increase small slice s
クイックソート - Wikipedia
クイックソート（英: quicksort）は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 個のデータをソートする際の最良計算量および平均計算量は （ランダウの記号）である。他のソート法と比べて一般的に最も高速だと言われている[2]が、対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はである。安定ソートではない。 クイックソートは以下の手順で行われる。 ピボットの選択：適当な値（ピボット（英語版）という）を境界値として選択する 配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する 再帰：分割された区間に対し、再びピボットの選択と分割を行う ソート終了：分割区間が整列済みなら再帰を打ち切る 配列の分割方法の一例として、以下のようなものが考えられる： 配列要素からピボット P
Elixir のリスト内包表記でクイックソート - Qiita
Elixir にはリスト内包表記という記法があり、これを使うとリストに対して 任意の条件でフィルタリング 別の値へのマッピング というよくある操作を簡潔に記述できる。 http://elixir-ja.sena-net.works/getting_started/18.html 例 iex> for n <- 1..10, rem(n, 2) == 0, do: n * n [4, 16, 36, 64, 100] これは 1 〜 10 の値のうち偶数の値の自乗を求めている。このように Elixir ではリスト内包表記は for で始まる式になるようだ。 このとき n <- [1 .. 10] が生成器 (generator) : 入力になるリストの指定 rem(n, 2) == 0 がフィルタ : リストに対してこの条件でフィルタリングする n * n が構築子 (constructor
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
