Метод подсчета сравнений
Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N2), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N2 свидетельствует о том, что алгоритм неэффективен при большом N , т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.
Физическое проектирование программного обеспечения
Таблица 2
Имя модуля |
Заголовок Функции |
Формальные параметры |
Выполняемое действие |
MainUnit.cpp |
SimpleChoose |
*mass , int Kol |
Сортировка Массива mass с количеством элементов Kol методом простого выбора. |
MainUnit.cpp |
InsertionSort |
*mass , int Kol |
Сортировка Массива mass с количеством элементов Kol методом простых вставок. |
MainUnit.cpp |
CountCompares |
*mass , int Kol |
Сортировка Массива mass с количеством элементов Kol методом подсчета сравнений. |
MainUnit.cpp |
TForm1::Btn_SortClick |
- |
Выделение памяти под массивы с количеством элементов, полученных из формы, заполнение массива случайными числами; вызываем методы сортировки, выводим сообщение о завершении операции. |
MainUnit.cpp |
TForm1::DrawGis |
- |
Построение гистограммы на основе данных в переменных InsertionSort, CountCompares, SimpleChoose |
Проектирование интерфейса
В качестве интерфейса программы будет использованы две визуальные формы Windows. Это наиболее наглядный и интуитивно понятный способ представления информации, в отличии от консольных приложения имеющий гораздо больший потенциал визуального оформления.
В качестве форм ввода-вывода информации на экран будут использованы следующие компоненты:
TEdit (для ввода количества элементов )
TButton ( «Сортировать», «показать время работы алгоритмов»
TLabel (для статических надписей на формах )
TImage (для прорисовки гистограммы)
Все эти компоненты есть в стандартном наборе компонентов C++ Builder, они просты в использовании как для написания программы, так и для ее использования.
Кодирование
Реализация алгоритма сортировки методом простого выбора.
Листинг 1.1
// Выполняем сортировку
for(i=Kol-1;i>0;i--)
{
//Устанавливаем начальное значение и номер
//для максимального элемента
Max = Mass[i];
n =i;
// Ищем максимальный элемент
for(j=0;j<=i-1;j++)
{
if (Mass[j]> Max)
{
Max= Mass[j];
Mass[j]= Mass[n];
Mass[n]=Max;
}
}
Реализация алгоритма сортировки методом простых вставок.
Листинг 1.2
// Выполняем сортировку
for(i=0;i<Kol;i++)
{
Tmp=Mass[i];
for(j=i-1;j>=0 && Mass[j]>Tmp;j--)
Mass[j+1] = Mass[j];
Mass[j+1] = Tmp;
}
Реализация алгоритма сортировки методом подсчета сравнений.
Листинг 1.3
// Производим сортировку
for (i =1; i <= Kol ; i ++)
c[i]=0;
for (i=Kol; i>=2;i--)
for(j=i-1; j>=1; j--)
if (Mass[i]<Mass[j])
c[j]++;
else
c[ i ]++;
for (i =1; i <= Kol ; i ++)
b[c[i]] = Mass[i];
Тестирование.
Таблица 3
Исходные данные |
Тестируемый модуль или подпрограмма |
Ожидаемый результат |
1000 элементов массива |
TForm1::SimpleChoose |
Сохранение массива, отсортированного методом простого выбора в файл и подсчет времени выполнения |
1000 элементов массива |
TForm1::InsertionSort |
Сохранение массива, отсортированного методом простых вставок в файл и подсчет времени выполнения |
1000 элементов массива |
TForm1::CountCompares |
Сохранение массива, отсортированного методом подсчета сравнений в файл и подсчет времени выполнения |
1000 элементов массива |
TForm1::DrawGis |
Построение гистограммы по значениям времени работы. |
10000 элементов |
MainUnit.cpp |
Подсчет времени работы каждого метода сортировки и построение гистограммы. |
Таблица 4
Дата, время |
Тестируемый модуль или подпрограмма |
Кто проводил тестирование |
Описание теста |
Результаты тестирования |
10.12.14 |
TForm1::SimpleChoose |
Кузнецов Р.А. |
Проверка работы сортировки массива из 1000 элементов методом простого выбора |
Успех |
10.12.14 |
TForm1::InsertionSort |
Кузнецов Р.А. |
Проверка работы сортировки массива из 1000 элементов методом простых вставок |
Успех |
10.12.14 |
TForm1::CountCompares |
Кузнецов Р.А. |
Проверка работы сортировки массива из 1000 элементов методом подсчета сравнений |
Успех |
13.12.14 |
MainUnit.cpp |
Кузнецов Р.А. |
Проверка работы подсчета времени работы алгоритмов сортировки массива из 10000 элементов |
Ошибка. Неверный отсчет времени |
13.12.14 |
MainUnit.cpp |
Кузнецов Р.А. |
Проверка работы подсчета времени работы алгоритмов сортировки массива более 20000 элементов |
Вылет программы |
13.12.14 |
MainUnit.cpp |
Кузнецов Р.А. |
Проверка работы подсчета времени работы алгоритмов сортировки массива более 20000 элементов |
Успех |
Заключение
В ходе курсовой работы был проведен обзор трех алгоритмов сортировки, в том числе оценка их эффективности. Был сделан вывод, что сортировка методом простых вставок более эффективна в целом, чем остальные методы.
Были разработаны функции сортировки методом простых вставок, простого выбора и подсчета сравнений. Данные функции интегрированы в разработанное приложение, с помощью которого можно создать массив с заданным количеством элементов, отсортировать его любым из рассмотренных в курсовом проекте методом сортировки и узнать время сортировки массива.