Сортировка массива методом прямого включения

Министерство образования и науки Украины

Симферопольский автотранспортный техникум

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

на тему:

СОРТИРОВКА МАССИВА ПРЯМЫМ ВКЛЮЧЕНИЕМ

Руководитель проекта

              Безменова Е.Ю.

Разработал студент

40-АКД группы

Темченко С.Г.                                       

2011

              ЗАДАНИЕ

Для курсового проекта

по курсу «Системное программирование» учащемуся ____ курса _____ группы

____________________________________________________________________

Симферопольского автотранспортного техникума.

Тема и исходные данные:

Тема задания:

____________________________________________________________________

____________________________________________________________________

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

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

Курсовой проект на указанную тему выполняется учащимися техникума в полном объёме:

Введение

1.Исследовательский раздел

2.Технологический раздел

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

              2.2.Комментированный исходный код решения

Заключение

Литература

Дата выдачи_____________

Срок окончания__________

Преподаватель руководитель КП

________________________

Задание получил__________

Содержание

ВВЕДЕНИЕ…………...........................................................................................4

1. Исследовательский раздел             

1.1. Массивы………………………………………………………………..5

1.2. Описание методов сотрировки массивов и их алгоритмы….......5

2. Технологический раздел

2.1. Постановка задачи и предлагаемый алгоритм решения……….12

2.2. Описание команд языка программирования Ассемблер...……..13

2.3. Описание команд языка программирования С++……………….13

2.4 Коментированный ход решения в С++…………………………....15

2.5  Коментированный ход решения в Ассемблере…………………..18

Заключение………………………………………………………………...22СПИСОК ЛИТЕРАТУРЫ…………………………………………………….23

введение

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

Задачей КП является разработка программы сортировки массива методом прямого включения на языках программирования С++ и Ассемблер.

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

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

1.1. Массивы

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

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

1.2. Описание методов сотрировки массивов и их алгоритмы

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

• метод выбора;

• метод пузырька;

• метод включения;

• метод быстрой сортировки.

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

1. Метод сортировки выбором

Исходный массив длиной N разбивается на две части: итог и остаток. Участок массива, называемый итогом, располагается с начала массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит исходные числа не отсортированной части исходного массива. Пусть первый элемент остатка является J-ым элементом массива.

Алгоритм сортировки выбором

Шаг 1. Полагается J:=0, т.е. считается, что итоговый участок - пуст.

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

Шаг 3. Если J < N-1, то повторяется Шаг 2. В противном случае - конец алгоритма, т.к. итог становится равным всему массиву. Конец алгоритма.

Рис. 1 Алгоритм сортировки выбором

2. Метод сортировки пузырьком

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

Алгоритм сортировки пузырьком

Шаг 1. Пусть J:=1 , т.е. итоговый участок состоит из одного элемента.

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

Шаг 3. После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной J, тем самым увеличивая отсортированную часть массива. Если J<N, то управление передается на Шаг 2, в противном случае - работа алгоритма завершена.

Конец алгоритма.

Рис. 2 Алгоритм сортировки пузырьком

3. Метод сортировки включением

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

Алгоритм метода включения

Шаг 1. Пусть J=1 , т.е. итоговый участок состоит из одного элемента.

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

Шаг 3. После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной J, тем самым увеличивая отсортированную часть массива. Если J < N, то управление передается на Шаг 2, в противном случае - работа алгоритма завершена. Конец алгоритма.

Рис.3 Алгоритм сортировки включением

5. Метод быстрой сортировки

Исходным является массив А с номерами элементов от First до Last. В алгоритме используются еще два индекса массива, обозначенные как Index и ContrIndex. Первый из них всегда указывает на переставляемый элемент, а второй — на элемент, который сравнивается по значению с переставляемым. В процессе вычислений применяются переменная h (равная либо 1, либо -1) - шаг движения индексов навстречу друг другу, используемая для обозначения направления движения индекса ContrIndex, и логическая переменная Condition (равная либо TRUE, либо FALSE), используемая для изменения условия сравнения на противоположное при обратном движении индекса ContrIndex.

Алгоритм быстрой сортировки

Шаг 1. Если First >= Last, то происходит выход из алгоритма. В противном случае полагается h:=1, Condition:=TRUE, Index:=First, ContrIndex:=Last и делаются шаги: Шаг 2 - Шаг 3.

Шаг 2. Пока Index не равно ContrIndex, делаются шаги: Шаг 2а -Шаг 2b.

Шаг 2а. Если справедливо ((A[Index]>A[ContrIndex])=Condition), то переставляются как сами элементы, на которые указывают Index и ContrIndex, (Val:=A[Index], A[Index]:=A[ContrIndex], A[ContrIndex]:=Val), так и сами вспомогательные индексы массивов (Val:=Index, Index:=ContrIndex, ContrIndex:=Val). Затем меняется направление движения (h:= -h) и условие сравнения (Condition: = not Condition). В процессе таких перестановок слева от переставляемого элемента всегда будут находиться меньшие значения, а справа - большие значения.

Шаг 2b. Сдвигается вспомогательный индекс массива ContrIndex навстречу индексу Index , т.е. ContrIndex:= ContrIndex +h.

Шаг 3. Перед выполнением этого шага индексы Index = ContrIndex и элемент A[Index] находится на нужном месте. Т.е. исходный массив разбит на три части: часть массива до этого элемента, значения в котором меньше величины A[Index], часть массива после этого элемента с значениями большими значения A[Index] и сам этот элемент A[Index]. Поэтому для дальнейшего упорядочивания массива достаточно рекурсивно обратиться к алгоритму быстрой сортировки два раза: для первой и второй частей массива. Т.к. длина сортируемых участков массива уменьшается, то в итоге алгоритм конечен и после применения алгоритма массив будет полностью отсортирован. Конец алгоритма.

Рис. 4 Алгоритм быстрой сортировки

2. ТЕХНОЛОГИЧЕСКИЙ РАЗДЕЛ

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

Задачей КП является разработка программы сортировки массива методом прямого включения на языках программирования С++ и Ассемблер.

Принцип метода заключается в следующем:

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

Таким образом, алгоритм будет состоять из (n-1)-го прохода (n - размерность массива), каждый из которых будет включать четыре действия:

        взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;

        поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;