Podłubałem trochę w wolnym czasie i udało mi się zrobić program, który wykona sortowanie bez konieczności korzystania z dodatkowej macierzy:
program u2DMtxSort;
{$APPTYPE CONSOLE}
type
TSortMtx = array of array of Byte;
{ FILL MATRIX }
procedure FillMtx(var Mtx: TSortMtx; Range: Byte);
var
iCols, iCount, I: Word;
begin
if (Length(Mtx) = 0) or (Length(Mtx[0]) = 0) then Exit;
iCols := Length(Mtx[0]);
iCount := Length(Mtx) * iCols;
Randomize();
for I := 0 to iCount - 1 do
Mtx[I div iCols, I mod iCols] := Random(Range);
end;
{ BUBBLE SORT MATRIX }
procedure SortMtx(var Mtx: TSortMtx);
var
iCols, iCount, I, J: Word;
iTemp: Byte;
begin
if (Length(Mtx) = 0) or (Length(Mtx[0]) = 0) then Exit;
iCols := Length(Mtx[0]);
iCount := Length(Mtx) * iCols;
for I := 0 to iCount - 2 do
for J := 0 to iCount - 2 do
if Mtx[J div iCols, J mod iCols] > Mtx[(J + 1) div iCols, (J + 1) mod iCols] then
begin
iTemp := Mtx[J div iCols, J mod iCols];
Mtx[J div iCols, J mod iCols] := Mtx[(J + 1) div iCols, (J + 1) mod iCols];
Mtx[(J + 1) div iCols, (J + 1) mod iCols] := iTemp;
end;
end;
{ SHOW MATRIX }
procedure ShowMtx(Title: String; Mtx: TSortMtx);
var
iCols, iRows, I, J: Word;
begin
if (Length(Mtx) = 0) or (Length(Mtx[0]) = 0) then Exit;
WriteLn(Title, #10);
iRows := Length(Mtx);
iCols := Length(Mtx[0]);
for I := 0 to iRows - 1 do
begin
for J := 0 to iCols - 1 do
Write(Mtx[I, J], ' ');
WriteLn;
end;
WriteLn;
end;
var
aMtx: TSortMtx;
begin
{ SET MATRIX LENGTH }
SetLength(aMtx, 5, 5);
{ FILL MATRIX }
FillMtx(aMtx, 10);
{ SHOW MATRIX BEFORE SORT }
ShowMtx('Matrix content before sort:', aMtx);
{ SORT MATRIX }
SortMtx(aMtx);
{ SHOW MATRIX AFTER SORT}
ShowMtx('Matrix content after sort:' ,aMtx);
ReadLn;
end.
Sortowanie odbywa się na macierzach dynamicznych, ale z powodzeniem można także sortować statyczne; W tym algorytmie zastosowałem niezoptymalizowane sortowanie bąbelkowe - nie jest najszybsze, ale przedstawione tylko dla uwidocznienia sposobu odwoływania się do poszczególnych elementów macierzy;
Przykładowa zawartość ekranu konsoli po uruchomieniu:
Matrix content before sort:
0 9 9 6 8
2 1 6 7 2
1 3 8 4 1
6 3 6 2 5
2 6 8 6 7
Matrix content after sort:
0 1 1 1 2
2 2 2 3 3
4 5 6 6 6
6 6 6 7 7
8 8 8 9 9
Pewnie i można to wykonać bardziej profesjonalnie ale nie miałem zbyt wiele czasu, stąd nie testowałem szybkości algorytmu; W każdym razie działa bez zarzutów; Zaimplementowanie innej metody sortowania będzie analogiczne do powyższego; W tym przykładzie najważniejsza jest jedna rzecz - metoda odwoływania się do kolejnych elementów macierzy;
Co można przyspieszyć? Najprawdopodobniej część sprawdzającą wartości dwóch elementów macierzy i je zamieniającą:
if Mtx[J div iCols, J mod iCols] > Mtx[(J + 1) div iCols, (J + 1) mod iCols] then
begin
iTemp := Mtx[J div iCols, J mod iCols];
Mtx[J div iCols, J mod iCols] := Mtx[(J + 1) div iCols, (J + 1) mod iCols];
Mtx[(J + 1) div iCols, (J + 1) mod iCols] := iTemp;
end;
Zamiast ciągle wykonywać dzielenie całkowite i pobierać resztę z dzielenia moża przed warunkiem wpisać rezultaty dzielenia do czterech zmiennych; W takiej postaci jednak wyraźniej widać w jaki sposób odwołuje się do elementów macierzy;
Dodałem także w każdej procedurze zabezpieczenia przed odwołaniem się do nieistniejącego elementu w macierzy, a także kilka procedur elegancko ją obsługujących, a także wyświetlających jej zawartość;
Zapoznaj się z tym przykładem i przetestuj kod u siebie;