ここから本文です

<lisp関連です>loopを使った選択ソートのプログラムがどう動いているか、どうい...

t09********さん

2010/11/1204:02:57

<lisp関連です>loopを使った選択ソートのプログラムがどう動いているか、どういうことをしているかがよくわかりません。

ごちゃごちゃしてて初心者の僕には頭が痛いです。

どなたか選択ソートについて詳しい方いませんか?ぜひ説明をお聞かせください。
よろしければ、選択ソートがどういう場面で使われてるかもお聞かせください。

#例:

(defun selection-sort (X)
(let ((sorted-list nil) (next))
(loop
(cond ((null X) (return sorted-list)))
(setq next (select-lowest X))
(setq sorted-list (append sorted-list (list next)))
(setq X (remove-first next X)))))

(defun select-lowest (X)
(let ((lowest (car X)))
(setq X (cdr X))
(loop
(cond ((null X) (return lowest))
((< (car X) lowest) (setq lowest (car X))))
(setq X (cdr X)))))

(defun remove-first (X Y)
(let ((Z nil))
(loop
(cond ((null Y) (return Z))
((equal X (car Y)) (return (append Z (cdr Y)))))
(setq Z (append Z (list (car Y))))
(setq Y (cdr Y)))))

# 実行例

>(selection-sort '(8 3 4 6 3 9))
(3 3 4 6 8 9)

この質問は、活躍中のチエリアン・専門家に回答をリクエストしました。

閲覧数:
664
回答数:
2
お礼:
50枚

違反報告

ベストアンサーに選ばれた回答

biw********さん

編集あり2010/11/1605:33:43

選択ソートと云うのは、最大値又は最小値を検索し、それを「選択的に」抜き出す事でソートする技法です。
処理時間は、データ内容に殆ど依存せずに、常時データ数の二乗の時間が掛かります。
データ数が増えると急激に遅くなりますが、データ数が少ない場合には、アルゴリズムが簡単なので、無駄が少なく、実質最速になることも珍しくありません。
少ないデータをほぼ等時間でソートしたい用途で使用されます。

余談ですが、同様に「手順が簡単なので少数データでは高速」なソート技法に「バブルソート」があります。
こちらは、工夫すると「殆どソート済み」のデータでは最速になり得ますが、「逆順に並んだデータ」では逆に最遅のアルゴリズムになります。
選択ソート以上に少ない変数で記述出来るので、ソート済みでも速くない簡易版が入門用途で良く使用されます。
また、使用変数が少ないので、データ数が極端に少ない場合は、逆順でも最速になり得ます。

尤も、Lispでは、処理系自体が複雑なので、単純にどれが最速かは判断が難しいです。

で、質問にあるソースでは、下記の処理をしてます。
0. ソート済みリストを格納する空のリストを生成
以下主loop内
1. ソートする残りのリストがなくなればソート済みリストを返して終了。
2. ソート対象リストX内の最小値を求め、nextに格納
3. 最小値をソート済みリストの末尾に追加
4. ソート対象リストから、最初の最小値を削除
以上を繰り返し。

関数remove-firstの命名がちょっと厭らしいですね。
最初に見つけた「特定の値」を削除する関数なので、何か紛らわしいです。
(でも先頭を取り除くだけならcdr一発だからlisp的には妥当なのかな?)
4.の「最初の最小値」は、同じ値が複数在る場合の「最初」です。

手順は、概ね、選択ソートの基本どおりですね。
ソート対象のリストXの「残りの最小値」を抜き出しているので、Xからは小さい順にどんどん消えて行き、全要素が一度「最小値」になって、ソート結果に追加されます。
最小値の検索や削除にもloopを使用しているので、二重ループ構造になっていて、処理回数がデータ数の二乗回(正確にはその半分)になります。

select-lowestは、如何にもlispっぽいですね。
carに先頭データが入っていて、cdrに残りのリストが入っているのがlispのリスト構造です。
(再帰ではなくloop文を使うのは、ちょっと「らしくない」ですが)
setqは、lispの例外的記法で、通常の言語の代入文に相当します。
やや無駄気味にlist関数が入っていますが、append関数ではリストしか追加出来ないので、無理気味にリストを作ってます。
(そもそも、リスト末尾にはnilが必要なので、どのみちlist関数が必須なのですが)
括弧がやたら出てくるのはlispの宿命なので諦めまて慣れましょう。

C言語等の低水準記述言語では、「最小値の場所」も同時に記録して、二度目の検索を省略するのですが、lispだとこんな所ですかねぇ。

でも、最後のremove-first関数は、loopを使っているので無駄にappendしまくってる感があります。
生のappendは、毎回新規にリストを作る関数なので遅い筈で、再帰でループさせるとappend不要なのですが。
(最近の処理系だとそうではないのかも)

おまけで、再帰を使ったremove-firstも書いてみますね。
(即興なのでミスはご容赦)
(defun remove-first (X Y)
(cond
((null Y) Y)
((equal X (car Y)) (cdr Y))
(t (cons (car Y) (remove-first X (cdr Y)))))

質問した人からのコメント

2010/11/16 20:00:42

降参 ご丁寧に回答いただきありがとうございました。
とても勉強になりました。

ベストアンサー以外の回答

1〜1件/1件中

tar********さん

編集あり2010/11/1204:24:10

まずは名前から推測します

(selection-sort X)がやっていることは
Xが空リストになるまで,
nextをXの中で最小の要素にして(select-lowest)
sorted-listの最後尾にnextを追加して(append)
Xからnextを取り除く(remove-first)
という作業を繰り返して, 最後にsorted-listを返しています

つまり
sorted-listへ小さい順にXの要素を入れていくイメージです


実際
(select-lowest X)は, Xの最小の要素を返す関数ですし
(remove-first X Y)は, Yの中で一番手前にあるXを削除して, 削除した後のYを返す関数です

例えば
(select-lowest '(1 2 3 2 1))
(remove-first 2 '(12321))
の結果はそれぞれ
1
(1 3 2 1)
になります

ですので
selection-sortがやっていることは, 最初の推測のとおりです

あわせて知りたい

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる