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

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

Введение

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Введение

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

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

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

· Линейный выбор;

· Метод минимального (максимального) элемента;

· Метод «Пузырька»;

· Челночная сортировка;

· Сортировка вставки.

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

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

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

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

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

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

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

· объектно-ориентированное программирование;

· модульное программирование;

· структурное программирование.

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

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

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

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

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

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

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

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

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

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

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

· линейный выбором элемента;

· метод минимального (максимального) элемента;

· метод сортировки обменами ("пузырьковая" сортировка);

· челночная сортировка;

· метод сортировки вставками;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

программирование алгоритм массив сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция сортировки вставки.

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

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

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

Функция заполнения исходного массива.

Входные параметры: отсутствуют.

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

Изначально будет введена размерность массива. Для ввода будет предусмотрена защита - сравнение введенной длины. Если длина будет меньше 2, то выдастся сообщение об ошибки. При активации кнопки «Заполнить», будет вызвана функция, в которой определяется длина массива. Затем проверка условия, каким способом будет заполнен массив. Если пользователь выберет случайное заполнение массива, то в цикле с помощью функции random(), массив будет заполнен случайными числами. Если будет выбран способ заполнения вручную, то будет очищен массив, организован цикл, в котором заполняем массив вручную.

Если не будет выбран ни один из предложенных способов заполнения, то выдастся сообщение об ошибке.

Функция для очистки массива

При активации кнопки «Очистить», будет вызвана функция Clear(), которая очищает массив.

Главная функция

В пользовательском интерфейсе, при активации кнопки «Сортировать», будет вызвана функция. В этой функции будет предусмотрена проверка условия, какое направление сортировки выберет пользователь, если по возрастанию, то переменная, которая передается в функции сортировки, будет равна 1, а если по убыванию, то переменная будет равна -1, такое значение переменной предусмотрено для смены знака неравенства с больше на меньше, чтобы изменить направление сортировки.

Будет предусмотрена проверка условий: если не выбран метод сортировки и ее направление, то выдастся сообщение об ошибке.

После будет вызываться функции:

· сортировка линейным выбором;

· сортировка методом минимального (максимального) элемента;

· сортировка методом «Пузырька»;

· челночная сортировка;

· сортировка вставкой.

Функция выхода из программы

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

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

void lineset(int *&mas, int size, int p)



void mm (int *mas, int size, int p )

void puz (int *&mas, int size, int p)



void chel (int *&mas, int size, int p)

void vstav (int *&mas, int size, int p)

void __fastcall TForm1::ZapolnenieClick(TObject *Sender)

void __fastcall TForm1::SortClick(TObject *Sender)

void __fastcall TForm1::CloseClick(TObject *Sender)

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

Программа разработана для сортировки массивов. Запуск программы осуществляется двойным кликом по файлу SortArray.exe под управлением ОС Windows ХР/7/8, не требует большого количества системных ресурсов, имеет удобный пользовательский интерфейс.

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

Для начала работы надо ввести размерность исходного массива от 2 до 10. Если появится окно ошибки, то введена не правильная размерность или пытались ввести символы или знаки. В окне ошибки нажимается «ОК» и заново вводиться размерность массива.

Затем нужно выбрать способ заполнения массив и нажать кнопку «Заполнить». Если способ не выбран, выдается сообщение с предложением выбрать способ заполнения. Если выбран способ заполнения «Вручную», то активировав полосу Исходного массива, начинаем ввод, чтобы передвигаться по ячейкам массива можно: ЛКМ активировать каждую ячейку или после ввода каждого элемента массива нажимать клавишу Enter и передвигаться по ячейкам с помощью клавиш управления курсором. Если же выбран способ заполнения «Случайно», то массив заполниться элементами случайно, выбрав числа из диапазона от 0 до 200. После того как Исходный массив заполнен выбираем метод сортировки. В этой программе представлены пять основных методов сортировок:

· Линейный выбор;

· Метод мин и макс;

· Метод «Пузырька»;

· Челночная сортировка;

· Сортировка вставки.

Затем выбираем направление сортировки:

· По возрастанию;

· По убыванию.

И нажимаем по кнопке «Сортировать». Если не выбран метод сортировки и направление, то программа предложит выбрать. Отсортированный массив отобразиться во второй полосе.

ЗАКЛЮЧЕНИЕ

В данном курсовом проекте при разработке программы были закреплены навыки объектно-ориентированного программирования на языке С++. Среды разработки программы Borland C++ и Embarcadero RAD Studio XE2. Освоены алгоритмы пяти основных сортировок:

· Линейный выбор;

· Метод мин и макс;

· Метод «Пузырька»;

· Челночная сортировка;

· Сортировка вставки.

При разработке пользовательского интерфейса, были освоены основные объекты и их свойства. При оформлении курсового проекта изучено оформление прикладной документации согласно ГОСТу.

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

1. Шолмов Л.И. Руководство по турбо Си. М.: Наука, 1994. - 94-98с.

2. Уинер Р. Язык Турбо Си: Пер. с англ. - М.: Мир, 1991. - 384 с.

3. Керниган Б.В, Ричи Д.М. Си для профессионалов. М.: Энергия, 1996.- 213 с.

4. Грейд Дж. Математическое программирование. М.: Наука, 1987.- 241 с.

5. Либерман М. Алгоритмы сортировки массивов. М.: Наука, 1997. - 43-81с.

Размещено на Allbest.ru