Алгоритмы сортировки

Курс лекций по олимпиадной информатике (C) Лекция 4. Алгоритмы сортировки Михаил Густокашин, 2009 Êîíñïåêòû ëåêöèé ïîäãîòîâëåíû äëÿ ñèñòåìû äèñòàíöèîííîé ïîäãîòîâêè, äåéñòâóþùåé íà ñàéòå . Ïðè íàõîæäåíèè îøèáîê èëè îïå÷àòîê ïðîñüáà ñîîáùàòü ïî àäðåñó informatics.mccme.ru [email protected] Версия C от 16.11.2009 1 Сортировка пузырьком Óñëîâèìñÿ ñ÷èòàòü ìàññèâ îòñîðòèðîâàííûì, åñëè ýëåìåíòû ðàñïîëîæåíû â ïîðÿäêå íåóáûâà4 4 4 2 4 íèÿ (ò.å. êàæäûé ýëåìåíò íå ìåíüøå ïðåäûäóùå9 9 9 4 2 ãî). Âñå ïðèìåðû áóäåì ðàññìàòðèâàòü íà òèïå 7 7 2 9 9 int, îäíàêî îí ìîæåò áûòü çàìåíåí ëþáûì äðó2 6 7 7 ãèì ñðàâíèìûì òèïîì äàííûõ. 7 Ðàññìîòðåíèå ìåòîäîâ ñîðòèðîâêè íà÷íåì ñ 6 2 6 6 6 ñîðòèðîâêè ïóçûðüêîì (BubbleSort). 3 3 3 3 3 Ýòî îäèí èç ïðîñòåéøèõ ìåòîäîâ ñîðòèðîâêè, êîòîðûé îáû÷íî âõîäèò â øêîëüíûé êóðñ Ðèñ. 1: Íóëåâîé ïðîõîä. Ñðàâíèâàåïðîãðàììèðîâàíèÿ. Íàçâàíèå ìåòîäà îòðàæàåò ìûå ïàðû è îáìåíû âûäåëåíû åãî ñóùíîñòü: íà êàæäîì øàãå ñàìûé ¾ëåãêèé¿ ýëåìåíò ïîäíèìàåòñÿ äî ñâîåãî ìåñòà (¾âñïëûâàåò¿). Äëÿ ýòîãî ìû ïðîñìàòðèâàåì âñå ýëåìåíòû ñíèçó ââåðõ, áåðåì ïàðó ñîñåäíèõ ýëåìåíòîâ è, â ñëó÷àå, åñëè îíè ñòîÿò íåïðàâèëüíî, ìåíÿåì èõ ìåñòàìè. Âìåñòî ïîäíÿòèÿ ñàìîãî ¾ëåãêîãî¿ ýëåìåíòà ìîæíî ¾òîïèòü¿ ñàìûé ¾òÿæåëûé¿. Ò.ê. çà êàæäûé øàã íà ñâîå ìåñòî âñòàåò ðîâíî 1 ýëåìåíò (ñàìûé ¾ëåãêèé¿ èç îñòàâøèõñÿ), òî íàì ïîòðåáóåòñÿ âûïîëíèòü 𝑁 øàãîâ. Òåêñò ôóíêöèè ñîðòèðîâêè ìîæíî çàïèñàòü òàê: void bubble_sort(int a[], int n) { int i, j, k; For(i, n) for (j=n-1; j>i; j--) if (a[j-1] > a[j]) { k = a[j-1]; a[j-1] = a[j]; a[j] = k; } } 1 Íàïîìíèì, ÷òî çäåñü ìû èñïîëüçîâàëè ìàêðîïîäñòàíîâêó #define For(a,b) for(a=0; a= a[y]) break; a[k]=a[y]; k=y; } a[k]=temp; } Ýòà ôóíêöèÿ ïîëó÷àåò óêàçàòåëü íà ìàññèâ, íîìåð ýëåìåíòà, êîòîðûé íåîáõîäèìî ïðîòîëêíóòü è ðàçìåð êó÷è. Ó íåå åñòü íåáîëüøèå îòëè÷èÿ îò îáû÷íûõ ôóíêöèé ðàáîòû ñ êó÷åé. Íîìåð ìèíèìàëüíîãî ïðåäêà õðàíèòñÿ â ïåðåìåííîé 𝑦, åñëè íåîáõîäèìîñòü â îáìåíàõ çàêîí÷åíà, òî ìû âûõîäèì èç öèêëà è çàïèñûâàåì ïðîñåÿííóþ ïåðåìåííóþ íà ïðåäíàçíà÷åííîå åé ìåñòî. Ñàìà ñîðòèðîâêà áóäåò ñîñòîÿòü èç ñîçäàíèÿ êó÷è èç ìàññèâà è 𝑁 ïåðåíîñîâ ýëåìåíòîâ ñ âåðøèíû êó÷è ñ ïîñëåäóþùèì âîññòàíîâëåíèåì ñâîéñòâà êó÷è: void heap_sort(int a[], int n) { int i, temp; for(i=n/2-1; i >= 0; i--) down_heap(a, i, n); for(i=n-1; i > 0; i--) { temp=a[i]; a[i]=a[0]; a[0]=temp; down_heap(a, 0, i); 3 } } Âñåãî â ïðîöåññå ðàáîòû àëãîðèòìà áóäåò âûïîëíåíî 3 × 𝑁/2 − 2 âûçîâà ôóíêöèè êàæäûé èç êîòîðûõ çàíèìàåò 𝑂(log 𝑁 ). Òàêèì îáðàçîì, ìû è ïîëó÷àåì èñêîìóþ ñëîæíîñòü â 𝑂(𝑁 log 𝑁 ), íå èñïîëüçóÿ ïðè ýòîì äîïîëíèòåëüíîé ïàìÿòè. Êîëè÷åñòâî ïðèñâàèâàíèé òàêæå ñîñòàâëÿåò 𝑂(𝑁 log 𝑁 ). Ïèðàìèäàëüíóþ ñîðòèðîâêó ñëåäóåò îñóùåñòâëÿòü, åñëè èç óñëîâèÿ çàäà÷è ïîíÿòíî, ÷òî åäèíñòâåííîé ðàçðåøåííîé îïåðàöèåé ÿâëÿåòñÿ ¾ïðîòàëêèâàíèå¿ ýëåìåíòà ïî êó÷å, ëèáî â ñëó÷àå îòñóòñòâèÿ äîïîëíèòåëüíîé ïàìÿòè. down_heap, 4 Быстрая сортировка Ìû óæå ðàññìàòðèâàëè èäåè, êîòîðûå èñïîëüçóþòñÿ â áûñòðîé ñîðòèðîâêå, ïðè ïîèñêå ïîðÿäêîâûõ ñòàòèñòèê. Òî÷íî òàê æå, êàê è â òîì àëãîðèòìå, ìû âûáèðàåì íåêèé îïîðíûé ýëåìåíò è âñå ÷èñëà, ìåíüøèå åãî ïåðåìåùàåì â ëåâóþ ÷àñòü ìàññèâà, à âñå ÷èñëà áîëüøèå åãî  â ïðàâóþ ÷àñòü. Çàòåì âûçûâàåì ôóíêöèþ ñîðòèðîâêè äëÿ êàæäîé èç ýòèõ ÷àñòåé. Òàêèì îáðàçîì, íàøà ôóíêöèÿ ñîðòèðîâêè äîëæíà ïðèíèìàòü óêàçàòåëü íà ìàññèâ è äâå ïåðåìåííûå, îáîçíà÷àþùèå ëåâóþ è ïðàâóþ ãðàíèöó ñîðòèðóåìîé îáëàñòè. 4 9 7 6 2 i 4 4 3 8 2 6 7 i 7 6 2 i j 9 3 3 8 4 j 9 9 8 j 7 6 2 j 3 8 i Ðèñ. 3: Ïåðâûé ïðîõîä áûñòðîé ñîðòèðîâêè Îñòàíîâèìñÿ áîëåå ïîäðîáíî íà âûáîðå îïîðíîãî ýëåìåíòà.  íåêîòîðûõ êíèãàõ ðåêîìåíäóåòñÿ âûáèðàòü ñëó÷àéíûé ýëåìåíò ìåæäó ëåâîé è ïðàâîé ãðàíèöåé. Õîòÿ òåîðåòè÷åñêè ýòî êðàñèâî è ïðàâèëüíî, íî íà ïðàêòèêå ñëåäóåò ó÷èòûâàòü, ÷òî ôóíêöèÿ ãåíåðàöèè ñëó÷àéíîãî ÷èñëà äîñòàòî÷íî ìåäëåííàÿ è òàêîé ìåòîä çàìåòíî óõóäøàåò ïðîèçâîäèòåëüíîñòü àëãîðèòìà â ñðåäíåì. Íàèáîëåå ÷àñòî èñïîëüçóåòñÿ ñåðåäèíà îáëàñòè, ò.å. ýëåìåíò ñ èíäåêñîì (𝑙 + 𝑟)/2. Ïðè òàêîì ïîäõîäå èñïîëüçóþòñÿ áûñòðûå îïåðàöèè ñëîæåíèÿ è äåëåíèÿ íà äâà, è â öåëîì îí ðàáîòàåò äîñòàòî÷íî íåïëîõî. Îäíàêî â íåêîòîðûõ çàäà÷àõ, ãäå ñóòüþ ÿâëÿåòñÿ èñêëþ÷èòåëüíî ñîðòèðîâêà, õèòðîå æþðè ñïåöèàëüíî ïîäáèðàåò òåñòû òàê, ÷òîáû ¾çàâàëèòü¿ ñòàíäàðòíóþ áûñòðóþ ñîðòèðîâêó ñ âûáîðîì îïîðíîãî ýëåìåíòà èç ñåðåäèíû. Ñòîèò çàìåòèòü, ÷òî ýòî î÷åíü ðåäêàÿ ñèòóàöèÿ, íî âñå æå ñòîèò çíàòü, ÷òî ìîæíî âûáèðàòü ïðîèçâîëüíûé ýëåìåíò ñ èíäåêñîì 𝑚 òàê, ÷òîáû âûïîëíÿëîñü íåðàâåíñòâî 𝑙 ≤ 𝑚 ≤ 𝑟. ×òîáû ýòî óñëîâèå âûïîëíÿëîñü, äîñòàòî÷íî âûáðàòü ïðîèçâîëüíûå äâà ÷èñëà 𝑥 è 𝑦 è âûáèðàòü 𝑚 èñõîäÿ èç ñëåäóþùåãî ñîîòíîøåíèÿ: 𝑚 = (𝑥×𝑙 +𝑦 ×𝑟)/(𝑥+𝑦). 4  öåëîì òàêîé ìåòîä áóäåò íåçíà÷èòåëüíî ïðîèãðûâàòü âûáîðó ñðåäíåãî ýëåìåíòà, ò.ê. òðåáóåò äâóõ äîïîëíèòåëüíûõ óìíîæåíèé. Ïðèâåäåì òåêñò ôóíêöèè áûñòðîé ñîðòèðîâêè ñ âûáîðîì ñðåäíåãî ýëåìåíòà â êà÷åñòâå îïîðíîãî: void quick_sort(int a[], int left, int right) { int i = left, j = right, temp, p; p = a[(left+right)/2]; do { while (a[i] < p) i++; while (a[j] > p) j--; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i <= j); if (j > left) quick_sort(a, left, j); if (i < right) quick_sort(a, i, right); } ×òîáû âîñïîëüçîâàòüñÿ áûñòðîé ñîðòèðîâêîé, íåîáõîäèìî ïåðåäàòü â ôóíêöèþ ëåâóþ è ïðàâóþ ãðàíèöû ñîðòèðóåìîãî ìàññèâà (ò.å., íàïðèìåð, âûçîâ äëÿ ìàññèâà a áóäåò âûãëÿäåòü êàê quick_sort(a, 0, n-1). Àëãîðèòì áûñòðîé ñîðòèðîâêè â ñðåäíåì èñïîëüçóåò 𝑂(𝑁 log 𝑁 ) ñðàâíåíèé è 𝑂(𝑁 log 𝑁 ) ïðèñâàèâàíèé (íà ïðàêòèêå äàæå ìåíüøå) è èñïîëüçóåò 𝑂(log 𝑁 ) äîïîëíèòåëüíîé ïàìÿòè (ñòåê äëÿ âûçîâà ðåêóðñèâíûõ ôóíêöèé).  õóäøåì ñëó÷àå àëãîðèòì èìååò ñëîæíîñòü 𝑂(𝑁 2) è èñïîëüçóåò 𝑂(𝑁 ) äîïîëíèòåëüíîé ïàìÿòè, îäíàêî âåðîÿòíîñòü âîçíèêíîâåíèÿ õóäøåãî ñëó÷àÿ êðàéíå ìàëà: íà êàæäîì øàãå âåðîÿòíîñòü õóäøåãî ñëó÷àÿ ðàâíà 2/𝑁 , ãäå 𝑁  òåêóùåå êîëè÷åñòâî ýëåìåíòîâ. Ðàññìîòðèì âîçìîæíûå îïòèìèçàöèè ìåòîäà áûñòðîé ñîðòèðîâêè. Âî-ïåðâûõ, ïðè âûçîâå ðåêóðñèâíîé ôóíêöèè âîçíèêàþò íàêëàäíûå ðàñõîäû íà õðàíåíèå ëîêàëüíûõ ïåðåìåííûõ (êîòîðûå íàì íå îñîáî íóæíû ïðè ðåêóðñèâíûõ âûçîâàõ) è äðóãîé ñëóæåáíîé èíôîðìàöèåé. Òàêèì îáðàçîì, ïðè çàìåíå ðåêóðñèè ñòåêîì ìû ïîëó÷èì íåáîëüøîé ïðèðîñò ïðîèçâîäèòåëüíîñòè è íåáîëüøîå ñíèæåíèå òðåáóåìîãî îáúåìà äîïîëíèòåëüíîé ïàìÿòè. Âî-âòîðûõ, êàê ìû çíàåì, âûçîâ ôóíêöèè  äîñòàòî÷íî íàêëàäíàÿ îïåðàöèÿ, à äëÿ íåáîëüøèõ ìàññèâîâ áûñòðàÿ ñîðòèðîâêà ðàáîòàåò íå î÷åíü õîðîøî. Ïîýòîìó, åñëè ïðè âûçîâå ôóíêöèè ñîðòèðîâêè â ìàññèâå íàõîäèòñÿ ìåíüøå, ÷åì 𝐾 ýëåìåíòîâ, ðàçóìíî èñïîëüçîâàòü êàêîé-ëèáî íåðåêóðñèâíûé ìåòîä, íàïðèìåð, ñîðòèðîâêó âñòàâêàìè èëè âûáîðîì. ×èñëî 𝐾 ïðè ýòîì âûáèðàåòñÿ â ðàéîíå 20, êîíêðåòíûå çíà÷åíèÿ ïîäáèðàþòñÿ îïûòíûì ïóòåì. Òàêàÿ ìîäèôèêàöèÿ ìîæåò äàòü äî 15% ïðèðîñòà ïðîèçâîäèòåëüíîñòè. Áûñòðóþ ñîðòèðîâêó ìîæíî èñïîëüçîâàòü è äëÿ äâóñâÿçíûõ ñïèñêîâ (ò.ê. â íåé îñóùåñòâëÿåòñÿ òîëüêî ïîñëåäîâàòåëüíûé äîñòóï ñ íà÷àëà è ñ êîíöà), íî â ýòîì ñëó÷àå âîçíèêàþò ïðîáëåìû ñ âûáîðîì îïîðíîãî ýëåìåíòà  åãî ïðèõîäèòñÿ áðàòü ïåðâûì èëè ïîñëåäíèì â ñîðòèðóåìîé îáëàñòè. Ýòó ïðîáëåìà ìîæíî ðåøèòü íåêèì íàáîðîì ïñåâäîñëó÷àéíûõ ïåðåñòàíîâîê ýëåìåíòîâ ñïèñêà, òîãäà äàæå åñëè äàííûå áûëè ïîäîáðàíû ñïåöèàëüíî, ýôôåêò íåéòðàëèçóåòñÿ. 5 5 Сортировка слияниями Ñîðòèðîâêà ñëèÿíèÿìè òàêæå îñíîâûâàåòñÿ íà èäåå, êîòîðàÿ óæå áûëà íàìè çàòðîíóòà ïðè ðàññìîòðåíèè àëãîðèòìà ïîèñêà äâóõ ìàêñèìàëüíûõ ýëåìåíòîâ.  ýòîì àëãîðèòìå ìû ñíà÷àëà ðàçîáüåì ýëåìåíòû íà ïàðû è óïîðÿäî÷èì èõ âíóòðè ïàðû. Çàòåì èç äâóõ ïàð ñîçäàäèì óïîðÿäî÷åííûå ÷åòâåðêè è ò.ä. 3 7 8 2 4 6 1 5 Ïîñëåäîâàòåëüíîñòè äëèíû 1 37 28 46 1 5 Ñëèÿíèå äî óïîðÿäî÷åííûõ ïàð 2378 1456 Ñëèÿíèå ïàð â óïîðÿäî÷åííûå ÷åòâåðêè 12345678 Ñëèÿíèå ïàð â óïîðÿäî÷åííûå ÷åòâåðêè Èíòåðåñ ïðåäñòàâëÿåò ñàì ïðîöåññ ñëèÿíèÿ: äëÿ êàæäîé èç ïîëîâèíîê ìû óñòàíàâëèâàåì óêàçàòåëè íà íà÷àëî, ñìîòðèì, â êàêîé èç ÷àñòåé ýëåìåíò ïî óêàçàòåëþ ìåíüøå, çàïèñûâàåì ýòîò ýëåìåíò â íîâûé ìàññèâ è ïåðåìåùàåì ñîîòâåòñòâóþùèé óêàçàòåëü. Îïèøåì ôóíêöèþ ñëèÿíèÿ ñëåäóþùèì îáðàçîì: void merge(int a[], int b[], int c, int d, int e) { int p1=c, p2=d, pres=c; while (p1 < d && p2 < e) if (a[p1] < a[p2]) b[pres++] = a[p1++]; else b[pres++] = a[p2++]; while (p1 < d) b[pres++]=a[p1++]; while (p2 < e) b[pres++]=a[p2++]; } Çäåñü 𝑎  èñõîäíûé ìàññèâ, 𝑏  ìàññèâ ðåçóëüòàòà, 𝑐 è 𝑑  óêàçàòåëè íà íà÷àëî ïåðâîé è âòîðîé ÷àñòè ñîîòâåòñòâåííî, 𝑒  óêàçàòåëü íà êîíåö âòîðîé ÷àñòè. Äàëåå îïèøåì äîâîëüíî õèòðóþ íåðåêóðñèâíóþ ôóíêöèþ ñîðòèðîâêè ñëèÿíèåì: void merge_sort(int a[], int n) { int *temp, *a2=a, *b=(int*)malloc(n*sizeof(int)), *b2; int c, k = 1, d, e; b2=b; while (k <= 2*n) { for (c=0; c