計算量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;
}