スターリンソートをJavaで実装してみた

概要

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる

— やんぎん (@4116You) 2019年7月28日

Javaでこれを実装してみます。
Kotlinは既にあったけど、やりたかったのでやりました！

引用元

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell

ソースコード

StalinSort.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class StalinSort {
    public static void main(String[] args) {
        Integer[] data = {1,3,4,2,3,7,3,9};
        Integer tmp = data[0];
        List<Integer> index = new ArrayList<Integer>();

        for (int i = 1; i < data.length; i++) {
            if (tmp > data[i]) {
                index.add(i);
            } else {
                tmp = data[i];
            }
        }

        List<Integer> list = new ArrayList<Integer>(Arrays.asList(data));

        for (int j = index.size(); j > 0; j--) {
            int num = index.get(j - 1);
            list.remove(num);
        }

        System.out.println(list);
    }
}

ちょっと長いかもですがこんな感じに。
結果は以下のように。

[1, 3, 4, 7, 9]

ちゃんと2,3,3が粛清されてくれました。

最後に

個人的にはInteger型とremove(int i)について勉強になったので一歩前進かなといったところです。

編集履歴

2019/08/02
コメントでご指摘のあったfor文の改善。