АиСД / АиСД3
.DOCXМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
НАБЕРЕЖНОЧЕЛНИНСКИЙ ИНСТИТУТ (ФИЛИАЛ)
КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ
ЛАБОРАТОРНАЯ РАБОТА № 3
«Сортировка»
По дисциплине
«Алгоритмы и структуры данных»
Выполнил:
Студент группы 2161121
Золотых С.В.
Проверил:
Каримов Т.Н.
Набережные Челны
2018
Цель
Приобретение навыков реализации программ сортировки данных.
Задание
Написать программу, реализующую алгоритмы сортировки данных в информационном массиве:
-
Метод обмена;
-
Сортировка слиянием.
Листинг Программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace АиСД3
{
class Program
{
static void Main(string[] args)
{
int[] a1 = new int[] { 21, 23, 24,- 40, 75, 76, 78, 77, 90, 2100, 2200, -2300, 2400, 2500 };
int[] a2 = new int[] { -10, 11, 41, 50, 65, 86, 98, 110, 190, -1100, 1200, 3000, -5000 };
int[] a3 = new int[a1.Length + a2.Length];
int[] a4 = new int[] { 23, 67, -1, 34, 137, -123, 674, 34, 75, 2124, 64 };
//сливаем два массива в один
int i = 0, j = 0;
for (int k = 0; k < a3.Length; k++)
{
if (i > a1.Length - 1)
{
int a = a2[j];
a3[k] = a;
j++;
}
else if (j > a2.Length - 1)
{
int a = a1[i];
a3[k] = a;
i++;
}
else if (a1[i] < a2[j])
{
int a = a1[i];
a3[k] = a;
i++;
}
else
{
int b = a2[j];
a3[k] = b;
j++;
}
}
Console.WriteLine("Сортировка слиянием!");
Console.WriteLine("Первый массив: ");
for (i = 0; i < a1.Length; i++)
Console.Write(a1[i] + " ");
Console.WriteLine();
Console.WriteLine("Второй массив: ");
for (i = 0; i < a2.Length; i++)
Console.Write(a2[i] + " ");
Console.WriteLine();
Console.WriteLine("Объединённый массив: ");
for (i = 0; i < a3.Length; i++)
Console.Write(a3[i] + " ");
SortUnsorted(a3, 0, a3.Length-1);
Console.WriteLine();
Console.WriteLine("Отсортированный массив: ");
for (i = 0; i < a3.Length; i++)
Console.Write(a3[i] + " ");
Console.WriteLine();
Console.WriteLine("Сортировка обменом!");
Console.WriteLine("Массив: ");
for (i = 0; i < a4.Length; i++)
Console.Write(a4[i] + " ");
Bubble(a4);
Console.WriteLine();
Console.WriteLine("Отсортированный массив: ");
for (i = 0; i < a4.Length; i++)
Console.Write(a4[i] + " ");
Console.ReadKey();
}
//метод рекурсивной сортировки для объединённого массива
public static void SortUnsorted(int[] a, int first, int last)
{
if (last <= first)
return;
int mid = first + (last - first) / 2;
SortUnsorted(a, first, mid);
SortUnsorted(a, mid + 1, last);
int[] buf = new int[a.Length];
Array.Copy(a,buf,a.Length);
for (int k = first; k <= last; k++)
buf[k] = a[k];
int i = first, j = mid + 1;
for (int k = first; k <= last; k++)
{
if (i > mid)
{
a[k] = buf[j];
j++;
}
else if (j > last)
{
a[k] = buf[i];
i++;
}
else if (buf[j] < buf[i])
{
a[k] = buf[j];
j++;
}
else
{
a[k] = buf[i];
i++;
}
}
}
//метод сортировки обменом
public static void Bubble(int[] b)//Метод сортировки пузырьком
{
int S;//S-переменная, отвечающая за продолжение или выход из цикла
for (int i = 0; i < b.Length; i++)
{
S = 0;
for (int j = 0; j < b.Length - i - 1; j++)
{
if (b[j] > b[j + 1])
{
S = 1;
int temp = b[j];
b[j] = b[j + 1];
b[j + 1] = temp;
}
}
if (S == 1) { continue; }
else { break; }
}
}
}
}
Результат выполнения программы
Вывод
Были реализованы два алгоритма сортировки: сортировка слиянием и методом обмена (пузырьком).