現在、Lisp や DrScheme などの関数型言語を学習中ですが、DrScheme で Quicksort アルゴリズムのバリエーションを書くように依頼されました。しかし、私はどこから始めればいいのか少しわかりません。
どの関数とデータ型を使用するかについて、誰かが私にいくつかの指針を与えることができますか? リスト、car、cdr、および append が何をすべきかについて大きな役割を果たすことは明らかです。
ところで、私は本当に出発点となる一般的なアイデアだけを探しています。私は必ずしも完全な答えを求めているわけではありません。冒険と楽しさを台無しにするようなものです！
クイックソートは、機能的なスタイルで実装される最も単純なソート アルゴリズムの 1 つです。必要なデータ構造は標準の Lisp リストだけであることに注意してください。
quicksort(lst)
if lst is empty
return empty list
return quicksort([all the elements < first element in lst])
+ [first element in lst] +
quicksort([all the elements >= first element in lst])
リスト内の最初の要素よりも小さいすべての要素 (またはそれ以上のすべての要素) を取得するという「トリッキーな」部分は、filter手順の観点から簡単に表現できます。使用が許可されていない場合でも、基本的な機能をゼロから簡単に実装できます。
また、私の疑似コードの演算子は、リストの最初の要素より小さい要素のリスト、リストの最初の要素を持つシングルトン リスト (ピボット)、およびそれ以上の要素のリストの 3 つのリストの 1 つ+を表していることに注意してください。appendリストの最初の要素に。
クイックソートの実際の実装では、適切なピボット要素を選択する際により多くの注意が払われますが、この単純な例では、最初の要素を取得するだけで十分です。