Сортировка массивов данных

 

СОДЕРЖАНИЕ

 

 

Введение  3

1  ТЕОРЕТИЧЕСКИЙ  РАЗДЕЛ

1.1 Описание  языка программирования  4

1.2 Теоретический материал  5

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

2 ПРАКТИЧЕСКИЙ  РАЗДЕЛ

2.1 Эскизный проект 9

2.2 Технический проект  13

2.3 Инструкция  пользователя  22

ЗАКЛЮЧЕНИЕ  24

СПИСОК ЛИТЕРАТУРЫ  25

ПРИЛОЖЕНИЕ А Листинг программы  26

ПРИЛОЖЕНИЕ Б Результат работы программы  34

Графический материал:

СХЕМА АЛГОРИТМА  на отдельных листах

ИЛЛЮСТРАЦИИ  на отдельных листах

 

 

Введение

 

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

Необходимость отсортировать какие-либо величины возникает в программировании очень часто. Например, входные данные подаются "вперемешку", а нашей программе удобнее обрабатывать упорядоченную последовательность. Еще в упорядоченном массиве легче осуществлять поиск. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз.

Практическое значение выбранной темы – осуществление пяти основных методов сортировки:

• Линейный выбор;
• Метод минимального (максимального) элемента;
• Метод «Пузырька»;
• Челночная сортировка;
• Сортировка вставки.

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

В частности в данном курсовом проекте осуществлены следующие алгоритмы: введение исходного массива (вручную или случайно), выбор метода сортировки, направление сортировки и 5 методов сортировки.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1 ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1. Краткое описания языка программирования С++

Язык C++ представляет собой набор команд, которые говорят компьютеру, что необходимо сделать. Этот набор команд, обычно называется исходный код, исходный код или просто код. Командами являются или «функции» или «ключевые слова». Ключевые слова(зарезервированные слова С/С++) являются основными строительными блоками языка. Функции являются сложными строительными блоками, так как записаны они в терминах более простых функций.

Он прост  в понимании, и в применении, поддерживаются различные технологии и стили программирования, такие как:

• объектно-ориентированное программирование;
• модульное программирование;
• структурное программирование.

Объектно-ориентированное программирование - метод программирования, имитирующий способы, какими по нашему представлению выполнены предметы.

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

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

Структурное  программирование является одним из методов улучшающим программу. Оно служит для предотвращения и обнаружения логических ошибок.

 

 

 

 

 

 

 

 

 

 

2. Теоретический материал

 

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

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

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

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

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

  При разработке программы  можно воспользоваться различными  алгоритмами. Наиболее известными  являются следующие:

• линейный выбором элемента;
• метод минимального (максимального) элемента;
• метод сортировки обменами ("пузырьковая" сортировка);
• челночная сортировка;
• метод сортировки вставками;

 

Алгоритм линейного  выбора  элемента

 

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

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

 

Алгоритм метода минимального (максимального) элемента.

 

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

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

 

Алгоритм сортировки методом «Пузырька»

 

 Метод "пузырька" один из  самых простых методов внутренней  сортировки. Суть алгоритма состоит  в последовательном просмотре  массива от конца к началу  или от начала к концу и  сравнении каждой пары элементов  между собой. При этом "неправильное" расположение элементов устраняется  путем их перестановки.

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

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

 

Алгоритм челночной сортировки

 

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

 

Алгоритм сортировки вставками

 

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

Данный алгоритм также обладает слишком низким быстродействием.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

Условия для решения поставленной задачи:

Сортировка. Под сортировкой понимается перегруппировка заданного множества элементов в некотором заданном порядке. Сортировку  называют внутренней, если все элементы хранятся в оперативной памяти. Основное требование к методам сортировки - экономное использование времени процессора и оперативной памяти.    Необходимо реализовать сортировку целочисленного массива, содержащего не менее 100 элементов, по убыванию, по возрастанию (по выбору пользователя).

Предусмотреть сортировку следующими методами:

• Линейный выбор. Используется вспомогательный массив . В исходном массиве находится наибольший (наименьший) элемент и пересылается во вспомогательный массив. В исходном массиве этот элемент заменяется величиной, заведомо меньшей (большей) любого элемента. Операция повторяется до тех пор, пока все элементы исходного массива не будут перенесены во вспомогательный массив.

• Метод минимального  (максимального) элемента  аналогичен предыдущему, но без использования  вспомогательного массива. Вместо пересылки во вспомогательный массив, элемент переставляется на соответствующее место.

• Метод “пузырька”. Производится перестановка пар соседних элементов, не соответствующих условию сортировки. За один просмотр один элемент переставляется на свое место.

• Челночная сортировка. Алгоритм подобен методу “пузырька” , но при возникновении необходимости перестановки пары элементов, элемент переставляемый вверх, переставляется не на одну позицию, а на сколько это возможно.

• Сортировка вставки. Такую сортировку можно производить параллельно вводу элементов массива. Каждый элемент вставляется в уже упорядоченный массив.

 

 

 

2 ПРАКТИЧЕСКИЙ РАЗДЕЛ

 

2.1. Эскизный проект

 

Программа будет содержать следующие функции:

 

Функция сортировки линейным выбором.

 

Входные параметры: исходный массив и его размерность.

Выходные параметры: результирующий массив.

Будут объявлены: переменная с наибольшим (наименьшим) значением, для сравнения с элементами исходного массива и переменная для запоминания номера элемента в  исходном массиве.

Организуются вложенные циклы:

Внешний цикл будет проходить по результирующему массиву. Внутренний цикл по исходному массиву. Во внутреннем цикле будет сравнение  элементов исходного массива с переменной наибольшего (наименьшего) значения. Если элемент массива меньше (больше) значения переменной, то запоминаем его и его номер. После заносим элемент в результирующий массив.

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

 

Функция сортировки методом  минимального (максимального) элемента.

 

Входные параметры: исходный массив и его размерность.

Выходные параметры: результирующий массив.

Объявляться переменная для сортировки массива, через третью переменную.

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

Во внешнем цикле меняем местами. Текущий элемент заносим в переменную, на его место ставим тот элемент, номер которого мы запомнили и из переменной заносим текущий элемент на место следующего.

 

Функция сортировки методом «Пузырька».

 

Входные параметры: исходный массив и его размерность.

Выходные параметры: результирующий массив.

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