UdemyのAndrei Neagoieさんのコース Master the Coding Interview: Data Structures + Algorithms を参考にしています(オススメです).SortingのSectionを終わったので忘れないうちにメモ。
自分は式とかコードよりも図で覚えるタイプなので各アルゴリズムのイメージを図を書いて覚えようという試みです(コードはググればたくさん記事が既にあったので載せてません)。
全体のまとめ
Big OはBig-O cheat sheetを参考にしています。このサイトはSort以外にも各Data StructureのBig Oについても記載があります。
基本的には
- 最悪のケースを想定しなくてもいいなら 早くてメモリ消費の少ない
quick - メモリーを使ってもいいなら安定の
merge - インプットが小さい or ほとんどSortされているなら
insertion -
bubble,selectionは実装は簡単だけど効率は良くない
