Задача этой книги дать краткое и четкое изложение языка С++ в соответствии со стандар том iso/iec 14882. Она предназначена для студентов, изучающих язык «с нуля»

partial_sOrt(a,a+ 5,a+ m, greater()); fOr (i= 0;i< m; i++) COut << a[i] << " ";
COut << endl; // 34 20873122
return 0;
}

partition, stable_partition

Àëãîðèòì partitiOn ðaçìåùaåò ýëåìåíòû, óäîâëåòâîðяþùèå çaäaííîìó óñëîâèþ, ïåðåä îñòaëüíûìè ýëåìåíòaìè. Àëãîðèòì stable_partitiOn âûïîëíяåò òî æå ña- ìîå, íî ñ ñîõðaíåíèåì îòíîñèòåëüíîãî ïîðяäêa ýëåìåíòîâ. Óñëîâèå çaäaåòñя ñ ïî- ìîùüþ ôóíêöèè èëè ôóíêöèîíaëüíîãî îáúåêòa.
template
Bi partitiOn(Bi first, Bi last, Pred pred); template
Bi stable_partitiOn(Bi first, Bi last, Pred pred);

sort, stable_sort

Àëãîðèòì sOrt âûïîëíяåò ñîðòèðîâêó ýôôåêòèâíóþ ïîñëåäîâaòåëüíîñòè ça âðå- ìя, ïðîïîðöèîíaëüíîå N·log₂N. Äëя ñîõðaíåíèя ïîðяäêa ñëåäîâaíèя îäèíaêîâûõ ýëåìåíòîâ ñëåäóåò ïðèìåíяòü aëãîðèòì stable_sOrt. Âðåìя åãî ðaáîòû ïðîïîð- öèîíaëüíî N·(log₂N)².
template
vOid sOrt(Ran first, Ran last); template
vOid sOrt(Ran first, Ran last, COmpare COmp); template
vOid stable_sOrt(Ran first, Ran last); template
vOid stable_sOrt(Ran first, Ran last, COmpare COmp);
Îáðaòèòå âíèìaíèå ía òî, ÷òî ýòîìó aëãîðèòìó òðåáóþòñя èòåðaòîðû ïðîèçâîëü- íîãî äîñòóïa.

Алгоритмы работы с множествами и пирамидами

Àëãîðèòìû ýòîé êaòåãîðèè âûïîëíяþò ñîðòèðîâêó ìíîæåñòâ è îïåðaöèè ñ ïèða- ìèäaìè.  ïåðâîì ñëó÷aå îòñîðòèðîâaííaя ïîñëåäîâaòåëüíîñòü ðaññìaòðèâaåòñя êaê ìíîxåñòâî, a îïåðaöèè îáúåäèíåíèя è ïåðåñå÷åíèя èìåþò òîò æå ñìûñë, ÷òî â òåîðèè ìíîæåñòâ. Ïðèâåäåííûå aëãîðèòìû íå èçìåíяþò âõîäíûå ïîñëåäîâa- òåëüíîñòè, a âûõîäíûå ïîñëåäîâaòåëüíîñòè óïîðяäî÷åíû.
Ïèðaìèäîñ¹ íaçûâaåòñя ïîñëåäîâaòåëüíîñòü, äëя âñåõ ýëåìåíòîâ êîòîðîé âûïîë- íяþòñя óñëîâèя:
a[i]  a[2*i + 1]
a[i]  a[2*i + 2]
Ïðèìåð ïèðaìèäû èç 10 öåëûõ ÷èñåë: 23 20 21 17 19 18 15 12 10 14.
Êaê ñëåäóåò èç îïðåäåëåíèя, ìaêñèìaëüíûé ýëåìåíò ïèðaìèäû ðañïîëîæåí ïåð- âûì, ïîýòîìó ïèðaìèäû óäîáíî èñïîëüçîâaòü äëя ðåaëèçaöèè î÷åðåäåé ñ ïðè- îðèòåòaìè (ñì. c. 313), òaê êaê ñóùåñòâóþò ýôôåêòèâíûå aëãîðèòìû èçâëå÷åíèя ïåðâîãî ýëåìåíòa è äîáaâëåíèя íîâîãî ñ ñîõðaíåíèåì óñëîâèя ïèðaìèäaëüíîñòè.
Äëя ðaáîòû ñ ïèðaìèäîé òðåáóþòñя èòåðaòîðû ïðîèçâîëüíîãî äîñòóïa.
Òaê æå, êaê è äëя äðóãèõ êaòåãîðèé aëãîðèòìîâ, äëя êaæäîãî aëãîðèòìa ñóùåñò- âóåò äâå ôîðìû: îäía èñïîëüçóåò îïåðaöèþ <, a äðóãaя — ôóíêöèþ ñðaâíåíèя, çaäaííóþ ïîëüçîâaòåëåì.




¹ ×añòî ïèðaìèäó èçяùíî íaçûâaþò nó÷åñ (ïåðåâîä aíãëèéñêîãî ñëîâa heap).

Таблица 14.4. Алгоритмы работы с множествами и пирамидами