Методы сортировки массивов

Содержание

Введение 4

1. Алгоритмическое обеспечение 5

2. Программная реализация 12

3. Тестирование 19

4. Встроенная справка 24

5. Инструкция программисту 29

6. Инструкция пользователю 31

7. Инструкция по установке 33

Заключение 37

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

Приложение 39

Введение.

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

Задачами курсовой работы являются:

 получение навыков самостоятельной разработки и реализации алгоритмов;

 закрепление полученных знаний во время прохождения дисциплины «Структуры и алгоритмы обработки информации»;

 приобретение навыков разработки и отладки на языке высокого уровня программных средств;

 практическое освоение библиотек и возможностей программирования на языке высокого уровня;

 приобретение практических навыков оформления и выпуска документации в соответствии с ГОСТ.

1. Алгоритмическое обеспечение.

Cортировки осуществляются следующим образом:

1. Просмотр количества элементов в полученных массивах элементов.

2. Метод пузырька. Сложность: О(n2).

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются n-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма). (Рисунки 1-2).

Например: массив A={5,1,2,3}.

Действия: 1) A = {5,1,2,3}, 2) A = {1,5,2,3}, 3) A = {1,2,5,3}, 4) A = ={1,2,3,5}

Рисунок 1 – Блок-схема метода пузырька

Рисунок 2 – Продолжение блок-схемы метода пузырька

3. Метод выбора.

Сложность: О(n2).

1. В неотсортированном подмассиве ищется локальный максимум (минимум). 2. Найденный максимум (минимум) меняется местами с последним (первым) элементом в подмассиве. 3. Если в массиве остались неотсортированные подмассивы — см. пункт 1. (Рисунок 3)

Например: массив A={3,2,5,7,8,1}.

Действия: 1) A = {1,2,5,7,8,3,9}, 2) A = {1,2,5,7,8,3,9}, 3) A = ={1,2,3,7,8,5,9}, 4) A = {1,2,3,5,8,7,9}, 5) A = {1,2,3,5,7,8,9}, 6) A = ={1,2,3,5,7,8,9}.