【PHP】のスターリンソートがけっこうそれっぽい

著者:杉浦

【PHP】のスターリンソートがけっこうそれっぽい

 スターリンソートとはジョークソートアルゴリズムの一つです。

I came up with asingle pass O(n) sort algorithm I call StalinSort.
You iterate down the list of elements checking if they’re in order.
Any element which is out of order is eliminated.
At the end you have asorted list.
gustavo-depaula/stalin-sort: Add a stalin sort algorithm in any language you like ❣️ if you like give us a ⭐️

 スターリンソートは、要素を先頭から順番に見ていき、ソートされていない要素を発見する度に粛清することによって昇順ソートを実現します。全要素を一つずつ見るだけなので計算量はO(n)であり、高速です。

3, 6, 2, 1, 7, 10, 1, 10
↓
3, 6,       7, 10,    10
↓
3, 6, 7, 10, 10

 アルゴリズム完了時に昇順で要素が並んでいるので昇順ソートと言い張れます。入力時から要素が減っていようと昇順ソートです。(ソートの要件満たしていないし実際にはフィルターに分類されます)
 多くの言語は配列を詰めていくのでスターリンソート完了時には粛清された要素なんて最初からいなかったと思わされます。

 ですがPHPはそうなりません。

 PHPの配列は順番づけられたマップに過ぎず、キーと値はがっちり結びついており、配列が詰められることはありません。そのため次の様なことにもなります。

 紐づいた値に基づいて複数の名前が消されました。消された要素は戻ってきません。

  • この記事いいね! (0)

著者について

杉浦 administrator