Сортировка массивов

Случайные числа

В системе генерации случайных чисел используются процедура Randomize и функция Random.

Процедура Randomize инициализирует генератор случайных чисел. Синтаксис вызова имеет следующий вид:

Randomize;

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

Строго говоря, последовательность чисел является не случайной, а псевдослучайной, так как, начав с того же стартового значения, можно повторить всю последовательность случайных чисел.

Для получения псевдослучайных чисел используется функция Random. Синтаксис ее вызова имеет следующий вид:

случайное_число:= Random(верхняя_граница);

Этот оператор присвативает переменной случайное_число равномерно распределенное случайное значение типа Integer, находящееся в диапазоне от нуля до верхняя_граница, т.е. [0, верхняя_граница).

Параметр верхняя_граница необязателен. В этом случае генератор полагает, что верхняя_граница равна 1, т.е. функция возвращает случайное вещественное число из промежутка [0, 1).

Случайные целые числа, принадлежащие отрезку [ а, b ], вычисляют по формуле а + Random(b – a + 1).

Замечание. Не комбинируйте вызов процедуры Randomize в циклах вместе с обращением к функции Random. Обычно процедура Randomize вызывается только один раз до вызова функции Random (т.е. до цикла).

Сортировка массива – это перерасположение элементов массива в заданном порядке.

При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.

Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:

- количество присваиваний;

- количество сравнений.

Все методы сортировки можно разделить на две большие группы:'

- прямые методы сортировки;

- улучшенные методы сортировки.

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

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

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

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

Дата добавления: 2015-06-28