読者です 読者をやめる 読者になる 読者になる

asaのブログ

プログラミングの勉強まとめ

ソートアルゴリズム(クイックソート)

  集合と文字列検索があっさり終わって、現在リストに入ってます。だいぶ前にやった感がありますが、クイックソートをまとめました。参考書は変わらず『明解Javaによるアルゴリズムとデータ構造』を使っています。

 

明解Javaによるアルゴリズムとデータ構造

明解Javaによるアルゴリズムとデータ構造

 

 

 クイックソートは、配列をある基準値(枢軸)をもとにそれ以下のグループとそれ以上のグループへ分割していきます。分割を繰り返して、すべてのグループが1つの要素しか持たなくなったとき、ソートが完了します。


配列の分割
 まず、配列を分割する方法を確認します。

gist6c121a376139b72d02669378a8d4f4d5


 配列を左端から走査するpl(左カーソル)と、右端から走査するpr(右カーソル)を使用します。枢軸をxとすると、xの左側にはx以上の要素があってほしくなく、xの右側にはx以上の要素があってほしいです。


 そこで、plが左から走査を続けてx以上の要素を発見すると、同じく右から走査してきたprが発見したx以下の要素と交換します。plとprはこうして交換続け、どちらかがあるいは同時に枢軸に行き当たると、最後の交換を行って値を更新し、走査をストップします。

 do文の中に2つのwhile文があります。1つめのwhile文は左からの走査、枢軸以上の値が見つかるまではplをインクリメントしてカーソルを移動させます。

 x以上の値が見つかると1つ目のwhile文を抜け、2つ目のwhile文に入ります。prは枢軸以上の値を発見するまでデクリメントされ、カーソルを左へと移動させます。x以下の値が見つかると、次のif文に移ります。if文では、左からの走査であるplが右からの走査であるprを越えていない限り実行されます。

 

 今、plは配列の左側にあるx以下の要素のインデックスをさし、prは配列右側にあるx以上の要素のインデクッスをさしています。これを交換させた後、plをインクリメント、prをデクリメントしてカーソルを移動させておきます。


 plがprを越えない限りこの走査は実行され、最後に枢軸に行き着いて、交換、カーソルの値の更新をしてdo文が終わります。

 結局、配列(arrとします)は
1.枢軸以上・・・arr[0]~arr[pl - 1](カーソルは枢軸を越えて交差しているので1引く)
2.枢軸以下・・・arr[pr + 1] ~arr[ arr.length - 1] (同じく枢軸を越えて交差しているので1足す)
と交差した後の左カーソルplと右カーソルprの間に複数の要素がある場合(pl > pr + 1)
3.枢軸と等しい・・・arr[pr + 1]~arr[pr - 1]
に分割されます。

クイックソート
 この配列の分割を要素が1つになるまで続けたのがクイックソートです。左のグループと右のグループで再帰的にメソッドを呼び出してソートを行っています。

gist964148fed14a8b177d6e3966779727c5


きれいに並べられます(^^)

ソートアルゴリズム(バブルソート)

 今日は、タイトルにあるソートを勉強しました。単純選択ソートとシェルソートまで進みましたが、ずらずら書くと冗長なので今回はバブルソートをまとめました。参考書は『明解javaによるアルゴリズムとデータ構造』です。

 

明解Javaによるアルゴリズムとデータ構造

