クイックソートしながら重複要素削除アルゴリズム

アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ
ている物が多く処理のイメージが沸かずクイックソートもコピペや既存
の関数で処理していて、満足に理解出来ていないのですが。
以下の問題を、お解かりになるかた教えて頂けませんでしょうか？

■問題
2万件位の数値データの中から重複要素を削除しながら昇順または降順で、
ソートするアルゴリズム(※１)

■条件
BASIC的(※２)な記述やプログラム中のコメントなどの形式でも構いま
せん出来るだけ簡単に示して頂けると助かります。

補足
(※１)ソートする際、重複要素を消すともっと処理が早くなるのではと
思ったので。
目的は、処理の速さを求める事と、次回から応用が聞くよ
うにソート自体を理解したいのでクイックソートで無くても構いません。

(※２)実際に動かなくても構いません、イメージが掴みやすい方が良いと
　　　いう意味でとって下さい。

No.8 ベストアンサー 回答者： stylePET 回答日時： 2007/06/15 14:49

>pythonで実行してみたのですが、うまく行きませんでした。

>2行目のＩｆ文でエラーが出るようです。
投稿するとインテンドがきえてしまいました。以下のタブをタブに替えてください。
def qsort(list):
タブif len(list) != 0:
タブタブlt_list = [x for x in list if x < list[0]]
タブタブgt_list = [x for x in list if x > list[0]]
タブタブreturn qsort(lt_list) + [list[0]] + qsort(gt_list)
タブelse:
タブタブreturn []

>他の言語で置き換えようと調べてみたのですが、
>以下の解釈が解からないためよろしければ、教えて頂けるとありがたいのですが。
>3行目、4行目→x for x in list if x
これはpythonのリスト内包表記といって配列の中からある条件の配列を取り出しています。
gt_list = [x for x in list if x > list[0]]
はＶＢでいうと
for each x in list
if x > list(0) then
gt_listにx追加
end if
next
と同じです。
>ちなみに、以下は
>qsort(lt_list) + [list[0]] + qsort(gt_list)
>ソートと重複削除済みのリストが戻されると解釈して良いのでしょうか？
そうです。[list[0]]にはひとつしか値が入らないし、
lt_list,gt_listにもlist[0]と同じ値は入ってませんよね。

この回答へのお礼

有難うございます。
教えて頂いた、通りで解決しました。

お礼日時：2007/06/23 14:43

No.7 回答者： stylePET 回答日時： 2007/06/14 16:33

クイックソートで同じもののリストを真ん中で足さずに

ひとつだけにしてつなげれば、そのまま重複削除になります。
pythonの例です。

def qsort(list):
if len(list) != 0:
lt_list = [x for x in list if x < list[0]]
gt_list = [x for x in list if x > list[0]]
return qsort(lt_list) + [list[0]] + qsort(gt_list)
else:
return []

samplelist=[8,4,5,2,4,7,8,4,4,1]
print qsort(samplelist)

ここで以下はlist[0]よりも小さい値を集めた配列です。
[x for x in list if x < list[0]]

この回答へのお礼

有難うございます。
pythonで実行してみたのですが、うまく行きませんでした。
2行目のＩｆ文でエラーが出るようです。
他の言語で置き換えようと調べてみたのですが、
以下の解釈が解からないためよろしければ、教えて頂けるとありがたいのですが。
3行目、4行目→x for x in list if x

ちなみに、以下は
qsort(lt_list) + [list[0]] + qsort(gt_list)
ソートと重複削除済みのリストが戻されると解釈して良いのでしょうか？

お礼日時：2007/06/15 13:22

No.6 回答者： Oh-Orange 回答日時： 2007/06/14 10:53

★ソート後について

・重複チェックは２万件のデータを１回順番に調べ重複した値は 0 に書き換えます。
　２回目のシークで 0 以外は詰める処理を行えば良いでしょう。
　こうすれば重複するたびに削除詰めしなくて良いので早くなります。
・なお、この場合は２万件のデータで 0 という値が無いことが前提です。ある場合は
　ソートの最初が 0 ならゼロ有無フラグを ON にして削除詰めの時に最初の 0 は詰めない
　ように工夫すればよい。その他、数値データで絶対利用しない値を『重複』で削除用の
　値に使えば良い。
・以上。

