ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4

Тема: «Сортировка методом Шелла»

Цель: научиться сортировать по возрастанию и убыванию одномерные массивы и массивы записей методом Шелла.

Ход работы

Теоретические обоснования

Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле передвигалось место, оставленное под A[i]). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом (рис. 3).

Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i – h], A[i – 2h], A[i – 3h] и так далее, где h – положительная константа. Таким образом, формируется массив, в котором «h-серии» элементов, отстоящие друг от друга на h, сортируются отдельно.

Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h = 1.

В настоящее время неизвестна последовательность hi, h_i–1, h_i–2, ...,h₁, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h_i+1 = 3h_i+1,а h₁ = 1. Начинается процесс с h_m, что h_m ≥ [n/9]. Иногда значение h вычисляют проще: h_i+1 = h_i/2, h₁ = 1, h_m = n/2. Это упрощенное вычисление h и будем использовать далее.

Теперь запишем алгоритм:

procedure ShellSort(n: integer; var A: mas);

{Процедура сортировки Шелла}

var

h, i, j, Tmp: integer;

begin

{Вычисляем величину h}

h := n div 2;

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

while h > 0 do begin

for i := 1 to n-h do begin

j := i;

while j > 0 do begin

{Сравниваем элементы, отстоящие друг от друга}

{на расстояние, кратное h}

if A[j] > A[j+h] then begin

{Меняем элементы}

Tmp := A[j+h];

A[j+h] := A[j];

A[j] := Tmp;

j := j – h;

end else

{Досрочно завершаем цикл с параметром j}

j := 0;

end;

end;

{Уменьшаем размер серии}

h := h div 2;

end;

end;

Пример сортировки одномерного массива, состоящего из 5 элементов:

Задание 1. Выполнить сортировку в одномерном массиве. Массив заполнить случайными числами, вывести исходный массив, выполнить сортировку методом Шелла, вывести отсортированный массив.

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

Выполнение задания 1 и 2.

Решение задач осуществляется аналогично примерам, рассмотренным в 1 и 2 практических работах.

Решить самостоятельно:

1. Квартира описывается свойствами - порядковый номер квартиры в списке, количество комнат, площадь, этаж, стоимость. Отсортируйте квартиры по стоимости.

Организуйте:

• ввод данных в массив записей;
• вывод исходных данных в табличном виде;
• сортировку;
• вывод отсортированных данных;
• произвести запись в файл отсортированного массива и чтение из файла.

2. Расположить номера строк матрицы по убыванию сумм элементов строк.

3. Вывести на экран отсортированные данные: номера строк и соответствующие им суммы.