124日目です. いよいよ7月ですね. もうすぐ帰ります.
今日も1日ニートでした. 本読んでました.
明日こそは出掛けたいのと, 今頭痛いので軽くまとめて終わりにします.
読んだ内容だけ..
クイックソートと計数ソートです.
クイックソートはある要素よりも小さい領域と大きい領域に分けて, 分かれた領域内のある要素より~~を続けるソートです.
ある要素をどこにするかが肝になってる(って習った覚えがある)ので, 単純に中央値にしてしまうと最悪計算量になってしまう可能性があります. (最悪計算量になる要因これじゃなかったような.)
要はパーティションの再帰ですね. パーティションは配列の最後の要素を基準に取ります. 実際にクイックソートを書いてるとパーティションの再帰で実装した方がシンプルに書けました.
次に計数ソートは, ソートしたい配列のそれぞれの要素より小さい数字の個数をカウントし(カウンタ配列を作る), 出力する配列に後ろから順に配置していくだけです.
簡単な話, "10"より小さい数字が"4つ"あるなら, "10"は"5番目"に配置されるということです.
順に読み進めてると, やはりありました. C++でSTLとして既に実装されているソート関数.
Pythonもそうですが, 標準でソートが実装されてると楽なんですがどういう風に動いているのか知りたいならちゃんと勉強する必要がありますね.
sorted(dict.items(), key = lambda x : x[1])
みたいなのも知ってるとスマートですが, 自分で実装してみるのも楽しいです.
明日はAtcoderですよね..? 時間的に出先なので参加できませんが, どんどんやって行きたいと思います. せっかく勉強してるので.
では.
