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

Федеральное государственное бюджетное образовательное  учреждение

высшего профессионального образования

"Московский  государственный технический университет  радиотехники,

электроники и  автоматики"

МГТУ МИРЭА

Факультет Кибернетики


 

КУРСОВОЙ ПРОЕКТ

по  дисциплине

«Микропроцессорные устройства  управления роботов и их программное обеспечение»

Тема курсового проекта «Сортировка массива чисел по возрастанию»

                                                               

                    

 		  

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

доцент, к.т.н.

Герасимов В. В.

Рецензент

 
   

 

Работа представлена к защите

«12» мая 2012 г.

 

     

«Допущен к защите»

«14» мая 2012 г.

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 2012

 

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Московский  государственный технический университет  радиотехники,

электроники и  автоматики"

МГТУ МИРЭА

Факультет Кибернетики

 
 

Утверждаю

   
 

«____» __________201___ г.

 

ЗАДАНИЕ

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

по дисциплине «Микропроцессорные устройства  управления роботов и их программное обеспечение»

 

Студент 

      • Тема «Разработка алгоритма и программы сортировки массива из 20 чисел по возрастанию»
  • Исходные данные:

13h, 11h, 01h, 17h, 07h, 03h, 21h, 32h, 32h, 12h, 42h, 34h, 22h, 14h, 55h, 11h, 17h, 77h, 31h, 12h.

 
 
    • Перечень вопросов, подлежащих разработке, и обязательного графического материала:

алгоритм (рис 1), программа, блок-схема  алгоритма

 
 
  • Срок представления к защите курсового проекта (работы): до «12» мая 2012 г.
 

Задание на курсовой

проект, выдал

«12» апреля 2012г.

    

Задание на курсовой

проект, получил

«12» апреля 2012г.

    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание:

Введение            4

Основная часть           5

Блок-схема алгоритма работы программы      7

Алгоритм работы программы         8

Листинг программы          9

Результаты выполнения программы              12

Заключение                           13

Список литературы                                                                                                                            14

 

 

Введение

 
Программы можно писать не только для x86 компьютеров. Более того, большая  часть процессоров в мире - НЕ x86. Основная часть микропроцессоров сейчас - это микроконтроллеры. В большинстве учебных заведений бывшего СССР изучение микроконтроллеров начинается с легендарного Intel 8051 (официальное название - MCS 51, также он известен как i8051 и MCS-51). У этого микроконтроллера есть assembler, очень похожий на ассемблер привычных нам процессоров x86 архитектуры. Этот контроллер применялся в старых клавиатурах, да и вообще много где он применялся. Будем называть этот микропроцессор Intel 8051 или MCS 51, потому что во всем мире он известен именно под этим названием.

 

Цель работы:

Необходимо отсортировать  по возрастанию массив из 20 шестнадцатеричных  чисел. Чтобы это сделать надо найти максимальный элемент и  поместить в конец массива, потом  второй по величине и поставить его  на предпоследнее место массива и т.д.

Особенности микроконтроллера

 
Intel 8051 — это 8 разрядный однокристальный микроконтроллер гардвардской архитектуры, впервые произведенный компанией Intel в 1980 году и предназначенный для использования во встраиваемых (embedded) системах. Он состоит из процессорного ядра (CPU), ОЗУ, ПЗУ, последовательного и параллельного порта, и еще небольшого количества дополнительных элементов. Программы для него можно писать на специализированном ассемблере, который очень напоминает ассемблер для x86-процессоров, или на языке С. Но, конечно, есть ограничения. У нас в распоряжении всего 128 байт ОЗУ (называется память DATA), 4 кбайта встроенного ПЗУ для хранения самой программы (память программ), и 64 кбайта в ПЗУ (называется XDATA - external data, или память данных). Зато есть прерывания.

 

 

 

 

 

 

 

 

 

 

 

Основная часть

