Сортировка строк двумерного массива паскаль

Всем привет, столкнулся с небольшой проблемой. нужно отсортировать двумерный массив в паскале по строкам, за основу беря последний элемент, например:
на входе
1 2 3 4 2
1 5 2 9 3
3 5 2 9 6

3 5 2 9 6
1 5 2 9 3
1 2 3 4 2

Как осуществить такую процедуру?

• Вопрос задан более трёх лет назад
• 2721 просмотр

Находите минимальную строку, начав поиск с первой. Обмениваете первую с минимальной.

Находите минимальную строку, начав поиск со второй. Обмениваете вторую с минимальной.

Пример 36. Задан двумерный массив X из 6 строк и 4 столбцов. Упорядочить массив X по возрастанию элементов дробной части столбца с номером N. Отсортированный массив X вывести на экран монитора.

За основу алгоритма возьмем алгоритм сортировки одномерного массива методом пузырька. Отличие этой задачи в том, что переставлять местами нужно не два соседних элемента одномерного массива, а две соседние строки двумерного массива. Перестановка двух строк реализована с помощью арифметического цикла, третьего уровня вложения, с параметром цикла К.
Структурограмма:

PROGRAM PR36;
VAR
X: ARRAY [1..6, 1..4] OF REAL;
N, К, I, J: INTEGER;
R: REAL;
BEGIN
WRITELN(‘Введите матрицу X’);
FOR I := 1 ТО 6
DO FORJ := 1 TO 4
DO READ(X[I, J]);
WRITELN(‘Укажите номер столбца N матрицы X’);
READLN(N);
FOR I:=2 TO 6
DO FOR J:=6 DOWNTO I
DO IF FRAC(X[J-1,N])>FRAC(X[J,N])
THEN FOR К := 1 TO 4 < Перестановка строк>
DO BEGIN
R := X[J-1, К];
Х[J-1, K] := X[J, К];
Х[J, K]:- R;
END;
< Вывод на экран отсортированного массива X >
WRITELN(‘Матрица X имеет вид:’);
FOR I := 1 ТО 6
DO BEGIN
FOR J := 1 ТО 4
DO WRITE(X[I, J]: 6: 3,’ ‘);
WRITELN
END
END.

Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.

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

Мы рассмотрим только три простейшие схемы сортировки.

Метод "пузырька"

По-видимому, самым простым методом сортировки является так называемый метод " пузырька ". Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:

В результате наибольший элемент оказывается в самом верху массива.

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

Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j -го прохода не проверяются элементы, стоящие на позициях выше j .

Теперь можно привести текст программы упорядочения массива M[1..N] :

begin for j :=1 to N -1 do for i :=1 to N – j do if M[ i ] > M[ i +1] then swap (M[ i ],M[ i +1]) end;

Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:

procedure swap (var x,y: . );
var t: . ;
begin
t := x;
x := y;
y := t
end;

Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.

Применение метода "пузырька" можно проследить здесь.

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

Второй метод называется метод вставок ., т.к. на j -ом этапе мы "вставляем" j -ый элемент M[j] в нужную позицию среди элементов M[1] , M[2] ,. . ., M[j-1] , которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Сказанное можно записать следующим образом:

Чтобы сделать процесс перемещения элемента M[j] , более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M[0] , чье значение будет заведомо меньше значения любого из "реальных"элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.

Если барьер не использовать, то перед вставкой M[j] , в позицию i-1 надо проверить, не будет ли i=1 . Если нет, тогда сравнить M[j] ( который в этот момент будет находиться в позиции i ) с элементом M[i-1].

Описанный алгоритм имеет следующий вид:

begin M[0] := -oo; for j :=2 to N do begin i := j ; while M[ i ] M[ i – 1] do begin swap (M[ i ],M[ i -1]); i := i -1 end end end;

Процедура swap нам уже встречалась.

Сортировка посредством выбора

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j -ом этапе выбирается элемент наименьший среди M[j] , M[j+1] ,. . ., M[N] (см. процедуру FindMin ) и меняется местами с элементом M[j] . В результате после j -го этапа все элементы M[j] , M[j+1] ,. . ., M[N] будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1
выбрать среди M[j] ,. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц

begin for j :=1 to N -1 do begin FindMin ( j , i ); swap (M[ j ],M[ i ]) end end;

В программе, как уже было сказано, используется процедура FindMin , вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex :

procedure FindMin (start index : integer; var lowindex : integer );
var lowelem: . ;
u: integer;
begin
lowindex := start index ;
lowelem := M[startindex];
for u:= start index +1 to N do
if M[u] lowelem then
begin
lowelem := M[u];
lowindex := u
end
end;

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