Задача сортировки массивов

Задачу сортировки данных можно применить к числам, словам и символов текста. Для этого, требуется определить порядок сортировки для элементов массива, определить понятия "больше" и "меньше" для каждой пары элементов. Отсортировать последовательность чисел можно точно таким же способом, как и последовательность строк текста. Необходимо только определить какой из элементов пары "больше" другого.

Более важным для выбора алгоритма является местоположение данных - в оперативной памяти компьютера или на внешнем устройстве.

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

Различают два вида сортировки данных:

- сортировка данных, расположенных в оперативной памяти компьютера (внутренняя сортировка);

- сортировка данных, расположенных на внешних запоминающих устройствах (внешняя сортировка).

При разработке программы для сортировки можно воспользоваться различными алгоритмами. Наиболее известными являются следующие:

- метод сортировки обменами ("пузырьковая" сортировка);

- метод сортировки вставками;

- метод сортировки выбором элемента;

- метод быстрой сортировки;

- метод половинного деления.

Алгоритм "быстрой" сортировки обеспечивает высокую скорость сортировки и находит широкое практическое применение. Недостатком "быстрой" сортировки является возможность резкого увеличения трудоемкости при "неблагоприятном" исходном порядке элементов в массиве. Выбор в пользу того или иного алгоритма может быть сделан при условии тщательного статистического анализа реальной задачи и это является достаточно важной проблемой в программировании.