counting sort

counting sortは最速の探索アルゴリズムの一つ。 time complexityはO(n+k)

配列は合計で3つ使用する。 探索対象の配列A、indexを記録しておくための配列C、出力用の配列Bの３つ。 配列Cでは、配列Aの中で出現した特定の要素の回数を配列Cのindex順に割り当て、且つそれまでに出現した回数と足し合わせる。

例 配列Aの中で出現した特定の要素の回数を配列Cのindex順に割り当て作業

A = [1, 3, 5, 3, 2, 5, 6, 7]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 1, 2, 0, 2, 1, 1]

且つそれまでに出現した回数と足し合わせる。

C = [0, 1, 2, 4, 4, 6, 7, 8]

出力配列Bに、右端の配列Aの要素から配列Cの位置を元に順々に割り当てる。一度使用されたCの要素は-1する。この作業を配列Aのindex=0になるまで続ける。 例 [1]

A = [1, 3, 5, 3, 2, 5, 6, "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 2, 4, 4, 6, 7, 8]

B index =

B = [ ]

[2]

A = [1, 3, 5, 3, 2, 5, 6, "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 2, 4, 4, 6, 7, 8>>>7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ , , , , , , , 7]

[3]

A = [1, 3, 5, 3, 2, 5, "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 2, 4, 4, 6, 7>>>6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ , , , , , , 6, 7]

[4]

A = [1, 3, 5, 3, 2, "5", "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 2, 4, 4, 6>>>5, 6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ , , , , , 5, 6, 7]

[5]

A = [1, 3, 5, 3, "2", "5", "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 2>>>1, 4, 4, 5, 6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ ,2 , , , , 5, 6, 7]

[6]

A = [1, 3, 5, "3", "2", "5", "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 1, 4>>>3, 4, 5, 6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ ,2 , ,3 , , 5, 6, 7]

[7]

A = [1, 3, "5", "3", "2", "5", "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 1, 3, 4, 5>>>4, 6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ ,2 , ,3 ,5 ,5 , 6, 7]

[8]

A = [1, "3", "5", "3", "2", "5", "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1, 1, 3>>>2, 4, 4, 6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ ,2 ,3 ,3 ,5 ,5 , 6, 7]

[9]

A = ["1", "3", "5", "3", "2", "5", "6", "7"]

C index = 0, 1, 2, 3, 4, 5, 6, 7

C = [0, 1>>>0, 1, 2, 4, 4, 6, 7]

B index = 1, 2, 3, 4, 5, 6, 7, 8

B = [ 1 ,2 ,3 ,3 ,5 ,5 , 6, 7]