エンジニア実践的基礎: バケットソート

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

バケットソートとは

バケットソートは値の範囲が限定されている場合に利用するソートアルゴリズムです。制限のないデータに対するソートは、クイックソートやマージソートが最速(O(nlogn))です。しかし、取りうる値の範囲が事前にわかっているなら、O(n) まで時間計算量を減らせます。これがバケットソートの強みです。

例えば、0 - 2 までのカードが重複を許して存在するとします。事前に値の範囲が 0 - 2 と決まっているので、