Сызықтық, ретті іздеу (Линейный, последовательный)
жүктеу/скачать 0,89 Mb.
|
Алгоритм 5
- Бұл бет үшін навигация:
- Кірістіру сұрыптауы. (Сортировка вставками ( Insertion Sort) ) Вычислительная сложность — � ( � 2) O( n
- Сортировка подсчётом
АлгоритмӨлшемі n болатын А массивін толтыру және экранға шығару; i:=1; A[i] >A[i+1] элементтерінің орындарын ауыстыру; i:=i+1 мәні үшін i:=n болғанға дейін 3 қадамды қайталау; Сұрыпталған А массивін экранға шығару. Кірістіру сұрыптауы.(Сортировка вставками (Insertion Sort) ) Вычислительная сложность — �(�2)O(n²). Временная сложность алгоритма — �(�2)O(n²). Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным. Есеп сұрыптау или санау Сортировка подсчётом[1] (англ. counting sort[2]; сортировка посредством подсчёта[3] англ. sorting by counting[4]) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Предположим, что входной массив состоит из �n целых чисел в диапазоне от 00 до �−1k-1, где �∈� . Далее алгоритм будет обобщён для произвольного целочисленного диапазона. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название. Асимптотика – O(n + r — l). общем виде всё работает так: Мы создаём вспомогательный массив и на старте заполняем его нулями. Проходим по всему исходному массиву и смотрим очередное значение в ячейке. Берём содержимое этой ячейки и увеличиваем на единицу значение вспомогательного массива под этим номером. Например, если мы встретили число 5, то увеличиваем на единицу пятый элемент вспомогательного массива. Если встретили 13 — тринадцатый. После цикла во вспомогательном массиве у нас хранятся данные, сколько раз встречается каждый элемент. Теперь мы проходим по вспомогательному массиву, и если в очередной ячейке лежит что-то больше нуля, то мы в исходный массив столько же раз отправляем номер этой ячейки. Например, в первой ячейке вспомогательного массива лежит число 7. Это значит, что в исходный массив мы отправляем единицу 7 раз подряд. Жылдам сұрыптау (Быстрая сортировка, сортировка Хоара) (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем �(�log�) обменов при упорядочении n � элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Быстрая сортировка относится к алгоритмам «разделяй и властвуй». Алгоритм состоит из трёх шагов: Выбрать элемент из массива. Назовём его опорным. Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные - после. Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы. жүктеу/скачать 0,89 Mb. Достарыңызбен бөлісу:
|