2013-07-20

Программирование на языке C. Сортировка

Сортировка данных является одним из важных применений вычислительной техники. Центры по обслуживанию и продаже автомобилей имеют специальные базы данных, отсортированные по названию модели либо году выпуска. Файлы, хранящиеся на вашем компьютере, тоже, скорее всего, отсортированы по какому-либо признаку: названию, расширению или дате создания. Поставщики вычмашин считают, что на сортировку в среднем по отрасли тратится более 25% машинного времени.

Цель любой сортировки - упростить поиск элементов в некотором множестве (массиве). Действительно, если мы имеем дело с неотсортированным массивом, то будем вынуждены вести поиск с последовательным перебором, т.е. необходимо просматривать и проверять каждый элемент массива. Данный подход приемлем, если мы имеем дело с небольшими объемами информации, но что делать, если имеется массив данных, состоящий из нескольких миллионов или миллиардов элементов? В таких случаях просто не обойтись без эффективного метода сортировки.

Алгоритмы сортировки уже хорошо исследованы и изучены. Хотя некоторые методы в среднем могут быть лучше других (например, это относится к быстрой сортировке), ни один из методов не будет идеальным для всех ситуаций, поэтому каждый должен иметь в свеом арсенале несколько различных алгоритмов сортировки.

Для оценки эффективности сортировок можно использовать данные параметры:

1. Число сравнений элементов множества (массива).

2. Число перестановок элементов.

3. Скорость сортировки в наилучшем случае.

4. Скорость сортировки в «среднем» случае.

5. Скорость сортировки в наихудшем случае.

Интенсивность работы основана на количестве перестановок, которые выполняются. Наибольшая скорость сортировки, как правило, достигается, если массив уже упорядочен. Если массив не упорядочен, алгоритму приходится выполнять больший объем работы. И, наконец, наибольшие трудозатраты обычно требуются в тех случаях, когда массив отсортерован в обратном порядке.

Источник

Все новости>>
 

 

2021-04-01

Google сообщил о запуске проекта Dunant

Проект Dunant, начатый в 2018 году, был запущен в эксплуатацию. Трансатлантический интернет-кабель соединяет США и континентальную Европу. Общая протяженность...

подробнее
2020-04-06

Новшества в обновленной Windows 10

Корпорация Microsoft завершила разработку обновления, в котором добавлено множество функций. Обновление содержит как доработку уже имеющихся систем, так...

подробнее

 

Все новости...

 

Научно-Техническое Объединение

Тел.: 8(915)882-95-28

E-mail:e-mail