Posted at

Javaで分布数え上げソート[CountingSort](不完全燃焼版)

More than 5 years have passed since last update.

不完全燃焼と言いつつ乗せたのは、

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A

の問題で、テストケース9以降からメモリだったり実行時間で蹴られてしまったからです。

アルゴリズム的には正しいのですが、もっと効率の良い方法があるのか模索中です。

とは言え、気づいた方、アドバイスいただけるとすごく嬉しいです。

※最後の出力そのもので蹴られている気が。。。


分布数え上げソート

例によって、ソースへ直接コメント書いています。

概念などは下記URLが一番分かりやすかったと思います。

http://www.codereading.com/algo_and_ds/algo/counting_sort.html

要は、サイズや値の範囲が決まっている配列である場合に有効なソート方法であり、

値の発生回数を元に、値の位置を決めていくものです。

速度的には一応ソートアルゴリズムの中で最速とのことです。


コード


CountingSort.java

package aoj.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CountingSort {

public static void main(String args[]) throws IOException {
// 入力の受付
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 要素数が入ってくるが、要素数からサイズを取れるので読み捨て
br.readLine();
String line = br.readLine();
// 整数値の配列を取得
int[] befSort = parseInt(getSplitLine(line));

/**
* ここから計数ソート
*/

// 前提条件
// 1 ≤ n ≤ 2,000,000 : 要素数
// 0 ≤ A[i] ≤ 10,000 : 含まれる整数値

// カウンタ配列(出現回数)の初期化
// 数値の最大値+1で初期化する
int maxSize = 2000001;
int[] counter = new int[maxSize];

int i;
for (i = 0; i < befSort.length; i++) {
// numArrayに含まれる数値の出現回数を計算する
counter[befSort[i]]++;
// 2, 5, 1, 3, 2, 3, 0 の配列である場合、
// counter[0] = 1 回(0)
// counter[1] = 1 回(1)
// counter[2] = 2 回(2)
// counter[3] = 2 回(3)
// counter[4] = 0 回(4)
// counter[5] = 1 回(5)
// の様な計算結果になる
}
//
for (i = 1; i < counter.length; i++) {
// i 以下の出現回数を計算する
counter[i] = counter[i] + counter[i - 1];
// i = 0; counter[i] = 1; 0以下は1つ
// i = 1; counter[i] = 2; 1以下は2つ
// i = 2; counter[i] = 4; 2以下は3つ
// i = 3; counter[i] = 6; 3以下は6つ
// i = 4; counter[i] = 6; 4以下は6つ
// i = 5; counter[i] = 7; 5以下は7つ
}

// output(ソート結果を登録する配列)へ計算した結果を登録する
int[] output = new int[maxSize];
for (i = befSort.length - 1; i >= 0; i--) {
output[counter[befSort[i]]] = befSort[i];
// i = 0; output[counter[2]] = 2;
// i = 0; output[4] = 2;
// i = 1; output[counter[5]] = 5;
// i = 1; output[7] = 5;
// のように、入力配列の出現回数(count[i])の場所へ
// 数値を登録していくことでソートされる
counter[befSort[i]]--;
}

// 出力
System.out.print(output[1]);
for (i = 2; i <= befSort.length; i++) {
System.out.print(" " + output[i]);
}
System.out.println();
}

private static String[] getSplitLine(String line) {
return line.split("\\s");
}

private static int[] parseInt(String[] line) {
int[] numArray = new int[line.length];
for (int i = 0; i < line.length; i++) {
numArray[i] = Integer.parseInt(line[i]);
}
return numArray;
}

}