Восьмиразрядные  высокопроизводительные  однокристальные  микроЭВМ (ОМЭВМ) семейства  МК51 выполнены по высококачественной n-МОП технологий (серия 1816) и КМОП технологии (серия 1830) .

Семейство МК51 включает пять модификаций ОМЭВМ (имеющих  идентичные основные характеристики), основное различие, между которыми состоит в реализации памяти программ и мощности потребления.

ОМЭВМ КР1816ВЕ51 и КР1830ВЕ51 содержат масочно-программируемое в процессе изготовления кристалла ПЗУ памяти программ емкостью 4096 байт и рассчитаны на применение в массовой продукции. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КМ1816ВЕ751 содержит ППЗУ емкостью 4096 байт со стиранием ультрафиолетовым излучением и удобна на этапе разработки системы при отладке программ, а также при производстве небольшими партиями или при создании систем, требующих в процессе эксплуатации периодической подстройки. За счет использования внешних микросхем памяти общий объем памяти программ может быть расширен до 64 Кбайт.

ОМЭВМ КР1816ВЕ31 и КР183ОВЕ31 не содержат встроенной памяти программ, однако  могут  использовать  до  64  Кбайт  внешней  постоянной  или  перепрограммируемой памяти программ и эффективно использоваться в системах, требующих существенно большего по объему (чем 4 Кбайт на кристалле) ПЗУ памяти программ.

Каждая из перечисленных выше микросхем  является соответственно аналогом БИС 8051, 80С51, 8751, 8031, 80С31 семейства MCS-51 фирмы Intel (США).

Каждая ОМЭВМ рассматриваемого семейства содержит встроенное ОЗУ  памяти данных емкостью 128 байт с возможностью расширения общего объема оперативной памяти данных до 64 Кбайт за счет использования внешних микросхем ЗУПВ.

Общий объем памяти ОМЭВМ семейства  МК51 может достигать 128 Кбайт: 64 Кбайт  памяти программ и 64 Кбайт памяти данных.

При разработке на базе ОМЭВМ  более сложных систем могут быть использованы стандартные ИС с байтовой организацией, например, серии КР580. В дальнейшем обозначение "МК51" будет общим для всех моделей семейства, за исключением случаев, которые будут оговорены особо. ОМЭВМ содержат все узлы, необходимые для автономной работы:

1) центральный восьмиразрядный  процессор;

2) память программ объемом 4 Кбайт (только КМ1816ВЕ751, КР1816ВЕ51 и КР1830ВЕ51);

3) память данных объемом  128 байт;

4) четыре восьмиразрядных программируемых  канала ввода-вывода;

5) два 16-битовых многорежимных  таймера/счетчика;

6) систему прерываний с пятью  векторами и двумя уровнями;

7) последовательный интерфейс;

8) тактовый генератор.

 

Аккумулятор. АСС — регистр аккумулятора. Команды, предназначенные для работы с аккумулятором, используют мнемонику "А", например, MOV А, Р2.Мнемоника "АСС" используется, к примеру, при побитовой адресации аккумулятора. Так, символическое имя пятого бита аккумулятора при использовании ассемблера ASM51 будет следующим:    АСС.5.

Регистр В. Используется во время операций умножения и деления. Для других инструкций регистр В может рассматриваться как дополнительный сверхоперативный регистр.

Регистр состояния программы. Регистр PSW содержит информацию о состоянии программы.

Указатель   стека   SP.   8-битовый   регистр,   содержимое   которого инкрементируется перед записью данных в стек при выполнении команд PUSH и CALL. При начальном сбросе указатель стека устанавливается в 07Н, а область стека в ОЗУ данных начинается с адреса 08Н. При необходимости путем переопределения указателя стека область стека может быть расположена в любом месте внутреннего ОЗУ данных микроЭВМ.

Указатель данных. Указатель данных (DPTR) состоит из старшего байта (DPH) и младшего байта (DPL). Содержит 16-битовый адрес при обращении к внешней памяти. Может использоваться как 16-битовый регистр или как два независимых восьмибитовых регистра.

