Файл: Сортировка данных в массиве. Оценка эффективности метода (Архитектура программы).pdf

Заключение

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

• у алгоритмов сортировки множество важных применений в процессе функционирования современных систем и программных приложений;
• часто сортировка применяется без непосредственной необходимости для решения прикладных задач;
• применяются неэффективные алгоритмы сортировки, либо алгоритмы, не отвечающие поставленным для решения конкретных задач требованиям (целям).

Из вышеизложенного ясно, программа сортировки будет эффективна только тогда, когда выбранный алгоритм и способ его реализации учитывает специфику поставленной задачи.

В ходе настоящей работы была разработана программа, способная демонстрировать возможности алгоритмов сортировки различными методами и получать экспериментальным путем количественной оценки их эффективности.

В результате выполнения работы были решены следующие задачи:

• рассмотрены различные алгоритмы сортировки данных, для реализации были выбраны алгоритмы сортировки: Шелла, быстрая, вставками, выбора, обмена;
• разработан программный продукт, реализующий сортировку данных выбранными методами;
• проведены эксперименты по сортировке больших объемов данных всеми реализованными методами и получены зависимости времени сортировки от количества сортируемой информации – полученные результаты отражены в разделе 3.

Список использованных источников

1. Асхабов Х. И. Алгоритмы сортировки неупорядоченных статических массивов и их реализация в Lazarus. КНИИ РАН, г. Грозный, Россия. Грозненский естественнонаучный бюллетень, том 3, №5 (13), 2018, 10 с.
2. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д.Структуры данных и алгоритмы = Data structures and algorithms / Под ред. А. А. Минько. — М.: Вильямс, 2000. — 382 с.
3. Вершинин М., Иванова Е. C# Enterprise Edition. Технологии проектирования и разработки. – М.: BHV, 2003 г. – 1088 с.
4. Вирт Н. Алгоритмы и структуры данных = Algoritms and data structure. — М.: Мир, 1989. — 360 с.
5. Воройский Ф. С. Информатика. Новый систематизированный толковый словарь-справочник. — 3-е изд.. — М.: ФИЗМАТЛИТ, 2003. — 760 с. — (Введение в современные информационные и телекоммуникационные технологии в терминах и фактах).
6. Громов Ю.Ю. – Технология программирования: учебное пособие / Ю.Ю. Громов, О.Г. Иванова, М.П. Беляев, Ю.В. Минин. – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2013. – 172 с.
7. Джозеф Албахари – C#. Справочник. Полное описание языка. Пер. с англ. - М: ООО «И.Д. Вильямс», 6-е изд., 2016, 1040 с.
8. Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. 2 - е изд. М. : «Вильямс», 2008. 824 с.
9. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2013. – 1277 с.
10. Королевство Дельфи. Виртуальный клуб программистов. URL: http: //delphikingdom.com (дата обращения: 02.02.2019).
11. Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2016. — 576 с.
12. Макоха А.Н Компьютерные науки. Введение в язык программирования Турбо Паскаль: В 3 ч. Ч. III.: Учебное пособие. – Ставрополь: Изд-во СГУ, 2001.
13. Роберт Седжвик. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск — СПб.: ДиаСофтЮП, 2003. – 687 с.
14. Тюгашев А.А. Основы программирования. Часть I. – СПб: Университет ИТМО, 2016. – 160 с.
15. Фаронов В.В. Delphi. Программирование на языке высокого уровня: учебник для вузов. СПб., Питер. 2007. 639 с.

Приложение А. Исходный код алгоритма сортировки методом выбора, записанный на языке программирования C#

/// <summary>

/// Sort array by selections method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SelectionsSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary value for exchanging

T temp, currentSmallest;

// temporary values

int sortedRangeEnd = 0, currentSmallestIndex = 0;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

while (sortedRangeEnd < __array.GetLength(0))

