Sortowanie kolumnowo tablic dwuwymiarowych

Witam,
mam taką procedurę

l:=M*N;         
  for k:=1 to l do
    begin
      for i := 1 to M do
        for j := 1 to N-1 do
          begin
           if tab[i,j] > tab[i,j+1] then
             begin
               x := tab[i, j+1];
               tab[i, j+1] := tab[i, j];
               tab[i, j] := x;
             end;
           if (j=N-1) and (i<>M) then
             if tab[i,j+1] > tab[i+1,1] then
               begin
                 x := tab[i+1, 1];
                 tab[i+1, 1] := tab[i,j+1];
                 tab[i, j+1] := x;
               end;
          end;

która sortuje tablice miej więcej tak

przed:

9 6 1
3 8 2
4 7 5

po:

1 2 3
4 5 6
7 8 9

jak zmodyfikować procedure by posortowana tablica wyglądała tak:

1 4 7
2 5 8
3 6 9

zamienić i z j

Potraktować tablicę dwuwymiarową jako jednowymiarową i sortować

@Krwawy Karp - nie, i wynika to z kilku zależności.

O ile faktycznie dwuwymiarowe macierze przechowywane są w pamięci w postaci jednego, ciągłego bloku, to taka sytuacja nie musi występować w przypadku macierzy dynamicznych, które de facto macierzami dwuwymiarowymi nie są. Bo ta macierz jest dwuwymiarowa:

type T2DArray = array [0 .. N - 1, 0 .. M - 1] of UInt8;

a ta już nie jest:

type
  TNotExactly2DArray = array of array of UInt8;

Fakt zapewnienia rzekomego drugiego wymiaru nie czyni jej stricte dwuwymiarową. Druga sprawa to fakt, iż taka macierz (ta druga) nie musi być prostokątną - każda jej kolumna może posiadać inną liczbę komórek i wyglądać jak wykres słupkowy.

A trzecia sprawa to to, że nawet jeśli traktować tę macierz jako jednowymiarową, to nie do sortowania jakie interesuje pytacza, a do zastąpienia kodu jaki posiada. Czyli potraktowanie macierzy dwuwymiarowej jak jednowymiarowej da dokładnie to samo co pytacz ma teraz - liczby posortowane według wierszy, a nie według kolumn.

Kod posiadany przez pytacza można zamienić na krótszy, właśnie traktując wejściową macierz jako jednowymiarową - pod warunkiem, że faktycznie używa macierzy dwuwymiarowej. Do tego celu nie potrzeba żadnych skomplikowanych zabiegów, nie trzeba rzutowania czy pointerów - wystarczy zadeklarować sobie drugi typ danych jako macierz jednowymiarowa, zgodny rozmiarem z typem macierzy dwuwymiarowej, a samo "traktowanie" macierzy zaimplementować za pomocą dodatkowej zmiennej lokalnej i magicznego słowka absolute.

Przykład:

const
  N = 3;
  M = 3;

type
  T1DNumbers = array [0 .. N * M - 1] of UInt8;
  T2DNumbers = array [0 .. N - 1, 0 .. M - 1] of UInt8;

  procedure SortNumbers(var ANumbers: T2DNumbers);
  var
    LNumbers: T1DNumbers absolute ANumbers;  // magic
  var
    LSize, LNumIdx: Integer;
    LSwap: UInt8;
  begin
    for LSize := Low(LNumbers) to High(LNumbers) do
      for LNumIdx := Low(LNumbers) to High(LNumbers) - 1 do
        if LNumbers[LNumIdx] > LNumbers[LNumIdx + 1] then
        begin
          LSwap := LNumbers[LNumIdx];
          LNumbers[LNumIdx] := LNumbers[LNumIdx + 1];
          LNumbers[LNumIdx + 1] := LSwap;
        end;
  end;

Zmienna LNumbers zadeklarowana zostaje pod adresem macierzy z parametru, dzięki czemu po pierwsze operujemy pośrednio na macierzy wejściowej, a po drugie, unikamy zabawy w rzutowanie, translację indeksów inne zabiegi. Ten sposób można wykorzystać również do wypełniania macierzy czy wyświetlania jej zawartości na ekranie (w postaci jednego ciągu liczb). Cały kod aplikacji testowej znajduje się tutaj, a efekt jej wywołania poniżej:

 6 9 5 5 3 3 6 4 1

 6 9 5
 5 3 3
 6 4 1

 1 3 3 4 5 5 6 6 9

 1 3 3
 4 5 5
 6 6 9

Pierwsze dwa bloki liczb to stan początkowy, pokazany w postaci jedno- i dwuwymiarowej, a kolejne dwa to stan po posortowaniu według wierszy. Jak widać, to pytacz już ma, choć kodu sortującego jest o wiele mniej.

Odpowiadając pytaczowi - aby posortować kolumnowo macierz dwuwymiarową, należy albo pozmieniać indeksy (o czym napisał już poprzednik), albo zmienić koncepcję. Przekopiować zawartość macierzy wejściowej do pomocniczej (jednowymiarowej), posortować, a na koniec przepisać zawartość z lokalnej (posortowanej) kopii z powrotem, tyle że zmieniając indeksy komórek.

Przykład niżej (korzysta z podanej wcześniej procedury SortNumbers):

procedure SortNumbersCol(var ANumbers: T2DNumbers);
var
  LNumbers: T2DNumbers;
  LCol, LRow: Integer;
begin
  LNumbers := ANumbers;
  SortNumbers(LNumbers);

  for LCol := Low(LNumbers) to High(LNumbers) do
    for LRow := Low(LNumbers[LCol]) to High(LNumbers[LCol]) do
      ANumbers[LCol, LRow] := LNumbers[LRow, LCol];
end;

Na ekranie ujrzymy to:

 7 6 8 6 5 9 1 0 5

 7 6 8
 6 5 9
 1 0 5

 0 1 5 5 6 6 7 8 9

 0 1 5
 5 6 6
 7 8 9

 0 5 7 1 6 8 5 6 9

 0 5 7
 1 6 8
 5 6 9

Pierwsze dwa bloki to stan początkowy, drugie dwa bloki to stan po posortowaniu według wierszy, a ostatnie dwa bloki to stan końcowy, po posortowaniu według kolumn. Tego oczekuje pytacz, więc... to ode mnie dostaje w prezencie.

Zmodyfikowana wersja kodu znajduje się tutaj. Wszystkie wyżej wymienione kody napisane zostały we Free Pascalu.