Алгоритм «Поразрядная сортировка»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

 

1. Задание

 

Разработать программу для OS MS-DOS "Поразрядная сортировка", Использовать средства встроенного Ассемблера, реализующие алгоритм, работу с файла (считывание из файла), пользовательский интерфейс.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

2.1 Алгоритм «Поразрядная  сортировка»

 

Поразрядная сортировка  — алгоритм сортировки за линейное время.

Алгоритм сортировки, числа  сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

 

При MSD сортировке последовательность сортируется по старшему значимому  двоичному разряду так, чтобы  все ключи начинающиеся с 0 оказались  перед всеми ключами начинающимися  с 1. Для этого необходимо найти  крайний слева ключ Ki, начиющийся с 1, и крайний справа ключ Kj, начиющийся с 0. После чего Ki и Kj меняются местами, и процесс повторяется, пока не получится i > j. Пусть F0 — множество элементов  начинающихся с 0, F1 — множество всех остальных элементов. Будем к F0 применять  поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F0 полностью  не рассортируется. Затем проделаем  то же самое с F1.

Вместо сравнения N-й битовой  позиции в слове сравнивается N-й байт строки.

 

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

 

N-й (для N > 0) проход  выполняется последовательно над  каждой корзиной, полученной на (N - 1)-м проходе, с делением её  на «подкорзины». В этом проходе  сравниваются N-ные символы каждой  строки.

 

Операция завершается  при N, равном максимальной длине строки, или же в ситуации, когда все  «подкорзины» получили длину 1.

 

 

.

2.2 Выбор языка и среды разработки

 

В процессе моего обучения мною были освоены 2 языка программирования: Turbo Pascal и Си. Для реализации программы в качестве основного был выбран язык программирования Turbo Pascal, который представляется мне наиболее оптимальным для разработки MS-DOS приложений и который отлично подходит для реализации заданий средней сложности, какой и является моя программа. Данный язык мне кажется наиболее удобным, ясным и понятным для программирования.

Разработка программы  велась в среде Turbo Pascal 7.0. Система программирования Turbo-Pascal была разработана в середине 80-х годов фирмой Borland International (США). Turbo-Pascal включает в себя как язык программирования - одно из расширений языка Pascal для ЭВМ типа IBM, так и среду, предназначенную для написания, отладки и запуска программ.   Практически он полностью реализует аппаратные возможности персонального компьютера фирмы IBM и совместимых с ним. Система имеет два основных достоинства: простота и естественность языка программирования Pascal, великолепные сервисные возможности диалоговой среды программирования фирмы Borland.  Язык характеризуется расширенными возможностями по сравнению со стандартом, хорошо развитой библиотекой стандартных модулей,  позволяющих использовать возможности операционной системы,  создавать оверлейные структуры, организовывать ввод-вывод , формировать графические изображения и т.д.

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

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

2.3Описание переменных

Описание переменных, используемых в исполнительном файле RAZR.PAS приведено в таблице 1.

Таблица 1.Описание переменных исполнительного файла RAZR.PAS

 

 

Идентификатор	Тип данных	Назначение
lng	integer	Хранит длину строки
s	string	Строка для вывода на экран  текста
f	txt	Переменная привязки файла  с входными данными
g	txt	Переменная привязки файла  с выходными данными
ic	integer	Переменная-счётчик
p	integer	Переменная-счётчик
n	integer	Переменная-счётчик
m	string	Массив входных значений
gf	string	Массив выходных значений
ks	string	Переменная для связи  массива и файла

 

2.4 Описание  процедур

 

Все процедуры в исполнительном файле RAZR.PAS приведены в таблице 2.

 

Таблица 2. Процедуры модуля RAZR.PAS

Идентификатор	Назначение
MainMenu	Вывод меню

 

Таблица 2. Процедуры модуля RAZR.PAS(Продолжение)

Идентификатор	Назначение
Vihod	Выход из программы
About	О программе
MenuSpr	Вывод информации о входных  данных
ZapVFail	Вывод информации о записи данных
Schit	Считывание данных из файла
Zapis	Запись данных в файл
RazSort	Поразрядная сортировка

2.5 Комплект  файлов, входящих в состав программы

 

В комплект готовой программы  входят файлы: RAZR.PAS, RAZR.EXE, in.txt

2.6 Интерфейс

При запуске исполняемого файла программы BINARNIY.EXE появляется основное окно программы (Рисунок 1.)

Рисунок 1.Основное меню программы.

При нажатии на 1, появляется окно (Рисунок 2)

Рисунок 2.Окно по нажатии пункта 2.

При нажатии пункта 2, происходит запуска алгоритма «Поразрядной сортировки» (Рисунка 3).

Рисунок 3.Запуск алгоритма  поиска.

При нажатии пункта 3, происходит сохранение в файл под названием  OUT.txt (Рисунок 4).

Рисунок 4.Сохранение в файл.

По нажатию пункта 4 происходит вывод справочной информации (Рисунок  5).

Рисунок 5.Справочная информация

По нажатию пункта 0 происходит выход из программы(Рисунок 6)

 

Рисунок 6.Выход из программы

 

2.7 Тестирование программы

 

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

• Celeron 433, 128Mb ОЗУ, RivaTNT-2, OC Windows Me;
• AMD 64, 512Mb ОЗУ, 3.0Ггц, Radeon X9600, OC Windows XP SP2;
• Intel Pentium 4, 2.8 GHz, 512 Mb ОЗУ, Sapphire ATI Radeon 9600 XT,  ОС Windows XP Sp 2;

 

