Мегаобучалка Главная | О нас | Обратная связь

Метод подсчета сравнений




Введение

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

· Сравнение, определяющее упорядоченность пары элементов;

· Перестановка, меняющая местами пару элементов;

· Собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов данных до тех пор, пока все эти элементы не будут упорядочены.

 

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

Изучение и описание предметной области.

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

В начале необходимо отметить основные типы и виды сортировок, их основные характеристики. Это необходимо для выделения основных отличий рассматриваемых в курсовом проекте сортировок от других существующих методов сортировок. По рекомендованной литературе выполнить теоретическое сравнение алгоритмов сортировок, рассматриваемых в рамках курсового проекта. Построить блок-схемы, наглядно отображающие принцип работы алгоритмов сортировок методами быстрой сортировки, сортировки Шелла, сортировки слиянием.



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

Постановка задачи

В данной работе необходимо разработать программу, реализующую следующие задачи:

· Формирование одномерного динамического массива Mass c количеством элементов Kol, задаваемым пользователем,случайным образом.

· Сортировка массива Mass по возрастанию при помощи трех алгоритмов сортировки:

- Методом простого выбора.

- Методом простых вставок.

- Методом подсчета сравнений.

· Учет времени работы алгоритмов сортировки.

· Выведение данных о скорости работы алгоритмов на экран в виде гистограммы.

· Сохранение отсортированного массива в файл.

При написании программ для реализации сортировок массивов был использован язык программирования С++. Это один из широко используемых языков программирования, который можно использовать для написания программ, работающих в операционной среде Windows. Среда Borland C++ Builder 6- это сложный механизм, обеспечивающий высокоэффективную работу программиста.

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

Таблица 1

Наименование Обозначение Тип данных
Массив Mass Int
Переменная Kol,i long
Переменная SlSortTime Int
Переменная ShellSortTime Int
Переменная QSortTime Int
Файл f FILE
Массив Mass1 Int
Массив Mass2 Int
Массив Mass3 Int
Переменная vremya Int
Переменная start Int
Переменная end Int
Переменная i,j,k Int
Переменная tmp Int
Переменная max, n Int
Переменная x0, y0,w,h Int
Переменная del Float
Указатель *Mass1 Int
Указатель *Mass2 Int
Указатель *Mass3 Int

Логическое проектирование

Метод простого выбора

При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.

Алгоритм сортировки массива методом выбора:

1. Для исходного массива выбрать максимальный элемент.

2. Поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте).

3. Повторить п.п. 1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в нем максимальный элемент и поменять его местами с предпоследним (n-1)- м элементом массива, затем с оставшиеся (n-2)-мя элементами и так далее, пока не останется один элемент, уже стоящий на своем месте.

Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.

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

Метод простых вставок

Сортировка вставками — достаточно простой алгоритм. Как в и любом другом алгоритме сортировки, с увеличением размера сортируемого массива увеличивается и время сортировки. Основным преимуществом алгоритма сортировки вставками является возможность сортировать массив по мере его получения. То есть имея часть массива, можно начинать его сортировать. В параллельном программировании такая особенность играет не маловажную роль.

Сортируемый массив можно разделить на две части — отсортированная часть и неотсортированная. В начале сортировки первый элемент массива считается отсортированным, все остальные — не отсортированные. Начиная со второго элемента массива и заканчивая последним, алгоритм вставляет неотсортированный элемент массива в нужную позицию в отсортированной части массива. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент.

Метод подсчета сравнений

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N2), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N2 свидетельствует о том, что алгоритм неэффективен при большом N , т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.

 

 





Читайте также:





Читайте также:
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...

©2015 megaobuchalka.ru Все права защищены авторами материалов.

Почему 3458 студентов выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.005 сек.)