https://lightbulb-sun.swistak.codes/prod/_next/static/chunks/pages…-cz-5-dziel-i-zwyciezaj-527fc76734a96670.js

1(self.webpackChunk_N_E=self.webpackChunk_N_E||[]).push([[1960],{3182:(e,a,s)=>{"use strict";s.r(a),s.d(a,{Article:()=>k,__N_SSG:()=>u,default:()=>g});var n=s(37876),i=s(12687),t=s(59341),l=s(48230),o=s.n(l),c=s(70485);let r={src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/quicksort_zwyciezaj.d1933f84.png",height:584,width:638,blurDataURL:"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAgAAAAHCAMAAAACh/xsAAAAIVBMVEX////q7e33+vji5+Xx+vLc3uDJy8/w9PPV1tjY5trM3dS+lm2UAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAMElEQVR4nAXBiQEAIAwCsYM+qPsPbAJoVwBz8BZ4Bs3AVKJsKKVzXDjd2ja47n3mAxZCAM3ccug1AAAAAElFTkSuQmCC",blurWidth:8,blurHeight:7},m={src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/quicksort_dziel.79c70026.png",height:1109,width:559,blurDataURL:"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAQAAAAICAMAAADp7a43AAAADFBMVEX+/f3o6eHs7Ozx7/BHQJy7AAAACXBIWXMAAAsTAAALEwEAmpwYAAAAIElEQVR4nGNgZGJgYGBkBhGMIIKJiYmBCSLGzMwAlwUAAt8AJs09/6QAAAAASUVORK5CYII=",blurWidth:4,blurHeight:8},d={src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/mergesort.cc613f8d.png",height:560,width:648,blurDataURL:"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAgAAAAHCAMAAAACh/xsAAAAElBMVEXt7e3Y2Nj////n5+fg4OD19fWliJQnAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAK0lEQVR4nBXKsQ0AAAjDsDSF/19GrJbRJihkdSJNJVNmGRoY9kn2Z/F//h8N9ABwQVXepAAAAABJRU5ErkJggg==",blurWidth:8,blurHeight:7},p={src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/mergesort_zwyciezaj.13d18931.png",height:326,width:605,blurDataURL:"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAgAAAAECAMAAACEE47CAAAAElBMVEX29vbm5ub////u7u7f39/V1dUaG7LrAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAIUlEQVR4nAXBAQEAAAzCoDl9/8oHrhnX0qR24KYcKFn0AQXhAEuBdIT6AAAAAElFTkSuQmCC",blurWidth:8,blurHeight:4},j={src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/mergesort_scalanie.5a7ea7f9.png",height:877,width:681,blurDataURL:"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAICAMAAADtGH4KAAAADFBMVEX09fXq6+3x8vDs7eTpVca5AAAACXBIWXMAAAsTAAALEwEAmpwYAAAAJElEQVR4nC3JwQ0AAAjCwFr339kovi5Qugpg0ZD1J2K4tllwAAYnADZ6p2rbAAAAAElFTkSuQmCC",blurWidth:6,blurHeight:8},h={src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/mergesort_dziel.ecff12dd.png",height:267,width:632,blurDataURL:"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAgAAAADCAMAAACZFr56AAAAElBMVEX8/Pzm6OnZ297j4+Tt7vDX1tWIDdqaAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAHUlEQVR4nAXBgQEAIAwCINT1/8sBly3YQx/pSbsPAkQAK8gAHQgAAAAASUVORK5CYII=",blurWidth:8,blurHeight:3};function y(e){let a={a:"a",annotation:"annotation",code:"code",div:"div",em:"em",h2:"h2",h3:"h3",li:"li",math:"math",mi:"mi",mn:"mn",mo:"mo",mrow:"mrow",mstyle:"mstyle",msup:"msup",mtable:"mtable",mtd:"mtd",mtext:"mtext",mtr:"mtr",nav:"nav",ol:"ol",p:"p",path:"path",pre:"pre",semantics:"semantics",span:"span",svg:"svg",ul:"ul",...(0,t.R)(),...e.components};return(0,n.jsxs)(n.Fragment,{children:[(0,n.jsx)(a.nav,{className:"toc",children:(0,n.jsxs)(a.ol,{className:"toc-level toc-level-1",children:[(0,n.jsx)(a.li,{className:"toc-item toc-item-h2",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h2",href:"#uwaga-wstępna",children:"Uwaga wstępna"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h2",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h2",href:"#dziel-i-zwyciężaj-a-sortowanie",children:"Dziel i zwyciężaj a sortowanie"})}),(0,n.jsxs)(a.li,{className:"toc-item toc-item-h2",children:[(0,n.jsx)(a.a,{className:"toc-link toc-link-h2",href:"#sortowanie-szybkie",children:"Sortowanie szybkie"}),(0,n.jsxs)(a.ol,{className:"toc-level toc-level-2",children:[(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#dziel",children:"Dziel"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#zwyciężaj",children:"Zwyciężaj"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#rekurencja",children:"Rekurencja"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#rekursja-a-sortowanie-szybkie",children:"Rekursja a sortowanie szybkie"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#przetestuj",children:"Przetestuj!"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#wydajność-sortowania-szybkiego",children:"Wydajność sortowania szybkiego"})})]})]}),(0,n.jsxs)(a.li,{className:"toc-item toc-item-h2",children:[(0,n.jsx)(a.a,{className:"toc-link toc-link-h2",href:"#sortowanie-przez-scalanie",children:"Sortowanie przez scalanie"}),(0,n.jsxs)(a.ol,{className:"toc-level toc-level-2",children:[(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#dziel-1",children:"Dziel"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#zwyciężaj-1",children:"Zwyciężaj"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#scalanie",children:"Scalanie"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#podejście-top-down",children:"Podejście top-down"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#podejście-bottom-up",children:"Podejście bottom-up"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#przetestuj-1",children:"Przetestuj!"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#wydajność-sortowania-przez-scalanie",children:"Wydajność sortowania przez scalanie"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#optymalizacja",children:"Optymalizacja"})})]})]}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h2",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h2",href:"#właściwości-algorytm\xf3w-sortowania-opartych-na-metodzie-dziel-i-zwyciężaj",children:"Właściwości algorytm\xf3w sortowania opartych na metodzie „dziel i z

1wyciężaj”."})}),(0,n.jsxs)(a.li,{className:"toc-item toc-item-h2",children:[(0,n.jsx)(a.a,{className:"toc-link toc-link-h2",href:"#literatura",children:"Literatura"}),(0,n.jsxs)(a.ol,{className:"toc-level toc-level-2",children:[(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#pozycje-podstawowe",children:"Pozycje podstawowe"})}),(0,n.jsx)(a.li,{className:"toc-item toc-item-h3",children:(0,n.jsx)(a.a,{className:"toc-link toc-link-h3",href:"#pozycje-uzupełniające",children:"Pozycje uzupełniające"})})]})]})]})}),"\n","\n",(0,n.jsxs)(a.h2,{id:"uwaga-wstępna",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#uwaga-wstępna",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Uwaga wstępna"]}),"\n",(0,n.jsxs)(a.p,{children:["Tak jak poprzednio, kod użyty przy tworzeniu tego artykułu znajdziesz na moim GitHubie: ",(0,n.jsx)(a.a,{href:"https://github.com/swistak-codes/sorting-algorithms",children:"https://github.com/swistak-codes/sorting-algorithms"}),". Myślę, że już pamiętasz, że nie są to wzorcowe implementacje, a jedynie takie, kt\xf3re się dobrze wizualizuje."]}),"\n",(0,n.jsxs)(a.h2,{id:"dziel-i-zwyciężaj-a-sortowanie",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#dziel-i-zwyciężaj-a-sortowanie",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Dziel i zwyciężaj a sortowanie"]}),"\n",(0,n.jsxs)(a.p,{children:[(0,n.jsx)(a.a,{href:"/post/wyszukiwanie-w-listach",children:"W artykule o wyszukiwaniu"})," miałem okazję poruszyć temat metody „dziel i zwyciężaj”. Jest to jedna z podstawowych technik projektowania algorytm\xf3w, kt\xf3ra w dużym skr\xf3cie polega na rozwiązywaniu problem\xf3w po ich uprzednim podzieleniu na mniejsze."]}),"\n",(0,n.jsx)(a.p,{children:"Dokładnie w taki spos\xf3b wykorzystujemy tę metodę w sortowaniu. Dzielimy nasze sortowane kolekcje na coraz mniejsze, wykonując podczas dzielenia bądź też podczas p\xf3źniejszego złączania operacje, kt\xf3re doprowadzają do posortowania kolekcji. W taki właśnie spos\xf3b działają dwa najbardziej znane algorytmy sortowania tego typu, a zarazem uważane za jedne z najszybszych, jakie powstały — sortowanie szybkie (z ang. quicksort) oraz sortowanie przez scalanie (z ang. merge sort). Om\xf3wmy je."}),"\n",(0,n.jsxs)(a.h2,{id:"sortowanie-szybkie",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#sortowanie-szybkie",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Sortowanie szybkie"]}),"\n",(0,n.jsxs)(a.p,{children:["Sortowanie szybkie to prawdopodobnie najbardziej znany algorytm sortowania, kt\xf3ry jednocześnie sprawdza się w prawdziwych zastosowaniach. Wykorzystuje on metodę „dziel i zwyciężaj” i jest zaliczany do algorytm\xf3w sortowania przez zamianę (czyli tej samej kategorii, co ",(0,n.jsx)(a.a,{href:"/post/sortowanie-cz-2-sortowanie-babelkowe",children:"sortowanie bąbelkowe"}),"). Warto dodać, że algorytm nie wykorzystuje dodatkowych struktur danych, czyli sortuje w miejscu. Om\xf3wmy sobie teraz, jak algorytm działa. Podzielimy to na dwa etapy — dzielenie i „zwyciężanie”."]}),"\n",(0,n.jsxs)(a.h3,{id:"dziel",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#dziel",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Dziel"]}),"\n",(0,n.jsx)(a.p,{children:"Aby zacząć sortowanie szybkie, musimy podzielić tablicę na dwie mniejsze. Jednak aby podział miał sens, wszystkie elementy w lewej podtablicy muszą być mniejsze od każdego z element\xf3w w prawej podtablicy. Żeby tego dokonać, por\xf3wnujemy po kolei elementy z końca i początku kolekcji do wybranego elementu zwanego piwotem (zwykle uznajemy za niego pierwszy element). Interesuje nas taka kolejność, ponieważ elementy odmierzane przez lewy wskaźnik mają być mniejsze od piwota, natomiast przez prawy wskaźnik — większe. Jeżeli kolejność nie jest zachowana, zamieniamy je ze sobą. Gdy wskaźniki te się spotkają, oznacza to, że skończyliśmy rozmieszczanie, a miejsce ich spotkania to właśnie miejsce, według kt\xf3rego dzielimy. Pamiętajmy, że w tym momencie nie mamy posortowanej tablicy. Jedynie rozdzieliliśmy tablicę na dwie mniejsze, gdzie w jednej każdy element jest większy od każdego elementu z drugiej."}),"\n",(0,n.jsx)(a.p,{children:"Zobaczmy, jak się to odbywa na poniższym obrazku:"}),"\n",(0,n.jsx)(c._V,{image:m,alignCenter:!0,fullSize:!0,alt:"Schemat podziału w algorytmie quick sort",caption:(0,n.jsx)(n.Fragment,{children:"Schemat krok po kroku, na przykładzie, jak wygląda podział tablicy w algorytmie quicksort."})}),"\n",(0,n.jsx)(a.p,{children:"Zaczynamy od trzymania wskaźnik\xf3w poza rozpatrywaną tablicą (niepokazane na schemacie). Najpierw przesuwamy prawy wskaźnik do momentu, gdy trafimy na liczbę w złej kolejności, a potem analogicznie lewy. Każdy krok zaczynamy od przesunięcia jednego ze wskaźnik\xf3w. W pierwszym kroku od razu trafiliśmy na element w złym miejscu, więc zatrzymujemy wskaźnik. W drugim kroku sprawdzamy od lewej strony. Element na pozycji 0 też jest w złej kolejności (ma być mniejszy, nie r\xf3wny!), dlatego zatrzymujemy wskaźnik. Stąd, w trzecim kroku dokonujemy zamiany obu element\xf3w. Krok czwarty, piąty i sz\xf3sty to powt\xf3rka tego co widzieliśmy wcześniej, czyli znowu szukamy element\xf3w w złej kolejności i je zamieniamy. Krok si\xf3dmy zaczynamy oczywiście od przesunięcia wskaźnika i dochodzi tu do sytuacji, gdzie spotykają się one w jednej pozycji. Oznacza to, że przerywamy algorytm dzielenia i pozycję tę zwracamy — jest to miejsce, według kt\xf3rego dzielimy tablicę."}),"\n",(0,n.jsxs)(a.h3,{id:"zwyciężaj",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#zwyciężaj",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Zwyciężaj"]}),"\n",(0,n.jsx)(a.p,{children:"Zwycięstwem w przypadku takiego algorytmu byłoby otrzymanie posortowanej tablicy. Oczywiście po jednym podziale jeszcze tego nie mamy — podzieliliśmy dopiero na elementy mniejsze i większe od wybranego. W takim razie co robimy następnie? Aby zwyciężyć, powtarzamy procedurę dzielenia na tych mniejszych tablicach. Robimy to tak długo, aż podtablice będą jednoelementowe. Dzięki temu, że zamienialiśmy ze sobą elementy na bazie mniejsze-większe, w momencie kiedy dojdziemy do takich małych podtablic, otrzymujemy posortowaną tablicę. Możesz to zobaczyć na poniższym schemacie (moment dzielenia pokazany na poprzednim schemacie pominąłem i od razu zaprezentowałem jego rezultat)."}),"\n",(0,n.jsx)(c._V,{image:r,alignCenter:!0,fullSize:!0,alt:"Schemat zwyciężania w algorytmie quick sort",caption:(0,n.jsx)(n.Fragment,{children:"Schemat zwyciężania w algorytmie quicksort. Dzięki coraz większym podziałom problemu ostatecznie otrzymujemy posortowaną tablicę."})}),"\n",(0,n.jsxs)(a.h3,{id:"rekurencja",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#rekurencja",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Rekurencja"]}),"\n",(0,n.jsx)(a.p,{children:"Myślę, że wszystko, co opisałem do tej pory, ma sens w teorii i wydaje się być całkiem zrozumiałe. Jednak z tego opisu nie do końca wynika, jak to zaprogramować. Najbardziej problematyczny moment to oczywiście dzielenie na coraz to mniejsze tablice. Dlaczego? Nie wiemy, ile razy będziemy dzielić tablice, ile razy każdą z podzielonych tablic będziemy dzielić, a następnie, w jakiej kolejności rozwiązywać problem. Problemy tego typu najłatwiej jest rozwiązać, stosując rekurencję (zwaną też rekursją)."}),"\n",(0,n.jsx)(a.p,{children:"W celu wyjaśnienia tego pojęcia zacytuję jeden żart popularny wśr\xf3d matematyk\xf3w i informatyk\xf3w żart: aby zrozumieć, czym jest rekurencja, musisz zrozumieć, czym jest rekurencja. Jaki to ma sens? Ano taki, że rekurencja to, w dużym skr\xf3cie, zapętlenie przez odwołanie się funkcji do samej siebie. Przykładowo, z matematyki możesz kojarzyć ciąg Fibonacciego, kt\xf3ry wyglądał tak: 0, 1, 1, 2, 3, 5, 8, 13, 21... Wz\xf3r na niego wygląda następująco:"}),"\n",(0,n.jsx)(a.span,{className:"katex-display",children:(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",display:"block",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mtext,{children:"fib"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mo,{fence:"true",children:"{"}),(0,n.jsxs)(a.mtable,{rowspacing:"0.36em",columnalign:"left left",columnspacing:"1em",children:[(0,n.jsxs)(a.mtr,{children:[(0,n.jsx)(a.mtd,{children:(0,n.jsx)(a.mstyle,{scriptlevel:"0",displaystyle:"false",children:(0,n.jsx)(a.mn,{children:"0"})})}),(0,n.jsx)(a.mtd,{children:(0,n.jsx)(a.mstyle,{scriptlevel:"0",displaystyle:"false",children:(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mtext,{children:"dla\xa0"}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsx)(a.mn,{children:"0"}),(0,n.jsx)(a.mo,{separator:"true",children:","})]})})})]}),(0,n.jsxs)(a.mtr,{children:[(0,n.jsx)(a.mtd,{children:(0,n.jsx)(a.mstyle,{scriptlevel:"0",displaystyle:"false",children:(0,n.jsx)(a.mn,{children:"1"})})}),(0,n.jsx)(a.mtd,{children:(0,n.jsx)(a.mstyle,{scriptlevel:"0",displaystyle:"false",children:(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mtext,{children:"dla\xa0"}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsx)(a.mn,{children:"1"}),(0,n.jsx)(a.mo,{separator:"true",children:","})]})})})]}),(0,n.jsxs)(a.mtr,{children:[(0,n.jsx)(a.mtd,{children:(0,n.jsx)(a.mstyle,{scriptlevel:"0",displaystyle:"false",children:(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mtext,{children:"fib"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{children:"−"}),(0,n.jsx)(a.mn,{children:"1"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"}),(0,n.jsx)(a.mo,{children:"+"}),(0,n.jsx)(a.mtext,{children:"fib"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{children:"−"}),(0,n.jsx)(a.mn,{children:"2"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"})]})})}),(0,n.jsx)(a.mtd,{children:(0,n.jsx)(a.mstyle,{scriptlevel:"0",displaystyle:"false",children:(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mtext,{children:"dla\xa0"}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{children:">"}),(0,n.jsx)(a.mn,{children:"1."})]})})})]})]})]})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\text{fib}(n) = \\begin{cases}\n0 & \\text{dla } n = 0, \\\\\n1 & \\text{dla } n = 1, \\\\\n\\text{fib}(n-1) + \\text{fib}(n-2) & \\text{dla } n > 1.\n\\end{cases}"})]})})}),(0,n.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib"})}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mclose",children:")"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"4.32em",verticalAlign:"-1.91em"}}),(0,n.jsxs)(a.span,{className:"minner",children:[(0,n.jsx)(a.span,{className:"mopen",children:(0,n.jsx)(a.span,{className:"delimsizing mult",children:(0,n.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,n.jsxs)(a.span,{className:"vlist-r",children:[(0,n.jsxs)(a.span,{className:"vlist",style:{height:"2.35em"}

1,children:[(0,n.jsxs)(a.span,{style:{top:"-2.2em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.15em"}}),(0,n.jsx)(a.span,{className:"delimsizinginner delim-size4",children:(0,n.jsx)(a.span,{children:"⎩"})})]}),(0,n.jsxs)(a.span,{style:{top:"-2.192em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.15em"}}),(0,n.jsx)(a.span,{style:{height:"0.316em",width:"0.8889em"},children:(0,n.jsx)(a.svg,{xmlns:"http://www.w3.org/2000/svg",width:"0.8889em",height:"0.316em",style:{width:"0.8889em"},viewBox:"0 0 888.89 316",preserveAspectRatio:"xMinYMin",children:(0,n.jsx)(a.path,{d:"M384 0 H504 V316 H384z M384 0 H504 V316 H384z"})})})]}),(0,n.jsxs)(a.span,{style:{top:"-3.15em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.15em"}}),(0,n.jsx)(a.span,{className:"delimsizinginner delim-size4",children:(0,n.jsx)(a.span,{children:"⎨"})})]}),(0,n.jsxs)(a.span,{style:{top:"-4.292em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.15em"}}),(0,n.jsx)(a.span,{style:{height:"0.316em",width:"0.8889em"},children:(0,n.jsx)(a.svg,{xmlns:"http://www.w3.org/2000/svg",width:"0.8889em",height:"0.316em",style:{width:"0.8889em"},viewBox:"0 0 888.89 316",preserveAspectRatio:"xMinYMin",children:(0,n.jsx)(a.path,{d:"M384 0 H504 V316 H384z M384 0 H504 V316 H384z"})})})]}),(0,n.jsxs)(a.span,{style:{top:"-4.6em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.15em"}}),(0,n.jsx)(a.span,{className:"delimsizinginner delim-size4",children:(0,n.jsx)(a.span,{children:"⎧"})})]})]}),(0,n.jsx)(a.span,{className:"vlist-s",children:"​"})]}),(0,n.jsx)(a.span,{className:"vlist-r",children:(0,n.jsx)(a.span,{className:"vlist",style:{height:"1.85em"},children:(0,n.jsx)(a.span,{})})})]})})}),(0,n.jsx)(a.span,{className:"mord",children:(0,n.jsxs)(a.span,{className:"mtable",children:[(0,n.jsx)(a.span,{className:"col-align-l",children:(0,n.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,n.jsxs)(a.span,{className:"vlist-r",children:[(0,n.jsxs)(a.span,{className:"vlist",style:{height:"2.41em"},children:[(0,n.jsxs)(a.span,{style:{top:"-4.41em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.008em"}}),(0,n.jsx)(a.span,{className:"mord",children:(0,n.jsx)(a.span,{className:"mord",children:"0"})})]}),(0,n.jsxs)(a.span,{style:{top:"-2.97em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.008em"}}),(0,n.jsx)(a.span,{className:"mord",children:(0,n.jsx)(a.span,{className:"mord",children:"1"})})]}),(0,n.jsxs)(a.span,{style:{top:"-1.53em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.008em"}}),(0,n.jsxs)(a.span,{className:"mord",children:[(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib"})}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"−"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mord",children:"1"}),(0,n.jsx)(a.span,{className:"mclose",children:")"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"+"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib"})}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"−"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mord",children:"2"}),(0,n.jsx)(a.span,{className:"mclose",children:")"})]})]})]}),(0,n.jsx)(a.span,{className:"vlist-s",children:"​"})]}),(0,n.jsx)(a.span,{className:"vlist-r",children:(0,n.jsx)(a.span,{className:"vlist",style:{height:"1.91em"},children:(0,n.jsx)(a.span,{})})})]})}),(0,n.jsx)(a.span,{className:"arraycolsep",style:{width:"1em"}}),(0,n.jsx)(a.span,{className:"col-align-l",children:(0,n.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,n.jsxs)(a.span,{className:"vlist-r",children:[(0,n.jsxs)(a.span,{className:"vlist",style:{height:"2.41em"}

1,children:[(0,n.jsxs)(a.span,{style:{top:"-4.41em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.008em"}}),(0,n.jsxs)(a.span,{className:"mord",children:[(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"dla\xa0"})}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mord",children:"0"}),(0,n.jsx)(a.span,{className:"mpunct",children:","})]})]}),(0,n.jsxs)(a.span,{style:{top:"-2.97em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.008em"}}),(0,n.jsxs)(a.span,{className:"mord",children:[(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"dla\xa0"})}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mord",children:"1"}),(0,n.jsx)(a.span,{className:"mpunct",children:","})]})]}),(0,n.jsxs)(a.span,{style:{top:"-1.53em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"3.008em"}}),(0,n.jsxs)(a.span,{className:"mord",children:[(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"dla\xa0"})}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:">"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mord",children:"1."})]})]})]}),(0,n.jsx)(a.span,{className:"vlist-s",children:"​"})]}),(0,n.jsx)(a.span,{className:"vlist-r",children:(0,n.jsx)(a.span,{className:"vlist",style:{height:"1.91em"},children:(0,n.jsx)(a.span,{})})})]})})]})}),(0,n.jsx)(a.span,{className:"mclose nulldelimiter"})]})]})]})]})}),"\n",(0,n.jsx)(a.p,{children:"Jest to nic innego jak funkcja rekurencyjna. O ile zerowy i pierwszy element obliczymy od razu, wyższe wymagają odwoływania się do poprzednich wartości funkcji. Przykładowo, aby poznać wartość trzeciego elementu, zrobimy to następująco:"}),"\n",(0,n.jsx)(a.span,{className:"katex-display",children:(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",display:"block",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mtext,{children:"fib(3)"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsx)(a.mtext,{children:"fib(2)"}),(0,n.jsx)(a.mo,{children:"+"}),(0,n.jsx)(a.mtext,{children:"fib(1)"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mtext,{children:"fib(1)"}),(0,n.jsx)(a.mo,{children:"+"}),(0,n.jsx)(a.mtext,{children:"fib(0)"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"}),(0,n.jsx)(a.mo,{children:"+"}),(0,n.jsx)(a.mtext,{children:"fib(1)"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mn,{children:"1"}),(0,n.jsx)(a.mo,{children:"+"}),(0,n.jsx)(a.mn,{children:"0"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"}),(0,n.jsx)(a.mo,{children:"+"}),(0,n.jsx)(a.mn,{children:"1"}),(0,n.jsx)(a.mo,{children:"="}),(0,n.jsx)(a.mn,{children:"2"})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\text{fib(3)} = \\text{fib(2)} + \\text{fib(1)} = (\\text{fib(1)} + \\text{fib(0)}) + \\text{fib(1)}  = (1 + 0) + 1 = 2"})]})})}),(0,n.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib(3)"})}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib(2)"})}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"+"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib(1)"})}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib(1)"})}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"+"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib(0)"})}),(0,n.jsx)(a.span,{className:"mclose",children:")"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"+"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord text",children:(0,n.jsx)(a.span,{className:"mord",children:"fib(1)"})}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord",children:"1"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"+"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord",children:"0"}),(0,n.jsx)(a.span,{className:"mclose",children:")"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,n.jsx)(a.span,{className:"mbin",children:"+"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"0.6444em"}}),(0,n.jsx)(a.span,{className:"mord",children:"1"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,n.jsx)(a.span,{className:"mrel",children:"="}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"0.6444em"}}),(0,n.jsx)(a.span,{className:"mord",children:"2"})]})]})]})}),"\n",(0,n.jsx)(a.p,{children:"Natomiast w językach programowania zrobilibyśmy to w taki spos\xf3b (na przykładzie JavaScript, ale w wielu innych będzie wyglądać bardzo podobnie):"}),"\n",(0,n.jsx)(a.div,{className:"remark-highlight",children:(0,n.jsx)(a.pre,{className:"language-javascript",children:(0,n.jsxs)(a.code,{className:"language-javascript",children:[(0,n.jsx)(a.span,{className:"token keyword",children:"function"})," ",(0,n.jsx)(a.span,{className:"token function",children:"fib"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token parameter",children:"n"}),(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"{"}),"\n  ",(0,n.jsx)(a.span,{className:"token keyword control-flow",children:"switch"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),"n",(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"{"}),"\n    ",(0,n.jsx)(a.span,{className:"token keyword",children:"case"})," ",(0,n.jsx)(a.span,{className:"token number",children:"0"}),(0,n.jsx)(a.span,{className:"token operator",children:":"})," ",(0,n.jsx)(a.span,{className:"token keyword control-flow",children:"return"})," ",(0,n.jsx)(a.span,{className:"token number",children:"0"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token keyword",children:"case"})," ",(0,n.jsx)(a.span,{className:"token number",children:"1"}),(0,n.jsx)(a.span,{className:"token operator",children:":"})," ",(0,n.jsx)(a.span,{className:"token keyword control-flow",children:"return"})," ",(0,n.jsx)(a.span,{className:"token number",children:"1"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token keyword module",children:"default"}),(0,n.jsx)(a.span,{className:"token operator",children:":"})," ",(0,n.jsx)(a.span,{className:"token keyword control-flow",children:"return"})," ",(0,n.jsx)(a.span,{className:"token function",children:"fib"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),"n ",(0,n.jsx)(a.span,{className:"token operator",children:"-"})," ",(0,n.jsx)(a.span,{className:"token number",children:"1"}),(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token operator",children:"+"})," ",(0,n.jsx)(a.span,{className:"token function",children:"fib"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),"n ",(0,n.jsx)(a.span,{className:"token operator",children:"-"})," ",(0,n.jsx)(a.span,{className:"token number",children:"2"}),(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n  ",(0,n.jsx)(a.span,{className:"token punctuation",children:"}"}),"\n",(0,n.jsx)(a.span,{className:"token punctuation",children:"}"}),"\n"]})})}),"\n",(0,n.jsxs)(a.h3,{id:"rekursja-a-sortowanie-szybkie",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#rekursja-a-sortowanie-szybkie",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Rekursja a sortowanie szybkie"]}),"\n",(0,n.jsx)(a.p,{children:"Tylko teraz jak zastosować tę technikę na przykładzie sortowania szybkiego? Schemat wygląda następująco. Najpierw wykonujemy procedurę dzielenia, w wyniku kt\xf3rej otrzymujemy punkt podziału. Gdy otrzymaliśmy punkt podziału, znowu odpalamy sortowanie szybkie, tym razem dwa razy z rzędu — pierwszy raz dla tablicy w zakresie początek-p

1odział, a drugi raz dla podział-koniec. Wykonujemy to tylko i wyłącznie wtedy, kiedy koniec zakresu naszej podtablicy nie zr\xf3wnał się z jej początkiem. W kodzie wyglądałoby to następująco:"}),"\n",(0,n.jsx)(a.div,{className:"remark-highlight",children:(0,n.jsx)(a.pre,{className:"language-javascript",children:(0,n.jsxs)(a.code,{className:"language-javascript",children:[(0,n.jsx)(a.span,{className:"token keyword",children:"function"})," ",(0,n.jsx)(a.span,{className:"token function",children:"quickSort"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsxs)(a.span,{className:"token parameter",children:[(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," p",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," r"]}),(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"{"}),"\n  ",(0,n.jsx)(a.span,{className:"token keyword control-flow",children:"if"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),"p ",(0,n.jsx)(a.span,{className:"token operator",children:"<"})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"{"}),"\n    ",(0,n.jsx)(a.span,{className:"token keyword",children:"var"})," q ",(0,n.jsx)(a.span,{className:"token operator",children:"="})," ",(0,n.jsx)(a.span,{className:"token function",children:"partition"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," p",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token function",children:"quickSort"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," p",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," q",(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token function",children:"quickSort"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," q ",(0,n.jsx)(a.span,{className:"token operator",children:"+"})," ",(0,n.jsx)(a.span,{className:"token number",children:"1"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n  ",(0,n.jsx)(a.span,{className:"token punctuation",children:"}"}),"\n",(0,n.jsx)(a.span,{className:"token punctuation",children:"}"}),"\n"]})})}),"\n",(0,n.jsx)(a.p,{children:"Sp\xf3jrzmy na to, co przedstawia powyższy kod. Funkcja quickSort przyjmuje jako parametry tablicę do posortowania A, wskaźnik początku podtablicy p i wskaźnik końca podtablicy r.  Jeżeli podtablica ma jakieś elementy, to wykonujemy sortowanie. Najpierw mamy procedurę dzielenia partition, kt\xf3ra zwraca nam punkt podziału q. Jak widzisz, zgadza się wszystko do tej pory z opisem przedstawionym powyżej, więc dw\xf3ch kolejnych linii już opisywać nie będę. Jeżeli chcesz zaprogramować to na własną rękę, to jedyne co Ci pozostaje, to napisać funkcję dzielącą."}),"\n",(0,n.jsxs)(a.h3,{id:"przetestuj",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#przetestuj",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Przetestuj!"]}),"\n",(0,n.jsx)(a.p,{children:"Jeśli czytałeś poprzednie artykuły, to spotkałeś się już z moimi wizualizacjami sortowania. Tak też jest i tutaj. Pokombinuj z r\xf3żnymi parametrami i sprawdź, jak sprawuje się sortowanie szybkie zaimplementowane w najprostszy możliwy spos\xf3b."}),"\n",(0,n.jsx)(c.vL,{src:"/iframe-content/sorting-visualizer/index.html?algorithm=quickSort",minHeight:620}),"\n",(0,n.jsxs)(a.h3,{id:"wydajność-sortowania-szybkiego",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#wydajność-sortowania-szybkiego",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Wydajność sortowania szybkiego"]}),"\n",(0,n.jsxs)(a.p,{children:["Jak można zauważyć, nazwa nie wzięła się znikąd. Sortowanie szybkie faktycznie jest szybkie, jednak ma dość duży mankament — jego szybkość jest zależna od stopnia, w jakim dane wejściowe są posortowane. W przeciętnym przypadku osiągamy wręcz idealną wydajność ",(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mi,{children:"O"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mi,{children:"log"}),(0,n.jsx)(a.mo,{children:"⁡"}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"O(n\\log{n})"})]})})}),(0,n.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"O"}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,n.jsxs)(a.span,{className:"mop",children:["lo",(0,n.jsx)(a.span,{style:{marginRight:"0.01389em"},children:"g"})]}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,n.jsx)(a.span,{className:"mord",children:(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"})}),(0,n.jsx)(a.span,{className:"mclose",children:")"})]})})]}),", natomiast w najgorszym ",(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mi,{children:"O"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsxs)(a.msup,{children:[(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mn,{children:"2"})]}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"O(n^2)"})]})})}),(0,n.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1.064

11em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"O"}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsxs)(a.span,{className:"mord",children:[(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"msupsub",children:(0,n.jsx)(a.span,{className:"vlist-t",children:(0,n.jsx)(a.span,{className:"vlist-r",children:(0,n.jsx)(a.span,{className:"vlist",style:{height:"0.8141em"},children:(0,n.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,n.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,n.jsx)(a.span,{className:"mord mtight",children:"2"})})]})})})})})]}),(0,n.jsx)(a.span,{className:"mclose",children:")"})]})})]}),". Od czego to zależy?"]}),"\n",(0,n.jsx)(a.p,{children:"Najlepszy przypadek dla quicksort jest wtedy, gdy element dzielący zawsze jest medianą sprawdzanej podtablicy (czyli elementem, kt\xf3ry po posortowaniu byłby w jej środku). Najgorszy jest wtedy, gdy element dzielący jest największym lub najmniejszym elementem w podtablicy. Ten najgorszy przypadek możesz zasymulować na powyższym przykładzie przez posortowanie uprzednio posortowanej tablicy."}),"\n",(0,n.jsx)(a.p,{children:"Aby usprawnić algorytm, moglibyśmy eksperymentować z metodą dzielenia. Spos\xf3b pokazany przeze mnie jest najpopularniejszym i najprostszym, jednakże, jak widać, nieidealnym. Innym znanym powszechnie sposobem jest algorytm podział\xf3w Lomuta, jednak tu r\xf3wnież osiągniemy kwadratową złożoność w najgorszym przypadku. Obecnie do optymalizacji podchodzi się przez dzielenie tablicy na więcej niż dwie podtablice. Tutaj jako ciekawostkę warto zauważyć, że podejście to było kiedyś uważane za niewydajne (np. Sedgewick, 1977), jednak najnowsze badania temu zaprzeczają (np. Yaroslavskiy, 2009)."}),"\n",(0,n.jsx)(a.p,{children:"Innym mankamentem sortowania szybkiego, niezbyt widocznym na pierwszy rzut oka, jest tak szeroko om\xf3wiona przeze mnie rekurencja. O ile wydawać by się mogło, że jest to super sprawa, a do tego algorytm działa w miejscu, bo nie tworzymy kopii tablicy, to aby wykonać rekurencję, komputer musi utrzymywać tak zwany stos wywołań, co powoduje coraz większe zajmowanie pamięci wraz z każdym wywołaniem rekurencyjnym. Dlatego też powstała wersja sortowania szybkiego niewykorzystująca rekursji (opisana np. przez Wirtha), jednak rzadko można się z nią spotkać w praktyce."}),"\n",(0,n.jsxs)(a.h2,{id:"sortowanie-przez-scalanie",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#sortowanie-przez-scalanie",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Sortowanie przez scalanie"]}),"\n",(0,n.jsx)(a.p,{children:"Innym popularnym rodzajem sortowania bazującym na metodzie „dziel i zwyciężaj” jest sortowanie przez scalanie. Jest to algorytm najbardziej unikatowy ze wszystkich, kt\xf3re do tej pory sobie om\xf3wiliśmy, bo wyznacza on własną kategorię algorytm\xf3w — algorytmy sortowania przez scalanie. Do tego, co ciekawe, jest też jednym z najstarszych podejść do sortowania, ponieważ został opisane już w 1945 roku przez Johna von Neumanna."}),"\n",(0,n.jsx)(a.p,{children:"Podejście do dzielenia i zwyciężania w merge sort jest zupełnie inne niż w quicksort. Gdy w sortowaniu szybkim gł\xf3wny nacisk był na dzielenie, i to w jego trakcie wykonywaliśmy najważniejsze operacje, tak tutaj ciężar przechodzi na „zwyciężanie”."}),"\n",(0,n.jsxs)(a.h3,{id:"dziel-1",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#dziel-1",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Dziel"]}),"\n",(0,n.jsx)(a.p,{children:"Procedura dzielenia w algorytmie sortowania przez scalanie ogranicza się tylko i wyłącznie do... dzielenia. Nie robimy tutaj nic więcej. Naszym celem jest takie podzielenie wejściowej tablicy, aby otrzymać tablice jednoelementowe."}),"\n",(0,n.jsx)(c._V,{image:h,alignCenter:!0,fullSize:!0,alt:"Schemat dzielenia w algorytmie merge sort",caption:(0,n.jsx)(n.Fragment,{children:"Dzielenie w algorytmie sortowania przez scalanie."})}),"\n",(0,n.jsxs)(a.h3,{id:"zwyciężaj-1",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#zwyciężaj-1",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Zwyciężaj"]}),"\n",(0,n.jsx)(a.p,{children:"Skoro dzielenie było proste, to w fazie zwyciężania musi być ciężej. Tak też właśnie jest. Faza zwyciężania jest nazywana scalaniem, ponieważ to, co tutaj robimy, to złączamy n

1a nowo podzielone tablice. Oczywiście nie jest to po prostu złączenie. Złączając, dbamy o to, aby elementy połączyć w odpowiedniej kolejności, dlatego w jego trakcie por\xf3wnujemy ze sobą elementy obu tablic i wstawiamy je do nowej, złączonej w odpowiedniej kolejności. Możesz to zobaczyć na poniższym schemacie, gdzie scalimy tablicę podzieloną na poprzednim rysunku."}),"\n",(0,n.jsx)(c._V,{image:p,alignCenter:!0,fullSize:!0,alt:"Schemat zwyciężania w algorytmie merge sort",caption:(0,n.jsx)(n.Fragment,{children:"Schemat zwyciężania w merge sort."})}),"\n",(0,n.jsx)(a.p,{children:"Jak możesz zobaczyć na tym przykładzie, złączamy tablicę aż do momentu uzyskania posortowanej. Tylko teraz jak dokładnie wygląda samo scalanie?"}),"\n",(0,n.jsxs)(a.h3,{id:"scalanie",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#scalanie",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Scalanie"]}),"\n",(0,n.jsx)(a.p,{children:"Zerknijmy na kolejny schemat:"}),"\n",(0,n.jsx)(c._V,{image:j,alignCenter:!0,fullSize:!0,alt:"Schemat scalania w algorytmie merge sort",caption:(0,n.jsx)(n.Fragment,{children:"Schemat działania scalania w algorytmie merge sort."})}),"\n",(0,n.jsx)(a.p,{children:"Aby scalić ze sobą elementy, tworzymy nową tablicę wynikową. Następnie przechodzimy po kolei po obu rozpatrywanych tablicach. Por\xf3wnu

1jemy ze sobą elementy i bierzemy mniejszy z nich. W tablicy, z kt\xf3rej wzięliśmy element, przesuwamy wskaźnik, natomiast w drugiej zostawiamy go na miejscu. Dalej por\xf3wnujemy i zbieramy elementy. W pewnym momencie dojdziemy do przypadku, gdzie w jednej z tablic wyszliśmy wskaźnikiem poza jej zakres (na schemacie punkt 6). Wtedy możemy wprost przepisać pozostałą część drugiej tablicy do wyniku."}),"\n",(0,n.jsxs)(a.h3,{id:"podejście-top-down",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#podejście-top-down",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Podejście top-down"]}),"\n",(0,n.jsx)(a.p,{children:"Podsumowując to, co do tej pory zobaczyliśmy, możemy algorytm sortowania przez scalanie sprowadzić do takiego oto prostego schematu działania:"}),"\n",(0,n.jsx)(c._V,{image:d,alignCenter:!0,fullSize:!0,alt:"Schemat działania algorytmu merge sort",caption:(0,n.jsx)(n.Fragment,{children:"Schemat działania merge sort."})}),"\n",(0,n.jsx)(a.p,{children:"Jest to tak zwane podejście top-down. Najpierw rozdzielamy tablicę na jednoelementowe podtablice, a następnie wykonujemy operację scalania. Wszystko to możemy ponownie zrobić za pomocą rekurencji. W kodzie wygląda to bardzo podobnie jak w przypadku quicksort:"}),"\n",(0,n.jsx)(a.div,{className:"remark-highlight",children:(0,n.jsx)(a.pre,{className:"language-javascript",children:(0,n.jsxs)(a.code,{className:"language-javascript",children:[(0,n.jsx)(a.span,{className:"token keyword",children:"function"})," ",(0,n.jsx)(a.span,{className:"token function",children:"mergeSort"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsxs)(a.span,{className:"token parameter",children:[(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," p",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," r"]}),(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"{"}),"\n  ",(0,n.jsx)(a.span,{className:"token keyword control-flow",children:"if"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),"p ",(0,n.jsx)(a.span,{className:"token operator",children:"<"})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token punctuation",children:"{"}),"\n    ",(0,n.jsx)(a.span,{className:"token keyword",children:"var"})," q ",(0,n.jsx)(a.span,{className:"token operator",children:"="})," ",(0,n.jsx)(a.span,{className:"token known-class-name class-name",children:"Math"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"."}),(0,n.jsx)(a.span,{className:"token method function property-access",children:"floor"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),"p ",(0,n.jsx)(a.span,{className:"token operator",children:"+"})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"})," ",(0,n.jsx)(a.span,{className:"token operator",children:"/"})," ",(0,n.jsx)(a.span,{className:"token number",children:"2"}),(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token function",children:"mergeSort"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," p",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," q",(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token function",children:"mergeSort"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," q ",(0,n.jsx)(a.span,{className:"token operator",children:"+"})," ",(0,n.jsx)(a.span,{className:"token number",children:"1"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n    ",(0,n.jsx)(a.span,{className:"token function",children:"merge"}),(0,n.jsx)(a.span,{className:"token punctuation",children:"("}),(0,n.jsx)(a.span,{className:"token constant",children:"A"}),(0,n.jsx)(a.span,{className:"token punctuation",children:","})," p",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," q",(0,n.jsx)(a.span,{className:"token punctuation",children:","})," r",(0,n.jsx)(a.span,{className:"token punctuation",children:")"}),(0,n.jsx)(a.span,{className:"token punctuation",children:";"}),"\n  ",(0,n.jsx)(a.span,{className:"token punctuation",children:"}"}),"\n",(0,n.jsx)(a.span,{className:"token punctuation",children:"}"}),"\n"]})})}),"\n",(0,n.jsx)(a.p,{children:"Jedynymi r\xf3żnicami jest to, że tym razem punkt podziału wyznaczamy jako efekt dzielenia (zaokrąglone w d\xf3ł), a po wywołaniach rekurencyjnych wywołujemy funkcję złączającą."}),"\n",(0,n.jsxs)(a.h3,{id:"podejście-bottom-up",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#podejście-bottom-up",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Podejście bottom-up"]}),"\n",(0,n.jsx)(a.p,{children:"Możesz sobie teraz zadać pytanie — tylko po co rozdzielać? Przecież od razu możemy potraktować tablicę wejściową jako składającą się z n jednoelementowych tablic. Na tym też polega podejście bottom-up. W tej odmianie sortowania przez scalanie całkowicie rezygnujemy z rekurencji. Pominę jednak przedstawianie tego podejścia i zachęcam Cię do sprawdzenia go na własną rękę."}),"\n",(0,n.jsxs)(a.h3,{id:"przetestuj-1",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#przetestuj-1",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Przetestuj!"]}),"\n",(0,n.jsx)(a.p,{children:"Poniżej możesz sprawdzić działanie sortowania przez scalanie w wersji top-down. Od razu jednak wspomnę, że wizualizacja może sprawiać wrażenie „skakania”, Bierze się to stąd, że układamy elementy do tablicy w określone pozycje, a nie tak jak dotąd zamienialiśmy."}),"\n",(0,n.jsx)(c.vL,{src:"/iframe-content/sorting-visualizer/index.html?algorithm=mergeSort",minHeight:640}),"\n",(0,n.jsxs)(a.h3,{id:"wydajność-sortowania-przez-scalanie",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#wydajność-sortowania-przez-scalanie",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Wydajność sortowania przez scalanie"]}),"\n",(0,n.jsxs)(a.p,{children:["Sortowanie przez scalanie, podobnie jak quicksort, r\xf3wnież bardzo szybko sortuje tablice. Zdecydowaną zaletą tego algorytmu jest to, że na jego wydajność nie wpływa stopień uprzedniego posortowania danych. Dzięki temu w każdym przypadku osiągamy złożoność obliczeniową ",(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mi,{children:"O"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mi,{children:"log"}),(0,n.jsx)(a.mo,{children:"⁡"}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"O(n\\log{n})"})]})})}),(0,n.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"O"}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,n.jsxs)(a.span,{className:"mop",children:["lo",(0,n.jsx)(a.span,{style:{marginRight:"0.01389em"},children:"g"})]}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,n.jsx)(a.span,{className:"mord",children:(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"})}),(0,n.jsx)(a.span,{className:"mclose",children:")"})]})})]}),". Brzmi idealnie?"]}),"\n",(0,n.jsx)(a.p,{children:"Aż za bardzo idealnie, więc musi coś być tutaj nie tak. Owe „nie tak” to złożoność pamięciowa tego algorytmu. Podczas gdy w sortowaniu szybkim obciążaliśmy pamięć wywołaniami rekurencyjnymi, tak tutaj dodatkowo używamy tablic pomocniczych do scalania element\xf3w. Oznacza to, że w najgorszym wypadku algorytm potrafi zająć dodatkowo tyle samo pamięci, co zajmowała oryginalna tablica!"}),"\n",(0,n.jsxs)(a.h3,{id:"optymalizacja",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#optymalizacja",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Optymalizacja"]}),"\n",(0,n.jsx)(a.p,{children:"Zadajmy sobie tradycyjne pytanie — czy możemy coś z tym zrobić? Czy możemy polepszyć jeszcze bardziej sortowanie przez scalanie? Tak, i jest do tego kilka podejść, kt\xf3re kr\xf3tko om\xf3wię."}),"\n",(0,n.jsx)(a.p,{children:"Jedną z optymalizacji sortowania przez scalanie, kt\xf3ra może ograniczyć liczbę por\xf3wnań, jest tak zwany naturalny merge sort. W tym podejściu nie dzielimy tablicy do jednoelementowych podtablic, ale zatrzymujemy się w momencie, gdy podtablica jest posortowana. Dzięki temu można ograniczyć liczbę złączeń, a w najlepszym wyp

1adku (dane posortowane) uzyskujemy liniowy czas wykonania algorytmu."}),"\n",(0,n.jsx)(a.p,{children:"Dla zmniejszenia zajętości pamięciowej algorytmu możemy zastosować listy wiązane zamiast tablic. W\xf3wczas nie będziemy potrzebowali dodatkowej tablicy na wynik scalania. Co warto tu podkreślić, merge sort to jeden z niewielu algorytm\xf3w sortowania, kt\xf3re działają szybko na kolekcjach tego typu, ponieważ nie mamy tutaj pętli przechodzących po kolei po elementach. Jednak pamiętajmy, że zamiana tablicy na listę wiązaną tylko po to, żeby wykonać sortowanie (a potem w drugą stronę), może kosztować nas więcej niż sortowanie na tablicy."}),"\n",(0,n.jsx)(a.p,{children:"Popularnym podejściem do optymalizacji jest hybrydyzacja algorytm\xf3w. Polega ona na łączeniu r\xf3żnych algorytm\xf3w sortujących tak, aby mniejsze problemy rozwiązywać prostszymi algorytmami, kt\xf3re mogą rozwiązać je bez dodatkowego obciążania pamięci. Często łączy się sortowanie przez scalanie z sortowaniem przez wstawianie — po podziale odpowiednio małe tablice sortujemy przez wstawianie, a następnie scalamy tradycyjnym podejściem. Optymalizacje tego typu są szczeg\xf3lnie dobre przy niskopoziomowym programowaniu. Przykładowo, tiled merge sort wykorzystuje sortowanie przez wstawianie na poziomie cache procesora, więc omija zapytania do pamięci RAM, kt\xf3re zajmują więcej czasu."}),"\n",(0,n.jsxs)(a.h2,{id:"właściwości-algorytm\xf3w-sortowania-opartych-na-metodzie-dziel-i-zwyciężaj",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#właściwości-algorytm\xf3w-sortowania-opartych-na-metodzie-dziel-i-zwyciężaj",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Właściwości algorytm\xf3w sortowania opartych na metodzie „dziel i zwyciężaj”."]}),"\n",(0,n.jsx)(a.p,{children:"W celu podsumowania artykułu przyjrzyjmy się z g\xf3ry właściwościom obu przedstawionym w tym artykule algorytmom."}),"\n",(0,n.jsxs)(a.p,{children:["Jak już om\xf3wiliśmy dość szeroko, pod kątem wydajności oba algorytmy wyglądają bardzo dobrze — w przeciętnych przypadkach posiadają złożoność liniowo-logarytmiczną ",(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mi,{children:"O"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mi,{children:"log"}),(0,n.jsx)(a.mo,{children:"⁡"}),(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"O(n\\log{n})"})]})})}),(0,n.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"O"}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,n.jsxs)(a.span,{className:"mop",children:["lo",(0,n.jsx)(a.span,{style:{marginRight:"0.01389em"},children:"g"})]}),(0,n.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,n.jsx)(a.span,{className:"mord",children:(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"})}),(0,n.jsx)(a.span,{className:"mclose",children:")"})]})})]}),". Jednak o ile merge sort ma taką samą złożoność w najgorszym przypadku, to quicksort spada w złożoność kwadratową ",(0,n.jsxs)(a.span,{className:"katex",children:[(0,n.jsx)(a.span,{className:"katex-mathml",children:(0,n.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,n.jsxs)(a.semantics,{children:[(0,n.jsxs)(a.mrow,{children:[(0,n.jsx)(a.mi,{children:"O"}),(0,n.jsx)(a.mo,{stretchy:"false",children:"("}),(0,n.jsxs)(a.msup,{children:[(0,n.jsx)(a.mi,{children:"n"}),(0,n.jsx)(a.mn,{children:"2"})]}),(0,n.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,n.jsx)(a.annotation,{encoding:"application/x-tex",children:"O(n^2)"})]})})}),(0,n.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,n.jsxs)(a.span,{className:"base",children:[(0,n.jsx)(a.span,{className:"strut",style:{height:"1.064

11em",verticalAlign:"-0.25em"}}),(0,n.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"O"}),(0,n.jsx)(a.span,{className:"mopen",children:"("}),(0,n.jsxs)(a.span,{className:"mord",children:[(0,n.jsx)(a.span,{className:"mord mathnormal",children:"n"}),(0,n.jsx)(a.span,{className:"msupsub",children:(0,n.jsx)(a.span,{className:"vlist-t",children:(0,n.jsx)(a.span,{className:"vlist-r",children:(0,n.jsx)(a.span,{className:"vlist",style:{height:"0.8141em"},children:(0,n.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,n.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,n.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,n.jsx)(a.span,{className:"mord mtight",children:"2"})})]})})})})})]}),(0,n.jsx)(a.span,{className:"mclose",children:")"})]})})]}),". Z drugiej strony, sortowanie szybkie jest mniej obciążające dla pamięci komputera. Z tego powodu oba algorytmy, w dość nowoczesnych wariantach, są stosowane w praktyce. Przykładowo, w najnowszej wersji Javy (w momencie pisania artykułu jest to Java 15), do sortowania, w zależności od typu danych, są stosowane dwupiwotowy quicksort lub TimSort (jedna z hybrydowych odmian merge sort). Ten pierwszy jest stosowany do typ\xf3w prostych, natomiast drugi do złożonych obiekt\xf3w."]}),"\n",(0,n.jsx)(a.p,{children:"Nie zapominajmy o interesującej nas stabilności sortowania. Niestety, sortowanie szybkie jest niestabilne, stąd w Javie używa się je tylko do typ\xf3w prostych, gdzie stabilność jest nieistotna. Natomiast sortowanie przez scalanie jest najczęściej stabilne. Wiele zależy tu od sposobu implementacji, jednak książkowy spos\xf3b zachowuje kolejność element\xf3w."}),"\n",(0,n.jsx)(a.p,{children:"Myślę, że ostatnią rzeczą, kt\xf3rą warto dodać przy okazji tych algorytm\xf3w, jest fakt, że dzięki stosowaniu przez nie metody „dziel i zwyciężaj”, możemy z powodzeniem pisać ich r\xf3wnoległe wersje. Oznacza to, że jesteśmy w stanie tak napisać algorytm, aby z powodzeniem korzystał z wielu procesor\xf3w (czy rdzeni na jednym procesorze) a nawet wielu komputer\xf3w. Jednakże wykracza to daleko poza ramy prostego opisywania algorytm\xf3w sortowania."}),"\n",(0,n.jsxs)(a.h2,{id:"literatura",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#literatura",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Literatura"]}),"\n",(0,n.jsxs)(a.h3,{id:"pozycje-podstawowe",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#pozycje-podstawowe",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Pozycje podstawowe"]}),"\n",(0,n.jsxs)(a.ul,{children:["\n",(0,n.jsxs)(a.li,{children:["Cormen T. H., Leiserson C. E., Rivest R.L., „Quicksort — sortowanie szybkie” w ",(0,n.jsx)(a.em,{children:"Wprowadzenie do algorytm\xf3w"}),". Warszawa: Wydawnictwa Naukowo-Techniczne, 2001, s. 186-205"]}),"\n",(0,n.jsxs)(a.li,{children:["Knuth D. E., „Sortowanie przez zamienianie” w ",(0,n.jsx)(a.em,{children:"Sztuka programowania Tom 3 Sortowanie i wyszukiwanie."})," Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 110-145"]}),"\n",(0,n.jsxs)(a.li,{children:["Knuth D. E., „Sortowanie przez scalanie” w ",(0,n.jsx)(a.em,{children:"Sztuka programowania Tom 3 Sortowanie i wyszukiwanie."})," Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 166-178"]}),"\n",(0,n.jsxs)(a.li,{children:["Wirth N., „Sortowanie przez podział” w ",(0,n.jsx)(a.em,{children:"Algorytmy + struktury danych = programy."})," Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 94–100"]}),"\n",(0,n.jsxs)(a.li,{children:["Wirth N., „Sortowanie plik\xf3w sekwencyjnych” w ",(0,n.jsx)(a.em,{children:"Algorytmy + struktury danych = programy."})," Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 105–144"]}),"\n"]}),"\n",(0,n.jsxs)(a.h3,{id:"pozycje-uzupełniające",children:[(0,n.jsx)(a.a,{"aria-hidden":"true",tabIndex:"-1",href:"#pozycje-uzupełniające",children:(0,n.jsx)(a.span,{className:"icon icon-link"})}),"Pozycje uzupełniające"]}),"\n",(0,n.jsxs)(a.ul,{children:["\n",(0,n.jsxs)(a.li,{children:["Kushagra S., L\xf3pez-Ortiz A., Qiao A., Munro I. J. (2014). Multi-Pivot Quicksort: Theory and Experiments. ",(0,n.jsx)(a.em,{children:"2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX)"}),", 47-60."]}),"\n",(0,n.jsxs)(a.li,{children:["Bozidar D., Dobravec T. (2015

1). Comparison of parallel sorting algorithms. ",(0,n.jsx)(a.em,{children:"arXiv: 1511.03404"}),"."]}),"\n",(0,n.jsxs)(a.li,{children:["Class Arrays, ",(0,n.jsx)(a.a,{href:"https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/Arrays.html",children:"https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/Arrays.html"})," (ostatnio odwiedzone 23 grudnia 2020)"]}),"\n"]})]})}let x={Component:function(){let e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:{},{wrapper:a}={...(0,t.R)(),...e.components};return a?(0,n.jsx)(a,{...e,children:(0,n.jsx)(y,{...e})}):y(e)},meta:{title:"Sortowanie, cz. 5 — „dziel i zwyciężaj”",abstract:"W tym artykule przejdziemy do omawiania podejść do sortowania, kt\xf3re okazują się być bardzo wydajne i bazują na metodzie „dziel i zwyciężaj”.",firstParagraph:(0,n.jsxs)(n.Fragment,{children:["W ",(0,n.jsx)(o(),{href:"/post/sortowanie-cz-2-sortowanie-babelkowe",children:"poprzednich"})," ",(0,n.jsx)(o(),{href:"/post/sortowanie-cz-3-sortowanie-przez-wstawianie",children:"częściach"})," ",(0,n.jsx)(o(),{href:"/post/sortowanie-cz-4-sortowanie-przez-wybieranie",children:"serii"})," opisywałem, w jaki spos\xf3b tworzyć algorytmy sortowania bazujące na tym, jak na co dzień sortujemy, oraz jak podejścia te można optymalizować. Jednak, jak mogłeś się przekonać, nie są to najszybsze rozwiązania, dlatego teraz przejdziemy do omawiania tych mniej oczywistych podejść do sortowania, kt\xf3re okazują się być wydajniejsze. Om\xf3wimy algorytmy, kt\xf3re bazują na ",(0,n.jsx)(o(),{href:"/post/wyszukiwanie-w-listach",children:"metodzie „dziel i zwyciężaj”"}),"."]}),keyword:"sortowanie",categories:["Sortowanie"],tags:["sortowanie","quicksort","quick sort","merge sort","sortowanie szybkie","sortowanie przez scalanie","dziel i zwyciężaj","rekurencja","top-down","bottom-up","fibonacci","javascript","java","timsort"],slug:"sortowanie-cz-5-dziel-i-zwyciezaj",updateTime:"2021-08-17T16:36:29+00:00",publishTime:"2021-01-05T10:00:11+00:00",cover:{src:"https://lightbulb-sun.swistak.codes/prod/_next/static/media/zajac.6b23656e.jpg",height:674,width:1200,blurDataURL:"data:image/jpeg;base64,/9j/2wBDAAoKCgoKCgsMDAsPEA4QDxYUExMUFiIYGhgaGCIzICUgICUgMy03LCksNy1RQDg4QFFeT0pPXnFlZXGPiI+7u/v/2wBDAQoKCgoKCgsMDAsPEA4QDxYUExMUFiIYGhgaGCIzICUgICUgMy03LCksNy1RQDg4QFFeT0pPXnFlZXGPiI+7u/v/wgARCAAEAAgDASIAAhEBAxEB/8QAFQABAQAAAAAAAAAAAAAAAAAAAAT/xAAVAQEBAAAAAAAAAAAAAAAAAAADBf/aAAwDAQACEAMQAAAAlE5v/8QAGRABAAIDAAAAAAAAAAAAAAAAAgExABJB/9oACAEBAAE/ABtCMw1Vcz//xAAVEQEBAAAAAAAAAAAAAAAAAAAAAf/aAAgBAgEBPwCv/8QAFBEBAAAAAAAAAAAAAAAAAAAAAP/aAAgBAwEBPwB//9k=",blurWidth:8,blurHeight:4},coverCaption:(0,n.jsxs)(n.Fragment,{children:["Źr\xf3dło zdjęcia: ",(0,n.jsx)("a",{href:"https://pxhere.com/en/photo/1616213",target:"_blank",rel:"noreferrer",children:"pxhere"})]})}};var z=s(3972),w=s(37114),u=!0;function k(e){let{dateLink:a,categoryMap:s,tagsMap:t,modifiedMeta:l}=e;return(0,n.jsxs)(i.L,{metadata:l,categoryMap:s,tagsMap:t,children:[(0,n.jsxs)(z.r,{children:[(0,n.jsx)(o(),{href:"/author/tomasz-swistak",scroll:!0,prefetch:!1,children:"Tomasz Świstak"}),","," ",(0,n.jsx)(o(),{href:a,scroll:!0,prefetch:!1,children:l.localizedDate})]}),(0,n.jsx)(w.u,{english:l.english,youtube:l.youtube}),(0,n.jsx)("p",{children:x.meta.firstParagraph}),(0,n.jsx)(x.Component,{})]})}let g=k},3972:(e,a,s)=>{"use strict";s.d(a,{r:()=>l});var n=s(37876),i=s(74574),t=s.n(i);let l=e=>(0,n.jsx)("div",{className:t().postDate,...e})},13123:e=>{e.exports={square:"square_square___K2Un"}},18612:e=>{e.exports={container:"versions_container___xYgU",youtube:"versions_youtube__I154o",english:"versions_english__DVXKC"}},21236:(e,a,s)=>{(window.__NEXT_P=window.__NEXT_P||[]).push(["/post/sortowanie-cz-5-dziel-i-zwyciezaj",function(){return s(3182)}])},21839:e=>{e.exports={player:"video-player_player__1Di5E",wrapper:"video-player_wrapper__Ot1JB"}},37114:(e,a,s)=>{"use strict";s.d(a,{u:()=>o});var n=s(37876),i=s(18612),t=s.n(i),l=s(69241);let o=e=>{let{youtube:a,english:s}=e;return(0,n.jsxs)(n.Fragment,{children:[a&&(0,n.jsxs)("div",{className:(0,l.A)(t().container,t().youtube),children:[(0,n.jsx)("i",{className:"ph ph-youtube-logo"}),(0,n.jsxs)("div",{children:["Wolisz wersję wideo?"," ",(0,n.jsx)("a",{href:a,target:"_blank",rel:"noreferrer",children:"Znajdziesz ją na YouTube!"})]})]}),s&&(0,n.jsxs)("div",{className:(0,l.A)(t().container,t().english),children:[(0,n.jsx)("i",{className:"ph ph-translate"}),(0,n.jsxs)("div",{children:["Are you English-speaking?"," ",(0,n.jsx)("a",{href:s,target:"_blank",rel:"noreferrer",children:"Check out the English version!"})]})]})]})}},39735:e=>{e.exports={modal:"image_modal__J_JPn",modalOverlay:"image_modalOverlay__crqVL",modalContent:"image_modalContent__vSrem",modalContentWrapper:"image_modalContentWrapper__V53Iu",x:"image_x__SHfsk",caption:"image_caption__OeWYu",figure:"image_figure__5B39K",forceWhiteBackgroun

1d:"image_forceWhiteBackground__lFK5q",alignCenter:"image_alignCenter__FNORL",alignRight:"image_alignRight__N2hgT",alignLeft:"image_alignLeft__whSYn",image:"image_image__6_wrq",notClickable:"image_notClickable__GKFJw"}},48898:e=>{e.exports={iframe:"iframe_iframe__zOpna"}},59341:(e,a,s)=>{"use strict";s.d(a,{R:()=>o});var n=s(37876),i=s(48230),t=s.n(i);function l(e){let a=e.href,s=a&&a.startsWith("/");return a&&a.startsWith("#")?(0,n.jsx)("a",{...e}):s?(0,n.jsx)(t(),{href:a,target:"_blank",children:e.children}):(0,n.jsx)("a",{target:"_blank",rel:"noopener",...e})}function o(e){return{a:l}}},70485:(e,a,s)=>{"use strict";s.d(a,{ov:()=>y,xA:()=>v,vL:()=>A,_V:()=>p,M6:()=>C,L9:()=>k});var n=s(37876),i=s(14232),t=s(68827),l=s.n(t),o=s(69241),c=s(39735),r=s.n(c),m=s(41116),d=s.n(m);let p=e=>{let{image:a,alignCenter:s=!1,alignRight:t=!1,alignLeft:c=!1,fullSize:m=!1,maxWidth:p,caption:j=(0,n.jsx)(n.Fragment,{}),alt:h="",title:y="",radius:x="0%",forceWhiteBackground:z=!0,notClickable:w=!1,unoptimized:u=!1,noPlaceholder:k=!1}=e,[g,N]=(0,i.useState)(!1),A=()=>{N(!1)};return(0,n.jsxs)(n.Fragment,{children:[(0,n.jsxs)("figure",{className:(0,o.A)({[r().figure]:!0,[r().alignCenter]:s,[r().alignRight]:t,[r().alignLeft]:c,[r().forceWhiteBackground]:z}),style:{maxWidth:p||"100%"},children:[(0,n.jsx)(l(),{src:a,alt:h,title:y,placeholder:k?"empty":"blur",onClick:()=>{w||N(!0)},style:{borderRadius:x||"0"},unoptimized:u,className:(0,o.A)({[r().image]:!0,[r().notClickable]:w})}),(0,n.jsx)("figcaption",{className:r().caption,children:j})]}),!w&&(0,n.jsx)(d(),{isOpen:g,contentLabel:"Powiększenie zdjęcia",onRequestClose:A,shouldCloseOnOverlayClick:!0,shouldCloseOnEsc:!0,closeTimeoutMS:500,portalClassName:r().modal,className:r().modalContent,overlayClassName:r().modalOverlay,children:(0,n.jsxs)("div",{onClick:A,className:r().modalContentWrapper,children:[(0,n.jsx)("div",{className:r().modalContent,children:(0,n.jsx)(l(),{src:a,alt:h,title:y,placeholder:k?"empty":"blur",layout:"fill",objectFit:"contain",unoptimized:u})}),(0,n.jsx)("i",{className:(0,o.A)({[r().x]:!0,"ph ph-x":!0})})]})})]})};var j=s(85565),h=s.n(j);let y=e=>(0,n.jsx)("p",{className:h().center,...e});var x=s(21839),z=s.n(x),w=s(18847);let u=s.n(w)()(()=>s.e(108).then(s.bind(s,30108)),{loadableGenerated:{webpack:()=>[30108]},ssr:!1}),k=e=>{let{caption:a,height:s,width:i,url:t,...l}=e;return(0,n.jsxs)("figure",{className:(0,o.A)(r().figure,r().alignCenter),children:[(0,n.jsx)("div",{className:z().wrapper,style:{maxWidth:"".concat(i,"px"),maxHeight:"".concat(s,"px"),paddingTop:"".concat(s,"px")},children:(0,n.jsx)(u,{config:{html:{attributes:{controlsList:"nodownload"}}},height:"100%",width:"100%",src:"".concat("https://lightbulb-sun.swistak.codes/shared").concat(t),className:z().player,...l})}),(0,n.jsx)("figcaption",{className:r().caption,children:a})]})};var g=s(48898),N=s.n(g);let A=e=>{let{src:a,minHeight:s}=e;return(0,n.jsx)("iframe",{src:"".concat("https://lightbulb-sun.swistak.codes/shared").concat(a),title:a,className:N().iframe,style:{height:"".concat(s,"px")}})};var b=s(96802),f=s.n(b);let v=e=>{let{minWidth:a,children:s}=e;return(0,n.jsx)("div",{style:{gridTemplateColumns:"repeat(auto-fit, minmax(".concat(a,"px, 1fr)")},className:f().grid,children:s})};var _=s(13123),R=s.n(_);let C=e=>{let{color:a}=e;return(0,n.jsx)("span",{className:R().square,style:{backgroundColor:a}})}},74574:e=>{e.exports={postDate:"post-date_postDate__REjMS"}},85565:e=>{e.exports={center:"center_center__wX__S"}},96802:e=>{e.exports={grid:"grid_grid__DNi4o"}}},e=>{var a=a=>e(e.s=a);e.O(0,[8491,7002,2687,636,6593,8792],()=>a(21236)),_N_E=e.O()}]);