{

// find index of smallest from index

currentSmallest = __array[sortedRangeEnd];

currentSmallestIndex = sortedRangeEnd;

for (int i = sortedRangeEnd + 1; i < __array.GetLength(0); i++)

{

/* operations++ */ OperationsCount++;

if (currentSmallest.CompareTo(__array[i]) > 0)

{

currentSmallest = __array[i];

currentSmallestIndex = i;

/* operations++ */ OperationsCount++;

}

}

// swap elements

temp = __array[sortedRangeEnd];

__array[sortedRangeEnd] = __array[currentSmallestIndex];

__array[currentSmallestIndex] = temp;

/* operations++ */ OperationsCount += 3;

// continue

sortedRangeEnd++;

}

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение Б. Исходный код алгоритма сортировки методом обмена, записанный на языке программирования C#

/// <summary>

/// Sort array by bubbles method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] BubbleSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary swapping flag

bool swapped;

// temporary value for exchanging

T temp;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

do

{

swapped = false;

for (int i = 1; i < __array.GetLength(0); i++)

{

/* operations++ */ OperationsCount++;

if (__array[i - 1].CompareTo(__array[i]) > 0)

{

temp = __array[i - 1];

__array[i - 1] = __array[i];

__array[i] = temp;

swapped = true;

/* operations++ */ OperationsCount += 3;

}

}

} while (swapped != false);

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение В. Исходный код алгоритма сортировки методом вставок, записанный на языке программирования C#

/// <summary>

/// Sort array by insertions method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] InsertionsSort<T>(T[] __array_) where T : IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary value for exchanging

T temp;

// temporary values

int sortedRangeEndIndex = 1, ins_index = 0;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (int i = 0; i < __array_.GetLength(0); i++) __array[i] = __array_[i];

// sorting

while (sortedRangeEndIndex < __array.GetLength(0))

{

/* operations++ */ OperationsCount++;

if (__array[sortedRangeEndIndex].CompareTo(__array[sortedRangeEndIndex-1])<0)

{

// find index to insert

for (int index = 0; index < __array.GetLength(0); index++)

{

/* operations++ */ OperationsCount++;

if (__array[index].CompareTo(__array[sortedRangeEndIndex]) > 0)

{

ins_index = index; break;

}

} // insert

temp = __array[ins_index];

__array[ins_index] = __array[sortedRangeEndIndex];

for (int current = sortedRangeEndIndex; current>ins_index; current--)

{

/* operations++ */ OperationsCount++;

__array[current] = __array[current - 1];

}

__array[ins_index + 1] = temp;

/* operations++ */ OperationsCount += 3;

}

// next position

sortedRangeEndIndex++;

/* operations++ */ OperationsCount++;

}

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение Г. Исходный код алгоритма сортировки методом Шелла, записанный на языке программирования C#

/// <summary>

/// Sort array by Shell method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SortByShell<T>(T[] __array_) where T: IComparable<T>

{

//------------------------------------------

// reset sorting analytics to initial values

//------------------------------------------

OperationsCount = 0;

Duration = 0;

System.Diagnostics.Stopwatch SortTimer = new System.Diagnostics.Stopwatch();

SortTimer.Start();

//------------------------------------------

// temporary value for exchanging

T temp;

// counters

int i, j, k;

// temporary array to return

T[] __array = new T[__array_.GetLength(0)];

// copy array

for (i = 0; i < __array_.GetLength(0); i++)

__array[i] = __array_[i];

// sorting

for (k = __array.GetLength(0) / 2; k > 0; k /= 2)

for (i = k; i < __array.GetLength(0); i++)

{

temp = __array[i];

/* operations++ */ OperationsCount++;

for (j = i; j >= k; j -= k)

{

/* operations++ */ OperationsCount++;

if (temp.CompareTo(__array[j - k]) < 0)

{

__array[j] = __array[j - k];

/* operations++ */ OperationsCount++;

}

else

break;

}

__array[j] = temp;

/* operations++ */ OperationsCount++;

}

//------------------------------------------

// stop sorting time

SortTimer.Stop();

Duration = SortTimer.ElapsedMilliseconds;

//------------------------------------------

// return result

return __array;

}

Приложение Д. Исходный код алгоритма методом быстрой сортировки, записанный на языке программирования C#