Сортировка массива методом прямого включения
Министерство образования и науки Украины
Симферопольский автотранспортный техникум
пояснительная записка к курсовому проекту
на тему:
СОРТИРОВКА МАССИВА ПРЯМЫМ ВКЛЮЧЕНИЕМ
Руководитель проекта
Безменова Е.Ю.
Разработал студент
40-АКД группы
Темченко С.Г.
2011
ЗАДАНИЕ
Для курсового проекта
по курсу «Системное программирование» учащемуся ____ курса _____ группы
______________________________
Симферопольского автотранспортного техникума.
Тема и исходные данные:
Тема задания:
______________________________
______________________________
Постановка задачи:
______________________________
______________________________
______________________________
______________________________
______________________________
Курсовой проект на указанную тему выполняется учащимися техникума в полном объёме:
Введение
1.Исследовательский раздел
2.Технологический раздел
2.1.Постановка задачи и предлагаемый алгоритм решения
2.2.Комментированный исходный код решения
Заключение
Литература
Дата выдачи_____________
Срок окончания__________
Преподаватель руководитель КП
________________________
Задание получил__________
Содержание
ВВЕДЕНИЕ…………..................
1. Исследовательский раздел
1.1. Массивы……………………………………………………………
1.2. Описание методов сотрировки массивов и их алгоритмы….......5
2. Технологический раздел
2.1. Постановка задачи и предлагаемый алгоритм решения……….12
2.2. Описание команд языка программирования Ассемблер...……..13
2.3. Описание команд языка программирования С++……………….13
2.4 Коментированный ход решения в С++…………………………....15
2.5 Коментированный ход решения в Ассемблере…………………..18
Заключение……………………………………………………
введение
Целью курсового проекта является рассмотрение различных алгоритмов сортировки массива. В качестве практической проблемы, требующей решения, рассматривается известная задача сортировки (упорядочивания) массива в порядке возрастания (убывания) его элементов. При решении этой задачи требуется исходный массив, содержащий произвольные целые числа, преобразовать к виду, когда каждый элемент массива находится перед другим элементом этого массива, если его значение меньше (больше), чем значение сравниваемого элемента.
Задачей КП является разработка программы сортировки массива методом прямого включения на языках программирования С++ и Ассемблер.
Для организации большого количества данных одного типа, используются массивы. Массивы позволяют быстро обращаться к нужным данным, зная индекс. Применение данной структуры очень распространено, и эффективность доказана временем. При использовании массивов существенно сокращается время на поиск необходимого фрагмента данных, а так же пропадает необходимость использования большого количества переменных для отдельной информации. При необходимости упорядочивания данных в массиве, используется сортировка. Существует не один способ сортировки данных, по разным принципам и правилам.
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])=
Шаг 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 в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
вставка взятого элемента в найденную i-ю позицию.
2.2 Описание команд языка программирования Ассемблер
Команда | Описание |
Equ | Определение константы |
Mov | Копирование значения |
Xor | Логическая операция «исключающее ИЛИ» |
Lea | Сохранение адреса второго операнда, в первый |
Int | Вызов прерывания |
Add | Сложение операндов |
Jmp | Безусловный переход |
Shl | Умножение на степень двойки |
Cmp | Сравнение операндов |
Jle | Условный переход, если первый операнд =< второго операнда |
Jg | Условный переход, если первый операнд > второго операнда |
Inc | Инкремент, увеличение значения на единицу |
Jl | Условный переход, если первый операнд < второго операнда |
Loop | Организация цикла |
End | Конец программы |
2.3 Описание команд языка программирования С++
Команда | Описание |
Include | Подключение библиотек |
Int | Указание целочисленного типа данных |
char | Указание символьного типа данных |
For | Цикл со счетчиком |
Return | Возвращение чего-либо |
printf | Вывод информации на экран |
scanf | Ввод информации с клавиатуры |
If | Условие |
Getch | Ожидание нажатия кнопки на клавиатуре |
Endl | Конец строки |
3.2.1.Комментированный исходный код решения в С++
#include <stdio.h> //заголовочный файл стандартной библиотеки языка Си, содержащий определения макросов, константы и объявления функций и типов, используемых для различных операций стандартного ввода и вывода.
#include <conio.h> //консольный ввод-вывод
int vibor (int in[], int n); //
void main ()
{
int m=0; //объявление целочисленной переменной m значения 0
int s; // объявление целочисленной переменной s
int vvh [100]; //объявление количества целочисленных переменных
//Ввод массива
char f [80]; //объявление количества символьных переменных
printf("\n vvedite chislo elementov v massive: ", f);
scanf ("%d", &m); //Узнаем размер массива
printf("\n vvedite cherez probel celie chisla: ", f);
for (int j=0; j<m; j++)
scanf ("%d", &vvh[j]); //Заполнение массива
printf ("\n");
s = vibor (vvh, m); //Сортировка методом включения
getch(); //экран не закрывается пока не нажата любая клавиша
}
int vibor (int in[], int n)
{
int sravnen=0; //Характеристика трудоемкости (число стравнений)
//Вывод сообщений
char f [80];
printf("\n sortirovka metodom priamogo vklucheniya: \n", f);
//Начало сортировки
int i;
for (i=0; i<n-1; i++) //n-1 раз ищем наименьший элемент
{
int imin=i; //принимаем за наименьший первый из рассматриваемых элементов
//Поиск минимального элемента
for (int j= i + 1; j<n; j++)
{
if (in[j]<in[imin]) imin = j;
sravnen++;
}
int a = in[i]; in[i]=in[imin]; in[imin]=a; //Обмен элементов
}
//Вывод результатов работы программы
for (i=0; i<n; i++)
printf ("%d ", in[i]);
printf ("\n");
return sravnen; //Возвращаем число сравнений
}
}
2.2.1 Комментированный исходный код решения в Ассемблере
assume CS: code, DS: data
data segment ;сегмент данных
mas dw 9 ,2 ,4 ,0 ,1 ,9 ,3 ,6 ,5 ,8 ;заданные числа массива
mes1 db 'Исходный массив: $',10,13,
mes2 db 10,13,'Отсортированный массив: $'
n equ 9
i dw 0
j dw 0
temp dw 0
pkey db 10,13,'Нажмите "ОК" в окне... $'
stk segment stack
dw 128 dup (0) ;резервируется память объемом 128 слов
stk ends
code segment
begin: ;начало программы
mov AX, data ;заносится значение переменной data в ;AX
mov DS, AX ;заносится значение переменной AX в
;DS
mov AH, 09h ;заносится значение 09h в переменную
;AH
mov DX, offset mes1 ;заполнение исходного массива
int 21h
mov cx,10 ;заносится значение 10 в переменную СХ
mov si,0 ;заносится значение 0 в переменную SI
show_primary: ;цикл заполнения исходного массива
mov dx,mas[si];заносится значение переменной ;mas[si] в переменную
add dl,30h
mov ah,02h ;
int 21h ;вывод значения на экран
add si,2
loop show_primary ;цикл будет повторяться до тех пор пока не заполниться массив
internal: ;внутренний цикл
mov j,9
jmp cycl_j ;переход к cycl_j
exchange: цикл обмена
mov bx,i ;поместить в bx значение i
shl bx,1 ;сдвиг значения bx на 1 влево
mov ax,mas[bx] ;поместить в ax
;значение;mas[bx]
mov bx,j ;поместить j в bx
shl bx,1 ;сдвиг значения bx на 1 влево
cmp ax,mas[bx] ;сравнение элемента mas[bx] с ax
jle lesser ;переход к lesser
mov bx,i ;поместить i в bx
shl bx,1 ;умножение bx на 2
mov temp,ax ;поместить ax в temp
mov bx,j ;поместить j в bx
shl bx,1
mov ax,mas[bx]
mov bx,i
shl bx,1
mov mas[bx],ax
mov bx,j
shl bx,1
mov ax,temp
mov mas[bx],ax
lesser:
dec j ;уменьшить j на 1
cycl_j:
mov ax,j
cmp ax,i
jg exchange
inc i ;
cmp i,n ;
jl internal
mov AH, 09h ;
mov DX, offset mes2 ;
int 21h ;
mov cx,10 ;
mov si,0 ;
show:
mov dx,mas[si] ;
add dl,30h ;
mov ah,02h ;
int 21h ;
add si,2 ;
loop show ;
mov AH, 08h ;
lea dx, pkey ;
mov ah, 9 ;
int 21h ; output string at ds:dx
; ожидание нажатия клавиши....
mov ah, 1
mov AH, 4Ch
mov AL, 00h
int 21h
mov ax, 4c00h ;выход в операционную систему
int 21h ;
code ends ;
Заключение
В процессе выполнения курсового проекта были изучены алгоритмы сортировки массивов. Была составлена программа на языках программирования С++ и Ассемблер, реализующая сортировку массива методом прямого включения.
Из данного курсового проекта можно сделать вывод, что языки программирования Ассемблер и С++ до сих пор востребованы и неотъемлемо связаны с компьютером. И поэтому самой быстрой программой на данном оборудовании всегда будет программа, написанная на ассемблере. Данная программа позволяет переводить текст с языка, понятного человеку, в язык, понятный процессору.
Рис. 5 Пример работы программы
Рис. 6 Результаты выполения программы
СПИСОК ЛИТЕРАТУРЫ
1. Р. Марек - Ассемблер на примерах. Базовый курс. НиТ, 2005. – 233 с
2. Архангельский А.Я. Программирование в C++ Builder 6. БИНОМ, 2003. – 1152 с.
3. Р.Лафоре - Объектно-ориентированное программирование в С++. Питер, 2004. – 922 с
4. Пирогов В.Ю. ASSEMBLER Учебный курс. Нолидж, 2001. - 846 с
5. Дональд Э. К. Искусство программирования, том 3 Сортировка. Вильямс, 2007. – 824 с