明解Javaによるアルゴリズムとデータ構造

 

  

 バブルソート

 配列を昇順に並び替えます。走査は末尾からスタートします。隣り合う要素を比較して先頭側が大きければ(昇順なので)後ろの要素と交換します。

 参考書では配列の要素を入力させていましたが、やや面倒だと感じたのでmakeArrayメソッドを使って配列を作成しています。配列の確認は頻繁に行うのでcheckArrayメソッドを使いまわしています。swapとbublesortメソッドが今回の本体になります。

 

 最初 i = 0からスタートします。j は末尾からのスタートです。末尾とその前の要素を比較して、前の要素が大きければ交換します。j はデクリメントされて、次に末尾の一個前の要素とその前の要素を比較します。これは今、i = 0 なので、配列の先頭まで繰り返されて、最小の要素が先頭に来ます。

 j のループが回って、i がインクリメントされると i = 1となります。j の方の for 文は j > iとなっているので、末尾から2番目の要素までを比較して、2番目に小さい要素が先頭の次にやってきます。

 i は配列の末尾の1個手前までやって来て、ネストされているfor文で末尾とその手前の要素が比較されると j = n - 2、i = n - 2となり、ネストされたfor文を抜け、i も n - 1となりfor文を抜けます。

 終わってみると、配列は無事に昇順に並んでいます。

オークション関連文献(1)とJavaによる実装(目標)

 オークション関連の名著を(自分でも忘れやすいので)何本かづつまとめていきたいと思います。

 これらで紹介されているオークションをJavaで実装することが当面の目標です。

 

 オークション関連文献(1) 

 オークション関連の論文・著作は数多くありますが、今回は自分の知ってる範囲で有名なものを紹介します。読んでいるといろんなところでオークションが使われているのが分かったり、オークションの利点や欠点を指摘しています。

 オークションの仕組みは抽象化するとメカニズムデザインにつながっています。なのでなんらかの仕組みを抽象化した後、オークションの仕組みで実装することができます。

 今回は2本。下の文献はオークションの仕組みを学んだり実装するときの基礎になるものです。ググッても直接的には見つからないので結構探すのは大変です。

 

 1.William Vickrey(1961) "Counterspeculation and competitive sealed tenders "

  オークション研究の嚆矢。レジェンド・オブ・レジェンドとはまさにこれです。この論文ではじめてオークションが理論的に分析されました。

 これまで未開拓だったオークションという領域を、手練手管で分析しています。後半になると、分析が複雑になり完全に解くことができないことが明らかになるのですが、それでもなんとか結論を出しています。

 Vickreyのこの研究が花開くのはこれからさらに20年後になります。その後、それまでの研究が総合され、きれいな数式で理論が解説されるようになりました。自分が最初に読んだ英語の論文で、数式が扱いやすいので今もVickreyの方を結構使います。

 

 2.Ralph Cassady(1967) "Auctions and Auctioneering"

 Cassadyが世界中のオークションを長年に渡って見て回り、それをまとめたものです。バビロニア時代のオークションから、当時のオークションまで幅広く紹介しています。日本のオークションも紹介されています。

 バビロニアでは年頃の女性はオークションにかけられて、旦那さんを決めていたそうですよ(詳しくは後のブログで)。ヘロドトスを読んでいた人は知っているかもしれません。

 Cassadyのこの本は、直接今のオークション理論に絡みませんが、一回じっくり読みたかったので、これは今後少しづつ訳して紹介していきたいと思います。

 

 オークションの実装(目標)

 オークションには種類がたくさんあるのですが、大別すると基本4種に落ち着きます。基本4種は、English-Auction、Dutch-Auction、First-Price Sealedbid Auction、Scond-Price Sealedbid Auctionと呼ばれます。

 English - Aucutionはヤフオクなどでも使われている競り上げ式のオークションのことです。Dutch - Auctonは魚の競りに使われるような、高い値段から下げていくオークションで、すぐに入札が終了するのが特徴です。

 後の2つは一般に封印入札と呼ばれるオークションで、公共団体の入札に使われますね。第2価格ルールはeBay等で使われています。

 まずは、これらの基本4種を実装していくことが当面の目標です。暖かい目で見てやってください_( .  . )_。

 

 

AtcorderBiginerContest056のD問題

 題名の通り、この前あったAtcorderの大会のD問題を『みんなの回答』から解説してみました。公式回答とは若干違いますが、答えを導けます。

 

gist7379266b326379cf4829408d2982c9d4