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

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文を抜けます。

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

AtcorderBiginerContest056のD問題

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

 

gist7379266b326379cf4829408d2982c9d4