この回答へのお礼

お陰様で、アルゴリズムの方も理解できそうな所まで来ました。

>こうすれば重複するたびに削除詰めしなくて良いので早くなります。削除詰めの回数を減らせば良いのですね。
どういった処理が遅くなるのか解かっていませんでした。

> 0 という値が無いことが前提です。
0と言う値はありますがある事が解かっているので消しても構いません
後から付け足せます。

>★ソート後について
と言う、事なのですがソート前では、無いのでしょうか？
どちらにしろ、今のレベルではアルゴリズムをソートと重複
削除に別けるしか無いようですね。

結果を報告できればと思いますので、
このスレは、2～3日締め切りせずに置いときます。

有難うございました。

お礼日時：2007/06/14 13:54

No.5 回答者： Tacosan 回答日時： 2007/06/13 21:05

クイックソートを前提にすると, 「分割するときにピボットと同じ値がいたら消す」という処理と「部分列のソートが終わったあとで詰める」という処理をしなきゃならないですね. 素直に「単純にソートしてから重複した要素を消す」のとあんまり処理時間はかわらないような気がします. 下手すると, 移動時間が増える分だけ処理時間が長くなる可能性があります.

「ソートしつつ重複要素を消す」のなら, 一番簡単なのはマージソートじゃないかなぁと思います. マージするときに「同じ要素があったら一方を捨てる (もう一方は自動的に移動すればよい)」だけで済むので. もっとも, 配列でマージソートをしようとするとメモリを使う可能性があるのでリストの方が安全な気はします.
ヒープソートも, ちょっと今一つって感じがします. クイックソートと同様, 「不要になった要素を捨てて残った要素を詰める」処理がどのくらい時間を使うかの勝負です.
う～ん, やっぱり「後処理として重複した要素を消す」のが安全な気がします.

この回答へのお礼

ありがとうございます。

>「後処理として重複した要素を消す」のが安全な気がします
なるほど、どちらに組み合わせた物をつくってみて、
その上でパフォーマンス改善を考えてみたいと思います。
現状
言葉では、解かっているつもりなのですが、プログラムが正しく
動きません＾＾；

まずは、マージソートだけに絞ってみます。

お礼日時：2007/06/13 23:09

No.4 回答者： don_go 回答日時： 2007/06/13 02:15

1)数値データテーブルと同じサイズのフラグ用テーブル

を準備して通常のソート手順でソートを行い、フラグ用
テーブルの並べ替え処理も同時に行う。
2)比較時に数値の値が同じ且つフラグ用テーブルの値が
共に初期値の場合には、片方に削除フラグをセットする。
3)ソート終了後にフラグ用テーブルに値がセットされて
いないのと同じ添字の数値データのみを出力。

この回答へのお礼

具体的な手法を提示して頂きありがとうございます。

しかし、現時点私の理解度では何故そうするのか？
どのソート法に対しての回答かすら解かっておりません。

ソートと重複処理を分けて考える手もあるのですが
重複処理を組み合わせるとアルゴリズム自体の構造が
変わってしまう気がして二つの問題を組み合わせた
プログラムを動作検証をして理解したいのですが。
よろしければ、引き続きご教授下さい。

お礼日時：2007/06/13 11:15

No.3 回答者： rabbit_cat 回答日時： 2007/06/13 01:35

＞重複判定とソート２つの比較演算を同ループ内で行うと

＞スワップ回数が減らせて処理が少なくなるとイメージしたのですが、
まさに、その通りでして、それを行うには、＃１で書いたように、ソートのアルゴリズムを、ヒープソート、マージソート等にする必要があります。

ソートのアルゴリズムとしてクイックソートを使うと、重複判定とソートを同時に行うことができません。（できませんはいいすぎか。少なくともかなり厄介になると思います。）

