クイックソートとは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > ソート > クイックソートの意味・解説 

クイックソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/04/24 03:50 UTC 版)

クイックソート: quicksort)は、1960年アントニー・ホーアが開発したソートアルゴリズム分割統治法の一種。


出典

  1. ^ a b Hoare 1962.
  2. ^ Skiena 2008, p. 129.
  3. ^ Yaroslavskiy 2009.
  4. ^ a b c Sedgewick 2018, pp. 273–291.
  5. ^ Sedgewick & Wayne 2011, p. 295.
  6. ^ 杉山 1995, p. 159.

注釈

  1. ^ 「先頭未満/以上」で分割してしまった場合、無限再帰によるスタックオーバーフローも起こりうる
  2. ^ Cによる実装例。「再帰しないクイックソートの実装」の節を参照。


「クイックソート」の続きの解説一覧

クイックソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/07 20:45 UTC 版)

OCaml」の記事における「クイックソート」の解説

クイックソートのコード例を示す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」の概要を参照ください。

ウィキペディア小見出し辞書の「クイックソート」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



クイックソートと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

クイックソートのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



クイックソートのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのクイックソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、WikipediaのOCaml (改訂履歴)、Guarded Horn Clauses (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2022 GRAS Group, Inc.RSS