sd_1

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра безопасности информационных систем (БИС)

СОРТИРОВКИ МАССИВОВ

Отчет по практической работе №1

по дисциплине «Структуры данных»

Выполнил Студент группы 730-2

_______ Подойницын К.В.

09.09.2021

Принял

Инженер Научно-технического отдела ЦСП

_______ Уразаев Д.Р.

09.09.2021

Томск 2021

2

Задание

Реализуйте сортировку расческой, быструю сортировку и еще одну по варианту. Продемонстрируйте на входных данных работоспособность вашего приложения и корректность реализации алгоритма сортировки. Реализуйте соответствующий варианту задания генератор входных данных. Подготовьте отчет и загрузите его на СДО. Размер массива выбирайте в диапазоне 20-100 элементов

Вариант 8. Третья сортировка - сортировка Шелла. Входные данные представлены только числами двойной точности с плавающей точкой (использовать double).

3

Содержание

4

1. Введение

Цель работы: овладеть навыками работы с разными способами сортировки массивов на языке программирования C#.

5

2. Ход работы

2.1 Описание работы

В данной работе реализуются три сортировки: сортировка расческой, быстрая сортировка и сортировка Шелла.

Сортировка расческой

Расстояние между элементами массива максимально и равно его размеру минус один. Пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения (равного примерно 1, 247). Затем пройти по списку вновь. Продолжать прохождение массива пока разность индексов не достигнет единицы. В этом случае сравниваются соседние элементы, как и в сортировке пузырьком, но такая итерация одна.

Быстрая сортировка.

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

Сортировка Шелла.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений ,а завершается сортировка Шелла упорядочиванием элементов при d=1.

6

1. Блок-схема программы сортировки Шелла представлена на рисунке

Рисунок 1

7

2.2 Скриншоты работы программы

Скриншот работы программы сортировки расческой представлен на рисунке 2. Листинг программы представлен в приложении А.

Рисунок 2

Скриншот работы программы быстрой сортировки представлен на рисунке 3. Листинг программы представлен в приложении Б.

Рисунок 3

8

Скриншот работы программы сортировки Шелла представлен на рисунке 4. Листинг программы представлен в приложении В.

Рисунок 4

9

3. Заключение

Входе выполнения практической работы были освоены навыки работы

стакими способами сортировки массивов, как: сортировка расческой,

быстрая сортировка и сортировка Шелла.

10

Приложение А

using System;

namespace sd_rascheska

{

class Program

{

static void Main(string[] args)

{

double[] massiv = new double[21]; Random rand = new Random();

for (int i = 0; i < massiv.Length; i++)

{

massiv[i] = rand.NextDouble();

}

Console.WriteLine(string.Join("\n", combSort(massiv)));

}

private static double[] combSort(double[] input)

{

double shag = input.Length; bool swaps = true;

while (shag > 1 || swaps)

{

shag /= 1.247330950103979; if (shag < 1) { shag = 1; } int i = 0;

swaps = false;

while (i + shag < input.Length)

{

int step = i + (int)shag; if (input[i] > input[step])

{

double swap = input[i]; input[i] = input[step]; input[step] = swap; swaps = true;

}

i++;

}

}

return input;

}

}