スターリンソートを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文の改善。