Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Алгоритм 7. Сортировка подсчетом
|
|
Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея вот в чем: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место. Если все равно непонятно, смотрите реализацию:
| 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. 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 " Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.