三区分割クイックソートと挿入ソートのハイブリッド実装
クイックソートは平均計算量が O(n log n) である一方、ピボット選択が悪い場合に最悪 O(n²) に退化する。本稿では、Java で実装可能な高速化テクニックを段階的に紹介する。
1. 単純な二方向分割
ピボットを末尾に固定したまま、slow / fast という２つの走査ポインタを使って「ピボット未満」を左に集める手法。
static void basicQuick(int[] a, int lo, int hi) {
...
7月5日 18:24 投稿
整数配列のソート実装：複数アルゴリズムによる昇順整列化
問題概要
非負とは限らない整数からなる配列 nums が与えられる。この配列を昇順に並べ替える関数を実装する。制約条件として、配列長は最大で 50,000、各要素の値は -50,000 から 50,000 の範囲内である。
基本的なソート手法
バブルソート（改良なし）
隣接する要素を比較し、必要に応じて交換を行うことで、毎回最大値が末尾に移動する。このプロセスを繰り返す。
pub ...
6月14日 23:21 投稿
基本的ソートアルゴリズムと応用問題の実装例
概要
本稿では、競技プログラミングやコーディングテストで頻出する「ソート」を中心とした 4 問の解法を紹介する。各問とも標準的なアルゴリズムを用いることで簡潔に解けるため、実装テクニックを押さえておくと非常に有利である。
問題 1：単純な昇順ソート
問題文
整数列が与えられる。昇順に並べ替えて出力せよ。
解法
要素数が 105 程度であれば、単純な挿入ソート ...
5月18日 14:38 投稿