Порт0—ПортЗ. Регистрами специальных функций Р0, Р1, Р2, РЗ являются регистры-"защелки" соответственно портов Р0, Р1, Р2, РЗ.

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

Регистры таймера. Регистровые пары (TH0.TL0) и (TH1.TL1) образуют 16- битовые счетные регистры соответственно таймера/счетчика 0 и таймера/счетчика 1.

Регистры управления. Регистры специальных функций IP, IE, TMOD, TCON, SCON и PCON содержат биты управления и биты состояния системы прерываний, таймеров/счетчиков и последовательного порта. ОМЭВМ при функционировании обеспечивает:

— минимальное время  выполнения команд сложения — 1 мкс;  
— аппаратное умножение и деление с минимальным временем выполнения команд умножения/деления — 4 мкс

 

 

 

 

 

Блок-схема алгоритма работы программы

 

Сначала программа записывает данные во внешнюю память. После  этого она считывает исходные числа из внешней памяти во внутреннюю и одновременно сортирует их.

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

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

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

Процесс продолжается до использования всех чисел из внешней памяти.

После этого отсортированные  элементы переписываются обратно во внешнюю память.

Использование памяти

Участки памяти:

Xdata:  0000h…0019h – область сортируемых чисел

data:  40h…53h - область, используемая для промежуточного хранения и сортировки чисел

Регистры:

DPTR: хранит адрес байта в XDATA (0000h..0019h).

A: используется как  буфер для передачи данных  из XDATA в DATA и для копирования  данных из одного участка памяти  в другой.

R0: хранит адрес обрабатываемого  элемента в DATA (40h..53h)

R1: используется как  локальный счетчик цикла.

R2: хранит данные из DPL для запоминания адреса текущего  самого большего элемента.

Участок 36h: хранит текущее самое большое число.

Рис 1. 
Листинг программы

 

    org 00h  ;смещение от начала

jmp start ;переход к началу

org 50h  ;память данных

 

Start:   

 

; ИНИЦИАЛИЗАЦИЯ

 

module_create_data:  ;Модуль  устанавливает начальные значения  байтам в XDATA с адресами 00h..09h

 

mov DPTR, #0000h ;адрес

mov A, #13h  ; 1-e число

movx @DPTR, A  ; занести число по адресу

inc DPTR  ;увеличить адрес на 1

 

mov A, #11h  ; 2-e число

movx @DPTR, A

inc DPTR

 

mov A, #01h  ; 3-e число

movx @DPTR, A

inc DPTR

 

mov A, #17h  ; 4-e число

movx @DPTR, A

inc DPTR

 

mov A, #07h  ; 5-e число

movx @DPTR, A

inc DPTR

 

mov A, #03h  ; 6-e число

movx @DPTR, A

inc DPTR

 

mov A, #21h  ; 7-e число

movx @DPTR, A

inc DPTR

 

mov A, #32h  ; 8-e число

movx @DPTR, A

inc DPTR 

 

mov A, #32h  ; 9-e число

movx @DPTR, A

inc DPTR

 

mov A, #12h  ; 10-e число

movx @DPTR, A

 

mov A, #42h  ; 11-e число

movx @DPTR, A

inc DPTR

 

mov A, #34h  ; 12-e число

movx @DPTR, A

inc DPTR

 

mov A, #22h  ; 13-e число

movx @DPTR, A

inc DPTR

 

mov A, #14h  ; 14-e число

movx @DPTR, A

inc DPTR

 

mov A, #55h  ; 15-e число

movx @DPTR, A

inc DPTR

 

mov A, #11h  ; 16-e число

movx @DPTR, A

inc DPTR

 

mov A, #17h  ; 17-e число

movx @DPTR, A

inc DPTR

 

mov A, #77h  ; 18-e число

movx @DPTR, A

inc DPTR

 

