4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

スターリンソート?

4
Last updated at Posted at 2019-07-31

計算量O(n)で噂のスターリンソートを実装してみた
https://qiita.com/MeilCli/items/721526d716851e92192a

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell
https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2

↑ここら辺を読んで、提唱者のページを見たんだが、

stalin-sort - github
https://github.com/gustavo-depaula/stalin-sort

You iterate down the list of elements checking if they're in order. Any element which is out of order is eliminated.

javascript版は少なくともこの定義に従っていない。

function stalinSort (array) {
  const sorted = [array[0]];
  for (let i = 1; i < array.length; ++i) {
    if (array[i] >= array[i-1]) {
      sorted.push(array[i])
    }
  }
  return sorted
}
module.exports = stalinSort

こうするのが正では?

const trueStalinSort = (array)=>
  array.filter((e,i,arr)=>arr.filter((o,j)=>j<i).filter(o=>o>e).length==0)
;

module.exports = trueStalinSort

追記:
配列のprototypeに突っ込むとこうなる。

Array.prototype.stalinSort = function(sort=(p,c)=>p>c){
  return this.filter((e,i,arr)=>arr.filter((o,j)=>j<i).filter(o=>sort(o,e)).length==0)
};

const arr = [2,1,5,3,4,1,2,3];

console.log(arr);

console.log(arr.stalinSort());
console.log(arr.stalinSort((p,c)=>p<c));

追記2:
O(n)を実現するならこっちかな。

Array.prototype.stalinSort = function(sort=(a,b)=>a>b){
  const sorted = [];
  for (let i = 0; i < this.length; i++) {
    if (sorted.length && sort(sorted[sorted.length-1],this[i]))
      continue;
    sorted.push(this[i]);
  }
  return sorted;
}
4
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?