Отсортированный массив представляет собой массив , в котором каждый элемент сортируются в численном, алфавиту, или какой - либо другой порядок, и размещены на равном расстоянии адресам в памяти компьютера. Обычно он используется в информатике для реализации статических таблиц поиска для хранения нескольких значений с одним и тем же типом данных . Сортировка массива полезна для упорядочивания данных и их быстрого восстановления.
Отсортированный массив | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | Множество | ||||||||||||||||||||
Изобретенный | 1945 г. | ||||||||||||||||||||
Изобретенный | Джон фон Нейман | ||||||||||||||||||||
Сложность времени в большой нотации O | |||||||||||||||||||||
|
Методы
Есть много хорошо известных методов , с помощью которых массив может быть отсортирован, которые включают в себя, но не ограничиваются ими: Выбор сортировки , пузырьковая сортировка , вставка сортировки , сортировка слиянием , Быстрая сортировка , пирамидальная сортировка и подсчет рода . [ необходима цитата ] Эти методы сортировки имеют разные алгоритмы, связанные с ними, и поэтому есть разные преимущества использования каждого метода.
Обзор
Сортированные массивы - это структура данных с наиболее эффективным использованием пространства с наилучшей локальностью ссылок для последовательно сохраняемых данных. [ необходима цитата ]
Элементы в отсортированном массиве находятся с использованием двоичного поиска в O (log n ); Таким образом, отсортированные массивы подходят для случаев, когда нужно иметь возможность быстро искать элементы, например, в виде структуры данных набора или мультимножества . Эта сложность поиска такая же, как и для самобалансирующихся двоичных деревьев поиска .
В некоторых структурах данных используется массив структур. В таких случаях те же методы сортировки могут использоваться для сортировки структур по какому-либо ключевому элементу структуры; например, сортировка записей об учениках по номерам списков, именам или оценкам.
Если используется отсортированный динамический массив , можно вставлять и удалять элементы. Вставка и удаление элементов в отсортированном массиве выполняется в O ( n ) из-за необходимости сдвинуть все элементы, следующие за элементом, который должен быть вставлен или удален; для сравнения, самобалансирующееся двоичное дерево поиска вставляет и удаляет на O (log n ). В случае, когда элементы удаляются или вставляются в конце, отсортированный динамический массив может сделать это за амортизированное время O (1), в то время как самобалансирующееся двоичное дерево поиска всегда работает в O (log n ).
Элементы в отсортированном массиве можно искать по их индексу ( произвольный доступ ) за время O (1), операция занимает время O (log n ) или O ( n ) для более сложных структур данных.
История
Джон фон Нейман написал первую программу сортировки массивов (сортировка слиянием ) в 1945 году, когда еще строился первый компьютер с хранимой программой . [1]
Применение отсортированных массивов
Коммерческие вычисления [2]
Правительственным организациям, частным компаниям и многим веб-приложениям приходится иметь дело с огромными объемами данных. К данным часто придется обращаться несколько раз. Хранение данных в отсортированном формате позволяет быстро и легко получить их.
В дискретной математике
Сортированные массивы могут использоваться для реализации алгоритма Дейкстры или алгоритма Прима . А также такие алгоритмы, как алгоритм Краскала для поиска минимальных остовных деревьев.
В приоритетном планировании
На уровне операционной системы одновременно ожидает множество процессов, но одновременно может обрабатывать только один процесс. Таким образом, с каждым процессом связаны приоритеты. Затем процессы отправляются в ЦП в соответствии с наивысшим приоритетом с использованием отсортированного массива идентификаторов процессов. Здесь процессы отсортированы в зависимости от их приоритетов, а затем им выделяется ЦП. Процесс с наивысшим приоритетом занимает первую позицию в отсортированном массиве. Таким образом, планирование системных процессов осуществляется по приоритетам. [3]
Планирование по принципу кратчайшего задания
Это особый случай приоритетного планирования. Здесь процессы сортируются по времени пика процессов. Процесс, требующий наименьшего времени, будет выделен ЦП в первую очередь. Следовательно, процессы отправляются в ЦП в соответствии с их пакетным временем.
Процесс | Время взрыва |
---|---|
P1 | 3 |
P2 | 4 |
P3 | 1 |
P4 | 8 |
P5 | 6 |
Смотрите также
Рекомендации
- ^ Дональд Кнут , Искусство программирования , том. 3. Эддисон-Уэсли
- ^ http://algs4.cs.princeton.edu/25applications/
- ^ Концепции операционных систем Питера Б. Гэлвина . WILEY-INDIA Pvt. ограничено. ISBN 978-81-265-2051-0.