Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

АиСД / АиСД3

.DOCX
Скачиваний:
6
Добавлен:
31.05.2018
Размер:
37.87 Кб
Скачать

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

НАБЕРЕЖНОЧЕЛНИНСКИЙ ИНСТИТУТ (ФИЛИАЛ)

КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ

ЛАБОРАТОРНАЯ РАБОТА № 3

«Сортировка»

По дисциплине

«Алгоритмы и структуры данных»

Выполнил:

Студент группы 2161121

Золотых С.В.

Проверил:

Каримов Т.Н.

Набережные Челны

2018

Цель

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

Задание

Написать программу, реализующую алгоритмы сортировки данных в информационном массиве:

  1. Метод обмена;

  2. Сортировка слиянием.

Листинг Программы

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; }

}

}

}

}

Результат выполнения программы

Вывод

Были реализованы два алгоритма сортировки: сортировка слиянием и методом обмена (пузырьком).

Соседние файлы в папке АиСД