Алгоритмы поиска и сортировки данных
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
нт, больший или равный А[n-1], и после этого осуществляется вставка непосредственно перед найденным элементом.
Хотя сортировка вставкой основана на рекурсивном подходе, более эффективной будет ее реализация снизу вверх, т.е. итеративная. Элемент А[i] (начиная с элемента А[1] и заканчивая А[n-1]) вставляется в соответствующее место среди первых i элементов массива (которые к этому моменту уже отсортированы). Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве.
Ниже приведен псевдокод данного алгоритма.
Алгоритм Insertionsort (А [0..n-1])
// Сортировка массива методом сортировки вставкой
// Входные данные: Массив А[0..n -1] из п упорядочиваемых
// элементов
// Выходные данные: Массив А[0..n - 1], отсортированный
// в неубывающем порядке
for i = 1 to n - 1 do
v = A[i]= i - 1j 0 and A[j] > v do[j + 1] = A[j]
j = j - 1
A[j + 1] = v
Работа алгоритма проиллюстрирована на рис. 2.3.
Рис. 2.3. Пример сортировки вставкой
Сортировка подсчетом:
Идея данного метода состоит в том, чтобы подсчитать для каждого элемента сортируемого списка общее количество элементов, меньших данного, и занести полученный результат в таблицу. Полученные числа указывают позиции элементов в отсортированном списке: например, если для некоторого элемента это количество равно 10, то он должен быть одиннадцатым (его индекс будет равен 10, если индексы начинаются с 0) в отсортированном массиве. Таким образом, можно отсортировать список, просто копируя его элементы в соответствующие позиции в новом, отсортированном списке. Такой алгоритм называется сортировкой подсчетом сравнений (comparison counting) (рис. 2.4).
Рис. 2.4. Пример сортировки подсчетом сравнений
Псевдокод данного алгоритма.
Алгоритм ComparisonCountingSort (А [0..n - 1])
// Сортировка массива подсчетом сравнений
// Входные данные: Массив А[0..n - 1] упорядочиваемых значений
// Выходные данные: Массив S[0..n - 1] элементов А,
// отсортированных в неубывающем порядке
for i = 0 to n - 1 do
Count[i] = 0i = 0 to n - 2 doj = i + 1 to n - 1 doA[i] < A[j][j] = Count[j] + 1[i] = Count[i] + 1i = 0 to n - 1 do[Count[i]] = A[i]
Сортировка Шелла:
,.
).,(,,< сортир