ビーズソート

ウィキペディア

ビーズソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/28 05:30 UTC 版)

ビーズソートまたは重力ソートとはJoshua J. Arulanandham、Cristian S. Calude、Michael J. Dinneenの3人によって2002年に発見されたソートアルゴリズムである。ヨーロッパ理論計算機科学会で発表された。ソフトウェアでの実装でも、ハードウェアでの実装でも時間計算量はO(n)であるが、特にソフトウェアでの実装では時間がかかることがあり、負の数のソートには使えないという欠点も持つ。また、少なくともこのアルゴリズムは空間計算量がO(n²)である。