Тема 2. Основная цель этой курсовой работы сравнение и анализ алгоритмов сортировки списка прямым выбором. 4

• Название: Основная цель этой курсовой работы сравнение и анализ алгоритмов сортировки списка прямым выбором. 4
• Дата: 28.04.2022
• Размер: 0.84 Mb.
• Имя файла: Тема 2.doc
• Тип: Реферат; #502797
• страница: 2 из 8

Основная цель этой курсовой работы - сравнение и анализ алгоритмов сортировки списка прямым выбором.

Объектом исследования в нашей курсовой работе будут алгоритм сортировки информации и алгоритм поиска данных.

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

Сразу надо отметить, вопросами анализа алгоритмов, группировкой, исследованием и методами их программирования в различные времена были заняты: Кнут Д., Ульман Дж., Левитин А., Цейтлин Г.Е., Гудман С., Хидетниеми С., Ахо А., Хлопккрофт Дж., Вирт Н., Лорин Г., Макконнелл Дж. и другие.

1 Постановка задачи и анализ предметной области

1. Основные понятия и определения

Сортировка - это процесс упорядочивания наборов данных одного типа по возрастанию или убыванию значения какого-либо признака. Задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием.

Массив - это однородный, упорядоченный структурированный тип данных с прямым доступом к элементам. Элементы массива объединяются общим именем и занимают в компьютере определенную конечную область памяти. К любому элементу массива можно обратиться, указав имя массива и индекс элемента в массиве.

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

Метод сортировки прямым выбором основан на следующих правилах:

• 
  Выбирается элемент с наименьшим ключом.
  
• 
  Он меняется местами с первым элементом a₀.
  
• 
  Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.
  

Пример алгоритма сортировки прямым выбором изображен на рисунке 1.



Рисунок 1 – сортировка прямым выбором

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

Упорядоченная последовательность – значения элементов возрастают с увеличением номера элемента. Пример: 3, 4, 8, 9, 12.

Неупорядоченная последовательность – элементы не располагаются по возрастанию или убыванию с увеличением номера элемента. Пример: 9, 4, 11, 46.

Упорядоченная в обратном порядке последовательность – значения элементов убывают с увеличением номера элемента. Пример: 87, 59, 42, 13, 7.

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

Структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

2. Постановка задачи на разработку программы

Сравнение и анализ алгоритмов сортировки массива прямым выбором.

1. 
   Запрограммировать следующие алгоритмы сортировки:
   
   1. 
      Классический прямой выбор. Сортировка массива.
      
   2. 
      Прямой выбор с одновременным поиском максимума и минимума. Сортировка массива.
      
2. 
   Выполнить сравнение времени сортировки перечисленными выше методами для:
   
   1. 
      Неупорядоченной последовательности;
      
   2. 
      Упорядоченной последовательности;
      
   3. 
      Упорядоченной в обратном порядке последовательности;
      
3. 
   Данные отобразить в табличной и графической формах. Графическая форма – график зависимости времени сортировки от размерности массива.