Сортировка матриц

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

 

 

 

 

 

 

         второй  проход                                                     третий проход

     по второму разряду                                            по первому разряду

 

 

 

 

 

 

 

                        Рисунок 4 – Поразрядная сортировка по возрастанию

 

 

 

 

 

 

 

 

 

2 Разработка программы  сортировки матрицы

2.1 Типы переменных и  файлов

В программе используются три типизированных файла, содержащие целочисленные значения.  Обращение к файлам производится посредством следующих файловых переменных: f, f_vib, f_vst, где f – исходный файл, f_vib и f_vst – файлы для хранения матриц, отсортированных методом простого выбора и методом простых вставок соответственно. С помощью константы N задается размерность матрицы. Одномерный целочисленный массив t, состоящий из N ячеек, служит для построчного считывания данных из файла. Переменные c_vib и c_vst предназначены для подсчета количества перестановок при сортировке методом простого выбора и простых вставок соответственно. Переменные i, j используются в качестве счетчиков; k, no, max нужны для перестановок. В целочисленные переменные str1, str2, sto1,sto2 заносятся номера строк и столбцов,  ограничивающих выводимые матрицы.

 

2.2 Разработка интерфейса  программы

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

2.3 Разработка программы,  реализующей сортировку матрицы

В программе используется шесть процедур:       Первая – Formir – создает и заполняет матрицу случайным образом.    Вторая- nesortmatrick- сохраняет сгенерированную матрицу в файл  «Несортированная матрица». В данной процедуре создаем в папке с программой файл « Несортированная матрица», затем с помощью циклов «for» и команды «write( vfile, ar[I,j] )» построчно сохраняем матрицу в файл; в данном случае I и j элементы матрицы.             Третья – sortinvstavka- процедура сортировки матрицы методом простых вставок. На каждом следующем шаге (к+1),берем ar[I,k+1] и вставляем в готовую часть массива. Поиск подходящего места определяем последовательным сравнением элемента с предыдущим( ar[I,k+1];=buf;  теперь сравниваем с предыдущим buf<ar[I,k]).  Переменная t используется для подсчета перестановок; inc(t) - увеличивает значение  переменной t на 1.                 Четвертая – sortinvibor- процедура сортировки простым выбором.  С помощью цикла for просматриваем матрицу и находим в ней минимальный элемент kmin и ставим его в начало, затем находим минимальный элемент массива со второго элемента k:=j+1;  и вставляем его на нужное место ar[I,kmin]>ar[I,k] then kmin:=k;  и запоминаем ar[I,k]:=c; меняем местами ar[I,j]:=ar[I,kmin]; а ar[I,kmin]:=c; Переменная t используется для подсчета перестановок; inc(t) - увеличивает значение  переменной t на 1.          Пятая – otsortvstavka- сохраняем отсортированную методом  вставок матрицу в файл. Для этого создаем в папке с программой файл «Отсортвставками». С помощью циклов for и команды write( Sfile,ar[I,j]) построчно записываем готовую матрицу в файл.          Шестая – otsortvibor - сохраняем отсортированную методом  выбора  матрицу в файл. Для этого создаем в папке с программой файл «Отсортвыбором». С помощью циклов for и команды write( Sfile,ar[I,j]) построчно записываем готовую матрицу в файл.              Далее с помощью цикла while и команды write просим пользователя выбрать метод сортировки, после ввода цифры считываем ее и при помощи оператора case переходим к нужным частям программы:     Если пользователь ввел 1 то запускаем процедуры формирования матрицы, процедуру записи не отсортированной матрицы в файл, затем процедуру сортировки методом простых вставок и процедуру сохранения отсортированной матрицы в файл( formir(n), nesortmatrick(n), sortinvsavka(n), otsortvstavka(n)).             Если пользователь ввел 2 то запускаем процедуры формирования матрицы, процедуру записи не отсортированной матрицы в файл, затем процедуру сортировки методом простого выбора и процедуру сохранения отсортированной матрицы в файл( formir(n), nesortmatrick(n), sortinvibor(n), otsortvibor(n)).   Если пользователь ввел 3 то предлагаем ему просмотреть  любую строку матрицы по его усмотрению. Для этого просим с помощью write ввести номер строки и номера столбцов, ограничивающих эту строку. После чего с помощью цикла for выводим нужную строку на экран (write(ar[I,j]).     Если пользователь ввел 4 то цикл while завершается и программа закрывается.                                 

 2.4 Сравнительный анализ  разработанных алгоритмов сортировок

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

 

 

 

 

 

 

 

Заключение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованных источников

1 Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0

2 Классификация алгоритмов сортировки. – Режим доступа: http://saod.narod.ru/ saod3/List005.html

3 Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4

4 Оценка алгоритмов сортировки. - Режим доступа: http://cpp.com.ru/ shildt_spr_po_c/21/2103.html

5 Оценка алгоритмов сортировки. – Режим доступа: 

http://www.cyberguru.ru/ programming/pascal/turbopascal-encyclopaedia-page4. html

6 Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 198-219.—ISBN 5-8459-0857-4

7 Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234. — ISBN 5-8459-0857-4

8 Поразрядная сортировка. – Режим  доступа: http://codelab.ru/task/radix_sort-basic/

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение А

(обязательное)

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение Б

(обязательное)

 

Схема алгоритма работы разработанных методов сортировок

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

На рисунках Б.1 и Б.2 представлена схема алгоритма работы сортировки методом простого выбора.

 

 

 

 

 

Рисунок Б.1 – Схема алгоритма работы сортировки строки матрицы

 

 

Рисунок Б.2 – Схема алгоритма работы сортировки всей матрицы построчно

На рисунках Б.3 и Б.4 представлена схема алгоритма работы сортировки методом простых вставок.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок Б.3 - Схема алгоритма  работы сортировки строки матрицы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок Б.2 – Схема алгоритма  работы сортировки всей матрицы построчно

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение В

(обязательное)

 

Структурная схема  работы программы

 

На рисунке В.1 представлена структурная схема работы программы

 

                                                  Файлы                              Переменные

 

 

Процедуры

 

 

    

                                                                                             Подсчет количества перестановок

                                                                                         Подсчет количества перестановок

 

Вывод на экран

 

 

 

 

Рисунок В.1 – Структурная  схема работы программы

Приложение Г

(обязательное)

 

Контрольный пример работы с программой

 

На рисунках Г.1, Г.2, Г.3 приведен пример работы с программой.

 

 

 

 

 

 

 

 

 

 

 

        Рисунок Г.1 – Пример работы с программой

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок Г.2 – Пример работы с программой

 

 

 

 

 

 

 

 

 

 

 

Рисунок Г.3 – Пример работы с программой