Сортировка подсчетом
========================

Сортировка подсчетом относится к семейству сортировок, которые выполняются за линейное время. Сортировка оперирует массивом, состоящим из элементов с целочисленными положительными значениями::

	public CountingSort(int array[]){
		arr = array;
	}	
	
	public int[] sort(int k){
		int C[] = new int[k + 1];
		// инициализируем вспомогательный массив C нулями
		for (int i = 0; i < C.length; i++){
			C[i] = 0;
		}
		
		// подсчитываем частоту появления значения в входном массиве
		for (int i = 0; i < arr.length; i++){
			C[arr[i]] += 1;
		}
		
		for (int i = 1; i < C.length; i++){
			C[i] = C[i - 1] + C[i];
		}
		
		// используем вспомогательный массив B, в котором будет хранится отсортированная последовательность
		int B[] = new int[arr.length + 1];
		
		for (int i = arr.length - 1; i >= 0; i--){
			B[C[arr[i]]] = arr[i];
			C[arr[i]] -= 1;
		}
		
		return B;
	}

В алгоритме сортировки подсчетом, используются два вспомогательных массива: массив C, в ячейках которого хранится число элементов, не превышающие i, где i - значение одного из элементов в исходном массиве и массив B, в котором хранится отсортированная последовательность. Переменная k определяет размер вспомогательного массива C, зависит от максимального значения в сортируемом массиве.

В первом цикле инициализируем вспомогательный массив C нулями. Во втором цикле подсчитываем частоту появления значений элементов входного массива.::

	Например, сортируемая последовательность: {1,8, 5, 2, 1, 2, 5}
	
	После второго цикла массив C, будет выглядеть следующим образом: {0, 2, 0, 0, 2, 0, 0, 1}, где индекс является значением одного из элементов в сортируемой массиве. Т.е. значение 0 встречается 0 раз, значение 1 встречается 2 раза и т.д.	 

Третий цикл определяет позиции элементов в отсортированном массиве.::

	В моем примере массив C после прохода цикла будет выглядеть след. образом: {0, 2, 0, 0, 4, 0, 0, 7}. Например, количество элементов, не превышающих значения 1 равно 2, или количество элементов, не превышающих значения 7 равно 7.

В четвертом цикле элемент из сортируемого массива arr, устанавливается в позицию отсортированного массива B. Позиции хранятся в вспомогательном массиве C. Если количество элементов, не превышающих значения 1 равно 2, то элемент устанавливается в 2-ую позицию массива B.	


Анализ времени выполнения алгоритма сортировки подсчетом
--------------------------------------------------------

Первый цикл выполняется за время Thetta(k), второй за время Thetta(n), третий за время Thetta(k), четвертый за время Thetta(n). Таким образом, полное время выполнения алгоритма равно Thetta(n + k). На практике сортировка подсчетом применяется, когда k = O(n), а в этом случае время работы алгоритма равно Thetta(n).

Свойство устойчивости
---------------------
Важное свойство алгоритма сортировки подсчетом заключается в том, что он устойчив: элементы с одним и тем же входным значением находятся в выходном массиве, в том же порядке, что и во входном. Обычно свойство устойчивости важно только в ситуации, когда вместе сортируемые элементы имеют сопутствующие данные.


Выводы
-------------------

Сортировка подсчетом используется, когда входные данные положительны, целочисленны и их значения изменяются в небольшом интервале.