Отсортированный массив - Sorted array

Отсортированный массив
Тип	Множество
Изобрел	1945
Изобретенный	Джон фон Нейман
Сложность времени в нотация большой O
Алгоритм Средний Худший случай Космос На) На) Поиск O (журнал n) O (журнал n) Вставлять На) На) Удалить На) На)

А отсортированный массив является структура данных массива в котором каждый элемент отсортирован в числовом, алфавитном или каком-либо другом порядке и размещен по одинаковым адресам в памяти компьютера. Обычно используется в Информатика реализовать статический таблицы поиска для хранения нескольких значений, которые имеют одинаковые тип данных. Сортировка массива полезна при организации данные в заказанном виде и быстро их восстанавливает.

Методы

Существует множество хорошо известных методов сортировки массивов, которые включают, но не ограничиваются: Выборочная сортировка, Пузырьковая сортировка, Вставка сортировки, Сортировка слиянием, Быстрая сортировка, Heapsort, и Счетная сортировка.^{[нужна цитата ]} С этими методами сортировки связаны разные алгоритмы, и поэтому использование каждого метода дает разные преимущества.

Обзор

Сортированные массивы - это наиболее компактная структура данных с лучшими местонахождение ссылки для последовательно сохраненных данных.^{[нужна цитата ]}

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

В некоторых структурах данных используется массив структур. В таких случаях одни и те же методы сортировки могут использоваться для сортировки структур по какому-либо ключевому элементу структуры; например, сортировка записей об учащихся по номерам списков, именам или оценкам.

Если используется отсортированный динамический массив, то можно вставлять и удалять элементы. Вставка и удаление элементов в отсортированном массиве выполняется в O (п) из-за необходимости сдвинуть все элементы, следующие за элементом, который нужно вставить или удалить; для сравнения самобалансирующееся двоичное дерево поиска вставляет и удаляет на O (журнал п). В случае, когда элементы удаляются или вставляются в конце, отсортированный динамический массив может сделать это в амортизированный O (1) раз, в то время как самобалансирующееся двоичное дерево поиска всегда работает в O (log п).

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

История

Джон фон Нейман написал первую программу сортировки массивов (Сортировка слиянием ) в 1945 году, когда первый компьютер с хранимой программой все еще строился.^[1]

Применение отсортированных массивов

Коммерческие вычисления^[2]

Правительственным организациям, частным компаниям и многим веб-приложениям приходится иметь дело с огромными объемами данных. К данным часто придется обращаться несколько раз. Хранение данных в отсортированном формате позволяет быстро и легко получить их.

В дискретной математике

Сортированные массивы можно использовать для реализации Алгоритм Дейкстры или же Алгоритм Прима. Также такие алгоритмы, как Алгоритм Краскала для поиска минимальных остовных деревьев.

В приоритетном планировании

На Операционная система на уровне, многие процессы ожидают одновременно, но может обрабатывать только один процесс за один раз. Таким образом, каждому процессу присваиваются приоритеты. Затем процессы отправляются в ЦП в соответствии с наивысшим приоритетом с использованием отсортированного массива идентификаторов процессов. Здесь процессы отсортированы в зависимости от их приоритетов, а затем им выделяется ЦП. Процесс с наивысшим приоритетом занимает первую позицию в отсортированном массиве. Таким образом, планирование системных процессов выполняется по приоритетам.^[3]

Планирование по принципу кратчайшего задания

Это особый случай приоритетного планирования. Здесь процессы сортируются по времени пика процессов. Процесс, требующий наименьшего времени, будет выделен ЦП в первую очередь. Следовательно, процессы отправляются в ЦП в соответствии с их пакетным временем.

Процесс	Время взрыва
P1	3
P2	4
P3	1
P4	8
P5	6

Смотрите также

• Алгоритм сортировки
• Алгоритм двоичного поиска
• Куча (структура данных)
• Структура данных поиска

Рекомендации