mov A, #31h  ; 19-e число

movx @DPTR, A

inc DPTR

 

mov A, #12h  ; 20-e число

movx @DPTR, A

 

 

 

 

;СОРТИРОВКА 
 
module_sort_massiv: метка начала сортировки 
 
mov R0, #53h 
metka1: метка главного цикла сортировки 
mov 54h, #00h 
mov R2, DPL 
jmp module_search_massiv переход на метку поиска макс 
 
metka_vozvrata1: метка возврата из поиска макс эл. 
 
mov DPL, R2 
mov A, #00h 
dec DPL 
movx @DPTR, A 
 
mov @R0, 54h 
dec R0 
cjne R0, #3Fh, metka1 
jmp module_data_to_xdata переход на метку вывода данных 
 
;ДОПОЛНИТЕЛЬНЫЕ МОДУЛИ 
 
module_search_massiv: начало кода поска макс эл массива 
mov DPTR, #0000h 
metka2: главный цикл поиска  
movx A, @DPTR 
inc DPTR 
mov R1, DPL 
cjne A, 54h, metka3  
 
metka_vozvrata2: перед возвратом 
cjne R1, #14h, metka2 переход на метку вложенного цикла 
jmp metka_vozvrata1 переход на возврат из поиска 
metka3: 
jc metka_vozvrata2 продолжаем сканировать 
mov 54h, A 
mov R2, DPL 
jmp metka_vozvrata2 пока все не переберем программа в цикле 
 
 
;ПЕРЕМЕЩЕНИЕ ОТСОРТИРОВАННЫХ ЧИСЕЛ ОБРАТНО ВО ВНЕШНЮЮ ПАМЯТЬ

 
module_data_to_xdata: 
mov DPTR, #0000h 
mov R0, #40h 
metka4: цикл вывода 
mov A, @R0 
movx @DPTR, A 
inc DPTR 
inc R0 
cjne R0, #54h, metka4 на метку цикла

 

final:

 

end.

 

 

Результаты выполнения программы:

до сортировки

После сортировки

13h

01h

11h

03h

01h

07h

17h

11h

07h

11h

03h

12h

21h

12h

32h

13h

32h

14h

12h

17h

42h

17h

34h

21h

22h

22h

14h

31h

55h

32h

11h

32h

17h

34h

77h

42h

31h

55h

12h

77h


 

 

 

Таблица команд и число  их выполнения:

mov DPTR, #0000h

21

mov R0, #53h

21

movx @DPTR, A

60

inc DPTR

420

inc R0

20

cjne R0, #3Fh, metka1

460

dec R0

20

mov @R0, 54h

20

mov A, #31h

40

mov 54h, #00h

20

mov R2, DPL

560

jmp metka_vozvrata

180

movx A, @DPTR

420

cjne A, 54h, metka3

400

jc metka_vozvrata2

400

mov 54h, A

140

mov DPL, R2

20

dec DPL

20

mov A, @R0

20


 

Время затраченное  программой на своё выполнение:

t =     5 + 20 + 20 + 40 + 60 + 20 + 100 + 80 + 40 + 400 + 40 + 60 + 1680 + 540 + 420 + 1200 + 800 + 280 + 1320 + 40 + 40 = 7305 тактов = 609 циклов = 203 мкс

 

Объём памяти занимаемый программой:

V = 24 * (1 + 20 + 20 + 20 + 20 + 20 + 20 + 40 + 400 + 20 + 560 + 180 + 420 + 400 + 400 + 440 + 20) + 12 * (1 + 20 + 20 + 20 + 40 + 20 + 140 + 20) = 74916 байт = 73Кб

 

Заключение

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

Литература:

  1. http://atdevil.ru/wp-content/uploads/2011/02/mcs51.pdf
  2. “Система команд микроконтроллеров MCS-51”, http://www.gaw.ru/html.cgi/txt/doc/micros/mcs51/asm/start.htm