まずは、いろいろなソートのアルゴリズムを勉強されてはどうでしょうか。

http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC% …
http://www1.cts.ne.jp/~clab/Contents/Sortindex.h …

この回答へのお礼

度々、ありがとうございます。
アルゴリズムが理解できなかったので(解かってるような解かってい
ない様な)、コードを入力して動作検証したいと思っていたのですが。
C言語が使えないため、ベーシックのフローを頂けると自作できると
考えて投稿したのですが。
　
>厄介になると思います。アルゴリズムの比較演算のパターンを
　改良しないといけないと言うことですね、確かに複雑そうです。

クイックソートが一番早いと思いますのでクイックソートで実現した
かったのですが、今のレベルでは無理そうです。
教えて頂いた、マージソートやヒープソートも解説見たのですが、
やはり、自己でコードが組めず動作検証まで至っておりません。

何処が解かっていないかも、うまく説明できませんが、
標準的な「BASICコード」なら動作イメージが出来ますので、
図々しいお願いですが、教えて頂けませんでしょうか。

●重複処理の部分はこんなイメージですが

for i = 0 to 最大配列数 - 重複回数
　while data[i] = data[比較対象データポインタ]　　　　　　　　 //重複が無くなるまで
　　data[比較対象データポインタ] = data[最大配列数] 　　　//最後尾と入替
　　data[最後尾] = null　　　　　　　　 　　　　　　　　　　　　　　　 //重複内容削除
　　重複回数 = 重複回数 ＋１　
　end-while　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//重複判定ここまで
　ソート処理　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　// ※ヒープ？マージ？
　i = i + 1
next

お礼日時：2007/06/13 10:51

No.2 回答者： rabbit_cat 回答日時： 2007/06/12 23:25

＞以下の処理では、動かないですかね、

もちろんＯＫですけど、「重複判定」てのはどうやるつもりですか？
ｎ番目の要素が重複要素かどうか調べるには、もっとも単純にやれば、1番目からn-1番目の要素を全て調べる必要があります。
これをやるのは、ほとんどソートするのと同じくらい大変です（処理時間がかかる）

この回答への補足

我ながら、意味が不明だったので補足させてください。
※重複判定とソートのループを組み合わせる。
重複判定とソート２つの比較演算を同ループ内で行うとスワップ
回数が減らせて処理が少なくなるとイメージしたのですが、
そういった、問題ではないのでしょうか？

ソートのアルゴリズムが頭に入っていないので、なにを言ってるの
的な質問になってたら申し訳ありません。

補足日時：2007/06/12 23:56

この回答へのお礼

>「重複判定」てのはどうやるつもりですか？
重複判定とソートのループを組み合わせる(同じループ内で)、
アルゴリズムて出来ませんでしょうか？

お礼日時：2007/06/12 23:54

No.1 回答者： rabbit_cat 回答日時： 2007/06/12 02:36

＞重複要素を削除しながら

これは大変そう。
クイックソートだと、削除した要素の分の空き詰めるのは難しそうです。分割統治なんで、自分と関係ない部分でいくつ要素が削除されたかを知る方法がない。

速いソートが望みなら、マージソート、ヒープソート等であれば、重複用の削除をしても、それほど処理に影響を与えないでできると思われます。

この回答へのお礼

>クイックソートだと、削除した要素の分の空き詰めるのは難しそうです。

以下の処理では、動かないですかね、ソートのアルゴリズムが解からない
のでテストできませんが、重複判定をして最後尾の内容と入れ替えるから
先に進めません。

for i=0　to　(初期の要素数-重複回数)　←ここは、ループ中に変更出来ない？
　　重複判定(重複なら配列の最後尾の内容とスワップ)
　　重複回数　カウンター
　　配列最後尾要素削除(言語によると思いますが。)
　　ソート
next
↑↑
ソート(アルゴリズム不明の為入れ子になるかもしれませんが）
※追記で申し訳ありませんが、配列の要素と中身は、
対応してなくて良いため、この様に処理は出来ないでしょうか？

お礼日時：2007/06/12 11:11