There is a program in Pascal, which is engaged in sorting Shell and inserts. The sorting procedures are wonderful and seem to work adequately (if I'm not mistaken), but only with one-dimensional arrays (in this case, the type is LittleDataArray ). You need to adapt them to work with two-dimensional arrays (in this case, the type of LittleDataArray ).

Here are the algorithms:

 ... DataItem = char; LittleDataArray = array [1..80] of char; DataArray = array [1..80,1..80] of char; ... procedure Shell(var item: LittleDataArray); var i, j, k: integer; h: DataItem; begin amnt_s:=0; k := t shr 1; while k > 0 do begin for i := 0 to t - k do begin j := i; while (j >= 0) and (item[j] > item[j + k]) do begin h := item[j]; item[j] := item[j + k]; inc(amnt_s); item[j + k] := h; inc(amnt_s); if j > k then Dec(j, k) else j := 0; end; end; k := k shr 1; end; 
 
  end; 
  procedure Inser (var item: LittleDataArray);  var i, l, j: integer;  x: DataItem;  begin amnt_i: = 0;  for i: = 2 to t do begin x: = item [i];  inc (amnt_i);  j: = i-1;  while (x0) do begin item [j + 1]: = item [j];  inc (amnt_i);  j: = j-1;  end;  item [j + 1]: = x;  inc (amnt_i);  end;  end;  {end Inser sort}

  • Guys, what does the "Make common" function do for this portal? - uzumaxy
  • This means that the question turns into a kind of wiki entry, i.e. everyone (well, who has enough karma) can add something of his own if desired. - VioLet

2 answers 2

And what is the algorithm for sorting a two-dimensional array? At least tell me in what order the elements should be when the array is sorted.

  • Sort Ascending. The sort parameter is the position of the character in the ASCII table. - uzumaxy

Already all. I decided myself. From a two-dimensional array made a large one-dimensional, sorted it and transformed it back. MB such a method is not rational from the point of view of optimization, but it does not matter for the set TZ.

 ... DataItem = char; DataArray = array [1..maxLenght,1..maxLenght] of DataItem; BigDataArray = array [1..maxLengthDbl] of DataItem; ... procedure Shell(var toSort: DataArray); var k,itemLenght,p: integer; h: DataItem; item: BigDataArray; begin amnt_s:=0; p:=1; for t2:=1 to t do for t3:=1 to t do begin item[p]:=toSort[t2,t3]; p:=p+1; end; itemLenght:=t*t; k := itemLenght shr 1; while k > 0 do begin for t2 := 0 to itemLenght - k do begin t3 := t2; while (t3 >= 0) and (item[t3] > item[t3 + k]) do begin h := item[t3]; item[t3] := item[t3 + k]; item[t3 + k] := h; inc(amnt_s); if t3 > k then Dec(t3, k) else t3 := 0; end; end; k := k shr 1; end; 
 

 p:=1; for t2:=1 to t do for t3:=1 to t do begin toSort[t2,t3]:=item[p]; p:=p+1; end; 
end;
procedure Inser (var toSort: DataArray);
var
l, itemLenght, p: integer;
x: DataItem;
item: BigDataArray;
begin
amnt_i: = 0;
p: = 1;
for t2: = 1 to t do
for t3: = 1 to t do
begin
item [p]: = toSort [t2, t3];
p: = p + 1;
end;
 itemLenght:=t*t; for t2 := 2 to itemLenght do begin x := item[t2]; t3 := t2-1; while (x<item[t3]) and (t3>0) do begin item[t3+1] := item[t3]; inc(amnt_i); t3 := t3-1; end; item[t3+1] := x; end; p:=1; for t2:=1 to t do for t3:=1 to t do begin toSort[t2,t3]:=item[p]; p:=p+1; end; 
end;

  • In C, the program would be significantly shorter :-). two-dimensional arrays in RAM does not exist. All the same, it is implemented as a one-dimensional array. In this case, the indices change as follows: <pre> char a [MAX_X] [MAX_Y]; char b = a; // refer to the element a [i] [j]; b [i MAX_Y + j] = 0; </ pre> In Pascal, there is also work with pointers, but nothing good will come of it. - gecube