程式隨筆
0%

【演算法】Counting Sort

Posted on Edited on Disqus:

何謂Counting Sort

是一種排序的演算法，特色是不需要比較數字間的大小，而是透過計算在Array中的Index的位置來達到排序的效果，限制是必須先知道數字的範圍以及數字組的個數，屬於線性排序 O(n) 。

案例一

Suppose you have an array of 1000 integers. The integers are in random order, but you know each of the integers is between 1 and 5000 (inclusive). In addition, each number appears only once in the array. Assume that you can access each element of the array only once. Describe an algorithm to sort it.

假設你有個數字陣列其中包含1000個數字，且這些數字來自1~5000之間不重複，請用一組演算法來達成只讀取數字一次並排序完成。

解題

欲排序的陣列

1
2
3
4
//隨機取1000個
int Amount = 1000;
//隨機從1~5000中取出不重複的1000個數字
int[] IntPool = Enumerable.Range(1, 5000).OrderBy(x => Guid.NewGuid()).Take(Amount).ToArray();

準備一個的數字陣列，空間為5000

1
int[] IndexArray = new int[5000];

計算哪些位置應該存在數字

1
2
3
4
foreach (var element in IntPool)
{
    IndexArray[ element -1 ] ++;
}

將IndexArray中值為1的挑出來

1
2
3
4
5
6
7
8
9
10
11
12
int[] Result = new int[1000];
var Index = 0;
for (int i = 0; i < IndexArray.Length; i++)
{
	if (IndexArray[i] > 0)
	{
		Result[Index] = i + 1;
		Index++;
	}
}

//此時Result即為排序後的結果

案例二

假設你有個數字陣列其中包含1000個數字，這些數字來自1~5000之間且可能會重複，如何用Counting Sort達成排序

解題

欲排序的陣列

1
2
3
4
5
6
Random Rnd = new Random();
int[] IntPool  =new int[1000];
for (int i = 0; i < 1000; i++)
{
   IntPool[i] = Rnd.Next(1,5001);
}

找出最大值與最小值

1
2
3
4
5
6
7
8
9
10
int Min = IntPool[0];
int Max = IntPool[0];
for (int i = 1; i < IntPool.Length; i++)
{
	if (IntPool[i] > Max)
		Max = IntPool[i];

	if (IntPool[i] < Min)
		Min = IntPool[i];
}

準備一個能容納最大範圍的IndexArray

1
int[] IndexArray = new int[Max - Min +1];

計算每個數字在IndexArray中的相對位置，並統計每個位置重複的數字數

1
2
3
4
5
foreach (var element in IntPool)
{
    //統計每個位置有幾個重複的數字
	IndexArray[element - Min] ++;
}

計算每個位置累積的數字個數
這邊是我想比較久的地方，所以畫了一個圖希望能幫助理解，假設我們算出來後陣列長這樣，表示Index 0放著2個數字，Index 2有1個數字，Index 4有1個數字以此類推

所以如果我們將每個位置的數字與前一格相加，可以得到該Index實際上已經排了幾個數字，

計算到達該位子時，實際上總共已經有幾個數字

1
2
3
4
for (int i = 1; i < IndexArray.Length; i++)
{
	IndexArray[i] = IndexArray[i] + IndexArray[i - 1];
}

排序

1
2
3
4
5
6
7
8
9
10
int[] Result = new int[1000];
foreach (var element in IntPool)
{
	var TotalCount = IndexArray[element - Min];
	//第幾個數字-1，其實就表示他要放在Result的Index位置
	Result[TotalCount- 1] = element;
	IndexArray[element - Min] --;
}

//此時Result即為排序後的結果