|
Èäåÿ ëèíåéíîé ñîðòèðîâêè ïî íåâîçðàñòàíèþ çàêëþ÷àåòñÿ â òîì, ÷òîáû ïîñëåäîâàòåëüíî ïðîñìàòðèâàÿ âåñü ìàññèâ, îòûñêàòü íàèáîëüøåå ÷èñëî è ïîìåñòèòü åãî íà ïåðâóþ ïîçèöèþ, îáìåíÿâ åãî ñ ýëåìåíòîì, êîòîðûé ðàíåå çàíèìàë ïåðâóþ ïîçèöèþ. Çàòåì ïðîñìàòðèâàþòñÿ âñå îñòàëüíûå ýëåìåíòû ìàññèâà è âûïîëíÿåòñÿ àíàëîãè÷íàÿ îïåðàöèÿ ïî îòáîðó èç ðàññìàòðèâàåìîé ÷àñòè ìàññèâà ìàêñèìàëüíîãî ýëåìåíòà è îáìåíó ìåñòàìè ýòîãî ýëåìåíòà è ïåðâîãî â ðàññìàòðèâàåìîé ÷àñòè, è ò. ä.
Ââåäåì â ðàçäåëå îïèñàíèÿ ñëåäóþùèå öåëûå ïåðåìåííûå:
I – äëÿ óêàçàíèÿ ïîçèöèè ïåðâîãî ýëåìåíòà â ðàññìàòðèâàåìîé ÷àñòè ìàññèâà;
J – äëÿ óêàçàíèÿ ïîçèöèè î÷åðåäíîãî ñðàâíèâàåìîãî ñ íèì ýëåìåíòà;
N – äëÿ âðåìåííîãî õðàíåíèÿ çíà÷åíèÿ ïåðâîãî ýëåìåíòà äëÿ îáìåíà çíà÷åíèÿìè ñ ìàêñèìàëüíûì èç ðàññìàòðèâàåìîé ÷àñòè ìàññèâà;
L – ïàðàìåòð öèêëà ïðè âûâîäå òåêóùåãî çíà÷åíèÿ ýëåìåíòîâ ìàññèâà â ïðîöåññå ñîðòèðîâêè äëÿ îòñëåæèâàíèÿ ïðîèñõîäÿùèõ â ìàññèâå èçìåíåíèé;
À – ïåðåìåííàÿ, çíà÷åíèå êîòîðîé áóäåò ðàâíî ÷èñëó ïåðåñòàíîâîê ýëåìåíòîâ.
Âûâîä èñõîäíîãî ìàññèâà íà ýêðàí çàïèøåì ñëåäóþùèì îáðàçîì:
Writeln('Èñõîäíûé ìàññèâ: ');
for I := 1 to Count do
Write( ', M[I]);
Writeln;
Ïåðåä íà÷àëîì ñîðòèðîâêè óñòàíîâèì çíà÷åíèå ñ÷åò÷èêà èòåðàöèé À ðàâíûì 0. Äëÿ ñîðòèðîâêè îðãàíèçóåì äâà öèêëà for: âíåøíèé öèêë ñ ïàðàìåòðîì I, óêàçûâàþùèì ïîçèöèþ ïåðâîãî ýëåìåíòà â íåîòñîðòèðîâàííîé ÷àñòè ìàññèâà, è âíóòðåííèé öèêë ñ ïàðàìåòðîì J, óêàçûâàþùèì ïîçèöèþ î÷åðåäíîãî, ñðàâíèâàåìîãî ñ ïåðâûì, ýëåìåíòà íåîòñîðòèðîâàííîé ÷àñòè ìàññèâà. Ñðàâíåíèå ýëåìåíòîâ çàïèøåì ïðè ïîìîùè îïåðàòîðà:
if M[I] < M[J] then begin
N := M[I];
M[I] := M[J];
M[J] := N;
end;
Åñëè óñëîâèå M[I] < M[J] âûïîëíÿåòñÿ, ò. å. â íåîòñîðòèðîâàííîé ÷àñòè ìàññèâà íàéäåí ýëåìåíò, áîëüøèé ïåðâîãî, òî ñëåäóåò ïîìåíÿòü ìåñòàìè ýòè ýëåìåíòû. Ïåðåñòàíîâêà îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì: ñíà÷àëà çíà÷åíèå Ì[1] çàïîìèíàåòñÿ â ïåðåìåííîé N, çàòåì çíà÷åíèå ýëåìåíòà ìàññèâà èç J-é ïîçèöèè çàïèñûâàåòñÿ â 1-þ ïîçèöèþ, à ïîñëå ýòîãî â J-þ ïîçèöèþ ìàññèâà çàïèñûâàåòñÿ çíà÷åíèå ïåðåìåííîé N. Äëÿ îòñëåæèâàíèÿ èçìåíåíèé ñîñòîÿíèÿ ìàññèâà ïîñëå êàæäîé ïåðåñòàíîâêè çàäàäèì öèêë âûâîäà çíà÷åíèé âñåõ ýëåìåíòîâ ìàññèâà è íàïå÷àòàåì òåêóùåå çíà÷åíèå ÷èñëà ïåðåñòàíîâîê ýëåìåíòîâ À:
for L := 1 to Count do
Write(', M[L]);
Writeln( '×èñëî èòåðàöèé=', À);
Ïîëíûé òåêñò ïðîãðàììû ëèíåéíîé ñîðòèðîâêè ìàññèâà Ì ïî íåâîçðàñòàíèþ ìîæåò áûòü çàïèñàí ñëåäóþùèì îáðàçîì:
program Sort_Lin; {Ëèíåéíàÿ ñîðòèðîâêà ïî íåâîçðàñòàíèþ} const
Count = 20;
Ì:àããàó [1..Count] of byte=(9.11,12,3.19,1.5,17,10.18.3,19,17.9. 12.20,20,19,2,5);
var
I, J, N. L : Byte;
A : integer;
begin
Writeln('Èñõîäíûé ìàññèâ: ');
for I := 1 to Count do Write( ', M[I]);
Writeln;
A:=0;
for I := 1 to Count - 1 do {Èçìåíÿòü ðàçìåð íåîòñîðòèðîâàííîé ÷àñòè ìàññèâà}
for J:=I+1 to Count do {Ñðàâíèâàåì ïîî÷åðåäíî 1-é ýëåìåíò íåîòñîðòèðîâàííîé ÷àñòè ìàññèâà ñî âñåìè îò I+1-ãî äî êîíöà}
begin
À:=À+1;
if M[I] < M[J] then {Åñëè â íåîòñîðòèðîâàííîé ÷àñòè ìàññèâà íàøëè ýëåìåíò. áîëüøèé, ÷åì 1-é, òî îáìåíÿòü èõ ìåñòàìè}
begin
N := Ì[1]; {Çàïîìíèòü íà âðåìÿ çíà÷åíèå Ì[1]}
M[I] := M[J];
M[J] := N;
end;
for L := 1 to Count do
Write(M[L]);
Writeln('×èñëî èòåðàöèé -',À);
end;
end.
Çàïóñòèòå èíòåãðèðîâàííóþ ñðåäó ïðîãðàììèðîâàíèÿ. Ââåäèòå òåêñò ïðîãðàììû Sort_Lin è çàïèøèòå ôàéë íà äèñê ïîä ñîîòâåòñòâóþùèì èìåíåì, à çàòåì îòêîìïèëèðóéòå åãî. Ïîñëå óñïåøíîãî çàâåðøåíèÿ êîìïèëÿöèè çàïóñòèòå ïðîãðàììó, îòñëåæèâàÿ â ïîøàãîâîì ðåæèìå òåêóùèå çíà÷åíèÿ ïåðåìåííûõ: I, J, N, M[I], M[J], à òàêæå ïðîñìàòðèâàÿ íà ýêðàíå ïîëüçîâàòåëÿ ðåçóëüòàò èçìåíåíèÿ ìàññèâà çà îäèí ïðîõîä âíóòðåííåãî öèêëà. Ïî ïîñëåäíåìó çíà÷åíèþ À ìîæíî îïðåäåëèòü, ÷òî äëÿ äàííîãî ìàññèâà ëèíåéíàÿ ñîðòèðîâêà ïî íåâîçðàñòàíèþ âûïîëíÿåòñÿ çà 190 èòåðàöèé.
| 
