Отсортировать строки двумерного массива вещественных чисел методом быстрой сортировки - Turbo Pascal
Формулировка задачи:
отсортировать строки двумерного массива вещественных чисел
по значению элемента первого столбца
методом быстрой сортировки.
Решение задачи: «Отсортировать строки двумерного массива вещественных чисел методом быстрой сортировки»
textual
Листинг программы
uses crt; const nmax=20; type mas=array [1..nmax] of real; mtr=array[1..nmax] of mas; var x:mtr; s,p:integer; procedure sort(l,r:integer); var i,j,m: integer; x1:real; y1:mas; begin i:=l; j:=r; m:=round ((l+r)/2); x1:=x[m,1]; repeat while x[i,1]<x1 do begin inc(i); inc(s); {сравниваем} end; while x[j,1]>x1 do begin dec(j); inc(s);{сравниваем} end; if i<=j then begin y1:=x[i]; x[i]:=x[j]; x[j]:=y1; inc(i); dec(j); inc(p);{переставляем} end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; var n,m,i,j:integer; begin clrscr; randomize; repeat write('Количество строк до ',nmax,' n='); readln(n); until n in [1..nmax]; repeat write('Количество столбцов до ',nmax,' m='); readln(m); until m in [1..nmax]; writeln('Исходная матрица:'); for i:=1 to n do begin for j:=1 to m do begin x[i,j]:=10*random; write(x[i,j]:5:2); end; writeln; end; writeln; sort(1,n); writeln('Матрица после сортировки: '); for i:=1 to n do begin for j:=1 to m do write(x[i,j]:5:2); writeln; end; write('Количество сравнений=',s,' перестановок=',p); readln end.
Объяснение кода листинга программы
- В начале кода подключается библиотека crt, которая содержит функции для работы с числами с плавающей точкой.
- Затем определяются две константы: nmax, которая ограничивает количество строк в двумерном массиве, и mtr, которая представляет собой тип данных для хранения строк.
- Далее объявляются переменные x, s и p. Переменная x представляет собой двумерный массив, который будет использоваться для хранения отсортированных строк. Переменные s и p используются для отслеживания индексов среднего элемента в процессе сортировки.
- Затем определяется процедура sort, которая принимает два аргумента: l и r. Эти аргументы представляют собой индексы левого и правого концов диапазона, который нужно отсортировать.
- Внутри процедуры sort объявляются три переменные: i, j и m. Они будут использоваться для отслеживания среднего элемента в процессе сортировки.
- Затем происходит итерация по диапазон от l до r. На каждой итерации сравниваются два соседних элемента и выполняются соответствующие действия.
- Если текущий элемент меньше следующего, то он помещается в переменную y1, а текущий элемент заменяется на y1. Затем текущий элемент и y1
перемещаются
вправо, пока текущий элемент больше y1. - После завершения итераций по диапазону от l до r, выполняется рекурсивная вызов sort для левой и правой половин диапазона.
- В конце кода считывается количество строк и столбцов, которые будут использоваться в матрице.
- Затем создается матрица, заполненная случайными значениями.
- После этого вызывается функция sort для сортировки матрицы.
- Наконец, выводится отсортированная матрица и количество сравнений и перестановок, которые были выполнены в процессе сортировки.