|
Îäèí èç ñàìûõ ïîïóëÿðíûõ ìåòîäîâ ñîðòèðîâêè – «ïóçûðüêîâûé» ìåòîä – îñíîâàí íà òîì, ÷òî â ïðîöåññå èñïîëíåíèÿ àëãîðèòìà áîëåå «ëåãêèå» ýëåìåíòû ìàññèâà ïîñòåïåííî «âñïëûâàþò». Îñîáåííîñòüþ äàííîãî ìåòîäà ÿâëÿåòñÿ ñðàâíåíèå íå êàæäîãî ýëåìåíòà ñî âñåìè, à ñðàâíåíèå â ïàðàõ ñîñåäíèõ ýëåìåíòîâ. Àëãîðèòì ïóçûðüêîâîé ñîðòèðîâêè ïî óáûâàíèþ ñîñòîèò â ïîñëåäîâàòåëüíîì ïðîñìîòðå ñíèçó ââåðõ (îò íà÷àëà ê êîíöó) ìàññèâà Ì. Åñëè äëÿ ñîñåäíèõ ýëåìåíòîâ âûïîëíÿåòñÿ óñëîâèå, ñîãëàñíî êîòîðîìó ýëåìåíò, íàõîäÿùèéñÿ ñïðàâà, áîëüøå ýëåìåíòà, íàõîäÿùåãîñÿ ñëåâà, òî âûïîëíÿåòñÿ îáìåí çíà÷åíèÿìè ýòèõ ýëåìåíòîâ.
Òåêñò ïðîãðàììû ñîðòèðîâêè ìàññèâà ïî íåâîçðàñòàíèþ ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì:
program Sort_Puz;
{Ñîðòèðîâêà ìàññèâà «ïóçûðüêîâûì» ìåòîäîì ïî íåâîçðàñòàíèþ} const
Count = 20;
M:array [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, K, L : Byte;
A : integer;
begin
Writeln('Èñõîäíûé ìàññèâ: ');
for I := 1 to Count do Write(M[I],' ');
Writeln;
A:=0;
for I := 2 to Count do
{Ñîðòèðîâêà «ïóçûðüêîâûì» ìåòîäîì ïî íåâîçðàñòàíèþ}
begin
for J:=Count downto I do
begin
A:=A+1;
if M[J-1]
{Åñëè ýëåìåíò ñïðàâà áîëüøå ýëåìåíòà ñëåâà, òî «âûòåñíèòü» åãî âëåâî - ïóçûðåê «âñïëûâàåò»}
begin
K:=M[J-1]; {Îáìåí çíà÷åíèÿìè ýòèõ ýëåìåíòîâ}
M[J-1]:=M[J];
M[J]:=K; {Ïå÷àòàòü òåêóùåå ñîñòîÿíèå ìàññèâà ïîñëå êàæäîé ïåðåñòàíîâêè}
for L := 1 to Count do Write(M[L]);
Writeln('×èñëî èòåðàöèé =',À);
end;
end;
end; {Çàâåðøåíèå ñîðòèðîâêè}
end.
Çàïóñòèòå èíòåãðèðîâàííóþ ñðåäó ïðîãðàììèðîâàíèÿ. Ââåäèòå òåêñò ïðîãðàììû Sort_Puz è çàïèøèòå ôàéë íà äèñê ïîä ñîîòâåòñòâóþùèì èìåíåì, à çàòåì îòêîìïèëèðóéòå åãî. Ïîñëå óñïåøíîãî çàâåðøåíèÿ êîìïèëÿöèè çàïóñòèòå ïðîãðàììó, îòñëåæèâàÿ â ïîøàãîâîì ðåæèìå òåêóùèå çíà÷åíèÿ ïåðåìåííûõ I, J, Ê, M[J], M[J–1], âñåãî ìàññèâà Ì, à ïî îêîí÷àíèè öèêëà J ïðîñìàòðèâàÿ èçìåíåíèÿ ìàññèâà â ðåçóëüòàòå îäíîãî ïðîõîäà. Êàê ìîæíî çàìåòèòü, ïðè ïîìîùè îïåðàòîðà for ñ ïàðàìåòðîì J âûïîëíÿåòñÿ öèêëè÷åñêèé ïðîñìîòð ýëåìåíòîâ ìàññèâà îò ïîñëåäíåãî äî âòîðîãî, è ïðè ýòîì ýëåìåíòû, áîëüøèå, ÷åì «ñîñåäè» ñëåâà, ñìåùàþòñÿ ïðè îáìåíå ê íà÷àëó ìàññèâà, à ìåíüøèå ñìåùàþòñÿ âïðàâî – «âñïëûâàþò» â êîíöå ìàññèâà. Êàæäûé ïðîõîä ôèêñèðóåòñÿ ñ÷åò÷èêîì – óâåëè÷åíèåì íà åäèíèöó çíà÷åíèÿ ïåðåìåííîé À. Ïîñëå êàæäîãî ïðîñìîòðà-ñðàâíåíèÿ ýëåìåíòîâ ìàññèâà ïðîñìàòðèâàåìûé ó÷àñòîê ìàññèâà óìåíüøàåòñÿ íà îäèí ýëåìåíò, òàê êàê èç ðàññìîòðåíèÿ èñêëþ÷àåòñÿ ñàìûé ëåâûé (ñàìûé áîëüøîé) ýëåìåíò. Òàêîå óìåíüøåíèå ïðîñìàòðèâàåìîãî ó÷àñòêà ðåàëèçóåòñÿ ïðè ïîìîùè âíåøíåãî öèêëà for ñ ïàðàìåòðîì I.
Ïî ïîñëåäíåìó çíà÷åíèþ À ìîæíî îïðåäåëèòü, ÷òî äëÿ äàííîãî ìàññèâà ñîðòèðîâêà ïî íåâîçðàñòàíèþ ïóçûðüêîâûì ìåòîäîì âûïîëíÿåòñÿ çà 170 èòåðàöèé.
|
