Witam!
Mam takie pytanie: jak posortować tablicę dwuwymiarową wg takiego schematu?
1 5 3 4
8 1 9 4
7 8 9 2
</code`code>na`
1 1 2 3
4 4 5 7
8 8 9 9
Na forum znalazłem jedynie coś takiego, co by pasowało do mojego pytania, ale nie działa w każdym wypadku...
http://4programmers.net/Forum/Delphi_Pascal/110073-Sortowanie_tablicy_dwuwymiarowej?p=381631#id381631
No właśnie myślałem o czymś takim, tylko właśnie nie potrafiłem z tablicy dwuwymiarowej zrobić jednowymiarową.
int ktoryElement=0;
int tablica[wiersze*kolumny wejsciowejj tablicy]
for (int i=0; i<wierszeWejsciowetablicy; i++) {
for (int j=0; j<kolumnyWejsciowejtablicy; j++) {
tablica[ktoryElement] = WejsciowaTablica[i][j];
ktoryElement++;
}
}
Zaznaczyłem w tagu, że chodzi mi o delphi, a nie c++
Spróbuje to przerobić, najwyżej jeszcze się dopytam :)
Niestety nie znam się na składni języka C, więc nie wiem co zrobić z tym :(
var
tab2: array[0..ww-1,0..kk-1] of Integer;
tab1: array[0..ww*kk-1] of Integer;
//...
for w:=0 to ww-1 do for k:=0 to kk-1 do tab1[w*kk+k]:=tab2[w,k];
Można by wszystko napisać bez wykorzystania dodatkowej macierzy jednowymiarowej; Sposób prosty - wystarczy skorzystać z operatorów div i mod, i sortowanie będzie mogło zostać wykonane na macierzy docelowej;
Będzie to raczej szybsze rozwiązanie od przepisywania, ale ww. operatory są dość wolne, stąd przy małych macierzach zyska się niewiele, za to przy coraz to większych różnica czasów sortowania będzie coraz większa;
Pomyśl nad tym, ja opracuję to jutro (ahh, tak dla celów edukacujnych);
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;
@Furious Programming, prosiłeś - masz. W zadaniu nie podano że wewnątrz ma być tablica dwuwymiarowa, grunt że na ekranie jest dwuwymiarowa.
type TIntegerArray=array of Integer;
procedure qsort(var T:TIntegerArray);
procedure sort(Lo,Hi:Integer);
var mLo,mHi,mid,tmp:Integer;
begin
mLo:=Lo;
mHi:=Hi;
mid:=T[(Lo+Hi)shr(1)];
repeat
while T[mLo]<mid do Inc(mLo);
while mid<T[mHi] do Dec(mHi);
if mLo<=mHi then
begin
tmp:=T[mLo]; T[mLo]:=T[mHi]; T[mHi]:=tmp;
Inc(mLo);
Dec(mHi);
end;
until mLo>mHi;
if Lo<mHi then sort(Lo,mHi);
if mLo<Hi then sort(mLo,Hi);
end;
begin
sort(0,High(T));
end;
procedure Show(const T:TIntegerArray;Rows,Cols:Word);
var Y,X,I:Integer;
begin
I:=0;
for Y:=0 to Rows-1 do
begin
for X:=0 to Cols-1 do
begin
Write(T[I]:3);
Inc(I);
end;
WriteLn;
end;
end;
procedure go;
var Rows,Cols:Word;
var I,Size:Integer;
var Tb:TIntegerArray;
begin
Rows:=0; Cols:=0; // Kompilator się upomina, ale nie trzeba tego
Randomize;
while true do
begin
while true do
begin
Write('Podaj wymiar Y: ');
{$I-} ReadLn(Rows); {$I+}
if IOResult=0 then Break;
WriteLn('Podaj w postaci liczbowej');
end;
while true do
begin
Write('Podaj wymiar X: ');
{$I-} ReadLn(Cols); {$I+}
if IOResult=0 then Break;
WriteLn('Podaj w postaci liczbowej');
end;
if (Rows=0)or(Cols=0) then Break;
Size:=Rows*Cols;
SetLength(Tb,Size);
for I:=0 to Size-1 do Tb[I]:=1+random(98);
WriteLn('Przed');
Show(Tb,Rows,Cols);
qsort(Tb);
WriteLn('Po');
Show(Tb,Rows,Cols);
WriteLn;
end;
end;
begin
go;
end.
_13th_Dragon napisał(a)
W zadaniu nie podano że wewnątrz ma być tablica dwuwymiarowa, grunt że na ekranie jest dwuwymiarowa.
Ylv napisał(a)
Na forum znalazłem jedynie coś takiego, co by pasowało do mojego pytania, ale nie działa w każdym wypadku...
Niestety się nie zgodzę, autor podał link do tematu (http://4programmers.net/Forum/Delphi_Pascal/110073-Sortowanie_tablicy_dwuwymiarowej?p=381631#id381631), w którym jasno napisane jest, że macierz ma być dwuwymiaowa; W licznych przykładach posługuje się właście taką tablicą, stąd musi być dwuwymiarowa; Autor zapewne podał przykład sposobu posortowania (tutaj: według wierszy), a nie jak to ma wyglądać na ekranie;
Mniejsza z tym, bardzo dobrym pomysłem było kopiowanie zawartości macierzy dwuwymiarowej do jednowymiarowej - można oszczędzić mnóstwo czasu na div i mod - sprawdziłem;
Twój przykład oczywiście działa, ale nie mam go jak porównać ze swoim, ponieważ użyłeś innego algorytmu sortującego; Potwierdziły się jednak moje przypuszczenia, że obliczając raz J div iCols, J mod iCols, (J + 1) div iCols oraz (J + 1) mod iCols i pakując wyniki do zmiennych można zaoszczędzić średnio od 5 - 15%, ale tylko przy macierzach o równej liczbie kolumn i wierszy - dla innych czas się znacznie wydłuża; Przetestowałem wszystkie rozwiązania (łącznie z tym @pelsta) i kopiowanie do jednowymiarowej macierzy jest wielokrotnie szybsze od sortowania macierzy źródłowej / docelowej;
Kod, którym testowałem znajduje się pod tym linkiem: http://4programmers.net/Pastebin/1777
Każdy z trzech algorytmów (mój z ciągłym dzieleniem, mój z pakowaniem wyników dzielenia do zmiennych oraz @pelsta z kopiowaniem tablicy do tymczasowej jednowymiarowej) sortuje macierz wykorzystując niezoptymalizowane sortowanie bąbelkowe; Każdy z nich sortuje tablicę raz na rozgrzewkę, następnie mierzony jest czas dla 10 sortowań z rzędu tej samej macierzy (przekazaną do procedury przez wartość), po czym pętla wraca, rozmiar macierzy jest powiększany i znów wykonuje się sortowanie; Tak więc każdy z algorytmów sortuje macierz 10 razy dla 10 rozmiarów + 1 raz na rozgrzewkę, czyli 110 razy; Przykładowe wyjście po wykonaniu programu:
Non optimized bubble sort of square matrix:
Sort Pelsta [10x10]: 0
Sort FP [10x10]: 2
Sort FP Opt [10x10]: 1
----------------------------
Sort Pelsta [20x20]: 2
Sort FP [20x20]: 25
Sort FP Opt [20x20]: 23
----------------------------
Sort Pelsta [30x30]: 5
Sort FP [30x30]: 126
Sort FP Opt [30x30]: 115
----------------------------
Sort Pelsta [40x40]: 17
Sort FP [40x40]: 384
Sort FP Opt [40x40]: 352
----------------------------
Sort Pelsta [50x50]: 41
Sort FP [50x50]: 952
Sort FP Opt [50x50]: 918
----------------------------
Sort Pelsta [60x60]: 87
Sort FP [60x60]: 1981
Sort FP Opt [60x60]: 1888
----------------------------
Sort Pelsta [70x70]: 177
Sort FP [70x70]: 3947
Sort FP Opt [70x70]: 3512
----------------------------
Sort Pelsta [80x80]: 296
Sort FP [80x80]: 6546
Sort FP Opt [80x80]: 5904
----------------------------
Sort Pelsta [90x90]: 426
Sort FP [90x90]: 10083
Sort FP Opt [90x90]: 9274
----------------------------
Sort Pelsta [100x100]: 649
Sort FP [100x100]: 15412
Sort FP Opt [100x100]: 13809
----------------------------
Put ENTER key to exit...
Wyniki mówią same za siebie; Po raz kolejny udowodniłem sobie, że operatory mod i div są cholernie wolne i trzeba je omijać z daleka;
Wiadome, wybrałem najwolniejszy algorytm sortujący, jednak zrobiłem to celowo; Jest wiele szybszych, więc jest się nad czym zastanowić; Ty @_13th_Dragon wykorzystałeś QuickSort, który jest znacznie szybszy od wykorzystanego przeze mnie, ale nie o to mi chodziło; Miałem na myśli to, żebyś przedstawił najszybsze rozwiązanie posortowania macierzy dwuwymiarowej niezoptymalizowanym algorytmem sortowania bąbelkowego, a nie najszybsze jakie istnieje (i to jeszcze wykonane na macierzy jednowymiarowej);