Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


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

Поиск:
Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея вот в чем: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место. Если все равно непонятно, смотрите реализацию:
Код

Program CountingSort;
Var A,B   : array[1..1000] of byte;
    C     : array[byte] of integer;
    N,i    : integer;
Begin
{Определение размера массива A (N) и его заполнение}

{сортировка данных}
for i:=0 to 255 do
C[i]:=0;
for i:=1 to N do
C[A[i]]:=C[A[i]]+1;
for i:=1 to 255 do
C[i]:=C[i-1]+C[i];
for i:=N downto 1 do
begin
  B[C[A[i]]]:=A[i];
  C[A[i]]:=C[A[i]]-1; {здесь мы избегаем возможности записи двух одинаковых чисел в одну ячейку}
end;
{Вывод массива B}

End.


Этот простой метод не использует вложенных циклов и, учитывая небольшой диапазон значений, время его работы есть O(n).

Рассмотрев такое количество сортировок, можно задуматься: а будет ли результат их работы одинаковым? Странный вопрос, ведь все сортировки правильно сортируют данные, так почему же результат работы может быть разным? Хорошо, объясню: меньшие элементы всегда расположены перед большими, но порядок одинаковых элементов может быть нарушен. Если мы сортируем данные, которые состоят из одного ключа, то мы, конечно, не заметим разницы. Но если к ключу прилагается дополнительная информация, то одна сортировка может вернуть нам 1977 "Иванов" и 1977 "Сидоров", а другая -1977 "Сидоров" и 1977 "Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.
Сайт: http://docs.com.ru






Просмотров: 7637

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную