Сортировка подсчетом (Count Sort) (реализация на C++)

C++   24 марта 2012  Автор статьи:  

В данной статье я приведу два примера реализации сортировки подсчетом. Данную сортировку следует использовать при достаточно небольшом диапазоне значений ключа.Очень просто написать реализацию countSort, если нужно отсортировать целые числа, тогда достаточно завести массив и хранить в нем количество повторений каждого целого числа в массиве, а затем последовательно пробежаться по массиву и вывести каждое число столько раз, сколько указано в массиве.Ниже приведен пример реализации сортировки подсчетом для целых чисел от 0 до k:

#include
using namespace std;
int a[100];
int c[100];
int main()
{
int n;//количество элементов в массиве
int k = 100;
cin >> n;
//считываем массив
for(int i = 0; i < n; i++) { cin>>a[i];
}
//строим массив с
for(int i = 0; i < n; i++) { c[a[i]]++; } //бежимся по всему отрезку //с 0 до k-1 for(int i = 0; i < k; i++) { //выводим i c[i] раз for(int j = 0; j < c[i]; j++) cout<
Проблемы с использованием Count Sort возникнут, если сортируемые элементы имеют разную структуру. Например есть некоторый университет в котором учиться много студентов. Каждый студент кроме возраста, по которому нужно отсортировать, имеет набор различных параметров. Поэтому для сортировки подсчетом в этом случае придется использовать очереди, стеки или списки, т.е любую структуру, которая умеет вынимать и класть данные за O(1). Таким образом мы создадим массив из очередей, и будем каждого студента класть в очередь, которая будем соответствовать его возрасту.

  • koloshmet

    А если в массиве есть одинаковые числа?

    • То ничего страшного.

  • Андрій Гонтаренко

    как записать в виде функции?

Научиться программировать

  • на Delphi

  • на Java

  • на C++