クイックソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/24 03:50 UTC 版)
クイックソート（英: quicksort）は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
出典
- ^ a b Hoare 1962.
- ^ Skiena 2008, p. 129.
- ^ Yaroslavskiy 2009.
- ^ a b c Sedgewick 2018, pp. 273–291.
- ^ Sedgewick & Wayne 2011, p. 295.
- ^ 杉山 1995, p. 159.
注釈
- ^ 「先頭未満／以上」で分割してしまった場合、無限再帰によるスタックオーバーフローも起こりうる
- ^ Cによる実装例。「再帰しないクイックソートの実装」の節を参照。
- 1 クイックソートとは
- 2 クイックソートの概要
- 3 アルゴリズム
- 4 最悪計算量の回避
- 5 実装例
- 6 脚注
クイックソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/07 20:45 UTC 版)
クイックソートのコード例を示す。MLは多くの関数型言語と同様、再帰処理に秀でる。また、Haskell などにも見られるパターンマッチの機能がここでも使われている。 let rec quicksort = function | [] -> [] | pivot :: rest -> let is_less x = x < pivot in let left, right = List.partition is_less rest in quicksort left @ [pivot] @ quicksort right
※この「クイックソート」の解説は、「OCaml」の解説の一部です。
「クイックソート」を含む「OCaml」の記事については、「OCaml」の概要を参照ください。
クイックソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/16 13:48 UTC 版)
「Guarded Horn Clauses」の記事における「クイックソート」の解説
与えられたリストのクイックソートを行うプログラム例を示す。part/4はリストをピボットより大きい数のリストと小さい数のリストの2つに分割する。2分割された各々のデータはそれぞれqsort/3でソートされる。 qsort([Pivot|Xs], Ys0, Ys2) :- part(Xs,Pivot, Small, Large), qsort(Small, Ys0, [Pivot|Ys1]), qsort(Large, Ys1, Ys2).qsort([], Ys0, Ys1) :- Ys0 = Ys1.part([X|Xs],Pivot,Small,Large) :- Pivot< X | Large=[X|L1], part(Xs,Pivot,Small,L1).part([X|Xs],Pivot,Small,Large) :- Pivot>=X | Small=[X|S1], part(Xs,Pivot,S1,Large).part([], _, Small,Large) :- Small=[], Large=[]. qsort/3を呼び出すことで順次part/4とqsort/3とのプロセスネットワークが作られ、それらの間で並行処理が行われる。このプログラムには以下の2種類の並行性が含まれている。 part/4が生成したリストを順次qsort/3でパイプライン的に処理 2分割された各々のデータのqsort/3による並行処理 part/4は先頭から順番に大小のリストを作成していくが、qsort/3はリスト全体の作成を待つことなく先頭の値が決まったものから順次処理を行う。また、大きい数のリストと小さい数のリストはそれぞれ並行して処理され、次のpart/4とqsort/3の処理が行われていく。逐次処理言語に並行実行の機能を追加した多くの並行プログラミング言語と異なり、GHCではプログラマーが特に指定しなくてもアルゴリズム自身が持つ並行性が自然に表現できる。
※この「クイックソート」の解説は、「Guarded Horn Clauses」の解説の一部です。
「クイックソート」を含む「Guarded Horn Clauses」の記事については、「Guarded Horn Clauses」の概要を参照ください。
クイックソートと同じ種類の言葉
- クイックソートのページへのリンク
