Элементы программирования на Си. Родионова Т.Е. - 25 стр.

UptoLike

Составители:

Рубрика:

Сортировка методом Шелла подобна сортировке методом парных пере-

становок в том смысле, что идет сравнение и, в нужном случае, перестановка пар

элементов. Но сравниваются не рядом стоящие элементы, а те, которые находятся

друг от друга на расстоянии D.

Эта величина первоначально равна D=(N+1)/2 ( N - количество элементов

сортируемой последовательности). После каждого просмотра расстояние между

элементами (D) уменьшается.

D(i+1)=floor((D(i)+1)/2)

Функция floor возвращает округленное в сторону уменьшения значение вы-

ражения. Последний просмотр осуществляется при D=1.

Сортировка подсчетом

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

элемента исходного массива в отсортированном массиве. Для этого каждый эле-

мент исходной последовательности сравнивается со всеми остальными элементами

и подсчитывается, сколько элементов меньше сравниваемого. Это значение оп-

ределяет число элементов, которые будут находиться перед рассматриваемым

элементом в отсортированном массиве и определяет индекс элемента (индексы

элементов массива в Си начинаются с 0). Индексы всех элементов хранятся во

вспомогательном массиве. В конце работы необходимо расставить элементы на

места в соответствии с полученными индексами.

4.2 Варианты заданий

1. Дана последовательность, расположить ее положительные элементы,

стоящие на нечетных местах по возрастанию.

2. Дана последовательность, расположить ее ненулевые элементы по убыва-

нию.

3. Переставить строки исходной матрицы так, чтобы убывало количество

нулей в строках.

4. Упорядочить все строки матрицы по числу элементов, кратных 3, т.е. на

первое место поставить строку с наименьшим числом таких элементов и т.д., на по-

следнее место - с наибольшим числом таких элементов.