• Intel Celeron D 2.6 GHz, 512 Mb ОЗУ, NVidia GeForce 6600,
• OC Windows XP SP2;
• Intel Pentium 3 733 Mгц, 420Mb ОЗУ,  GeForce2 440 MX,
• OC Windows XP SP2;

В процессе тестирования никаких  ошибок и неисправностей не выявлено. Программа работает стабильно и  без ошибок.

 

 

 

 

 

 

 

Заключение

 

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

Все выше указанные задачи были успешно реализованы на языке  Pascal, с применением «ассемблерных вставок», что значительно увеличивает скорость работы алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1. Кнут Д., Искусство программирования для ЭВМ, т. 3 "Сортировка и поиск", М., Мир, 1978
2. Вирт Н., Алгоритмы и структуры данных, М., Мир, 1989.

 

3. Абрамов С.А., Зима В.С. Начало программирования на языке Паскаль. – М.: Наука, 1987. – 112 с.
4. Вальвачев А.Н., Крисевич В.С. Программирование на языке Паскаль для персональных ЭВМ ЕС: Справочное пособие. – Мн.: Вышэйшая школа, 1989. – 223 с.
5. Дробышевский Р.В., Лифенко А.П., Персональный компьютер для начинающих. – Л.: ИМА–пресс, 1990. – 88 с.
6. Зуев Е.А. Язык программирования Turbo Pascal 6.0. – М.: Унитех , 1992. – 298 с.
7. Котов В.М., Волков B.А., Лапо И.А., Методы алгоритмизации. – М.: Народная асвета, 1997. – 159 с.
8. Павловский А.И., Пупцев А.Е., Гращенко П.Л, Информатика 10. – М.: Народная асвета, 2000. – 222 с.
9. Фаронов В.В. Программирование на персональных ЭВМ в среде Турбо Паскаль. – М.: Изд-во МГТУ, 1990. – 590 с.
10. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс: Учеб. пособие. – М.: Нолидж, 1998. – 616 с.

 

 

 

 

 

Приложение

Ниже приведён листин разрабатываемой  программы:

program razrSort;

 

uses

  Crt;

 

var

  buf: char;

  lng, i: integer;

  s: string;

  NameTxt: string;

  f,g:Text;

    ic,p,n:integer;

    m:array [1..100] of string;

    gf:array [1..100] of string;

    ks:string;

    ppc:integer;

    psk:string;

    res:string;

    mas:pointer;

    len:word;

 

procedure Pause;forward;

procedure MainMenu;forward;

procedure MenuInf;forward;

 

procedure Vihod;

 

var

  key: Char;

begin

     asm

        mov AH,0

        mov AL,3

        int 10h

     end;

     asm

        mov AH,2

        mov BH,0

        mov DL,28

        mov DH,10

        int 10h

     end;

     s:='Hotite viyty?';

     lng:=length (s);

     for i:= 1 to lng do

     begin

     buf:=s[i];

     asm

        mov AH,0eh

        mov AL,buf

        mov BH,0

        int 10h

     end;

     end;

     asm

        mov AH,0eh

        mov AL,10

        mov BH,0

        int 10h

        mov AH,0eh

        mov AL,13

        mov BH,0

        int 10h

     end;

     asm

        mov AH,2

        mov BH,0

        mov DL,28

        mov DH,12

        int 10h

     end;

     s:='Da - Enter';

     lng:=length (s);

     for i:= 1 to lng do

     begin

     buf:=s[i];

     asm

        mov AH,0eh

        mov AL,buf

        mov BH,0

        int 10h

     end;

     end;

     asm

        mov AH,2

        mov BH,0

        mov DL,48

        mov DH,12

        int 10h

     end;

     s:='Net - Esc';

     lng:=length (s);

     for i:= 1 to lng do

     begin

     buf:=s[i];

     asm

        mov AH,0eh

        mov AL,buf

        mov BH,0

        int 10h

     end;

     end;

     asm

        mov AH,2

        mov BH,0

        mov DL,28

        mov DH,10

        int 10h

     end;

  repeat

     asm

        mov AH,0

        int 16h

        mov key,AL

     end;

    if key = #13 then Halt(1);

  until key = #27;

  MainMenu;

     end;

 

procedure Information;

var

f:file of char;

p:char;

begin

     asm

        mov AH,0

        mov AL,3

        int 10h

     end;

   assign(f, NameTxt);

   reset(f);

   if IOResult<>0 then begin

    s:='Ошибка! Файл не найден!';

     lng:=length (s);

     for i:= 1 to lng do

     begin

     buf:=s[i];

     asm

        mov AH,0eh

        mov AL,buf

        mov BH,0

        int 10h

     end;

     end;

     asm

        mov AH,0eh

        mov AL,10

        mov BH,0

        int 10h

        mov AH,0eh

        mov AL,13

        mov BH,0

        int 10h

     end;

     end

     else

    begin

    while not eof(f) do

       begin

       read(f,p);

       write(p);

       end;

    close(f);

    end;

    asm

       mov AH,0

       int 16h

    end;

    MenuInf;

end;

 

procedure Pause;

begin

    asm

       mov AH,0

       int 16h

    end;

end;

 

procedure About;

begin