b'\n_START_ARTICLE_\nKr\xc5\xabvos rikiavimo algoritmas\n_START_SECTION_\nKr\xc5\xabvos sudarymas\n_START_PARAGRAPH_\nTarkim, turime duomen\xc5\xb3 masyv\xc4\x85:_NEWLINE_Pirmiausia sukeiskime jo elementus vietomis, kad gautume:_NEWLINE_ kur  ir _NEWLINE_Grafi\xc5\xa1kai tai atrodys kaip dvejetainis medis, kurio kiekvienos vir\xc5\xa1\xc5\xabn\xc4\x97s s\xc5\xabn\xc5\xabs yra ne didesni u\xc5\xbe t\xc4\x97vus._NEWLINE_Tarkime, turime pradinius duomenis . Masyvo element\xc5\xb3 skai\xc4\x8dius . Prad\xc4\x97sime nuo pradinio elemento ._NEWLINE_Element\xc5\xb3 perk\xc4\x97limas bus vykdomas taip:_NEWLINE__NEWLINE_6 4 8 7 3 9 1 2_NEWLINE_      ^       ^_NEWLINE__NEWLINE_6 4 8 7 3 9 1 2_NEWLINE_    ^     ^ ^_NEWLINE_    |     |_NEWLINE_    <-----> _NEWLINE_6 4 9 7 3 8 1 2_NEWLINE__NEWLINE_6 4 9 7 3 8 1 2_NEWLINE_  ^   ^ ^_NEWLINE_  |   |_NEWLINE_  <--->_NEWLINE_6 7 9 4 3 8 1 2 _NEWLINE__NEWLINE_6 7 9 4 3 8 1 2_NEWLINE_^ ^ ^_NEWLINE_|   |_NEWLINE_<--->_NEWLINE_9 7 6 4 3 8 1 2_NEWLINE_    ^     ^ ^_NEWLINE_    |     |_NEWLINE_    <----->_NEWLINE_9 7 8 4 3 6 1 2_NEWLINE_Taigi gavome . \xc5\xa0iame masyve jau tenkinama m\xc5\xabs\xc5\xb3 min\xc4\x97ta s\xc4\x85lyga._NEWLINE_Tokia duomen\xc5\xb3 strukt\xc5\xabra vadinama Kr\xc5\xabva. Pirma algoritmo dalis b\xc5\xabtent ir buvo kr\xc5\xabvos sudarymas._NEWLINE_Antroji algoritmo dalis yra pats rikiavimas. Eilin\xc4\x97je iteracijoje imama kr\xc5\xabvos vir\xc5\xa1\xc5\xabn\xc4\x97 ir sukei\xc4\x8diama vietomis su paskutiniu masyvo elementu. Kadangi kr\xc5\xabvos vir\xc5\xa1\xc5\xabn\xc4\x97je visada bus did\xc5\xbeiausias elementas, tai j\xc4\xaf sukeit\xc4\x99 vietomis su paskutiniu masyvo elementu, \xc5\xbeinosime, kad did\xc5\xbeiausias masyvo elementas yra jo paskutin\xc4\x97je pozicijoje. Taip sukeit\xc4\x99 elementus vietomis, turime atkurti kr\xc5\xabv\xc4\x85. Tai padaryti paprasta, nes viet\xc4\x85 pakeit\xc4\x99s b\xc5\xabna tik vienas elementas (jis atsiduria vir\xc5\xa1\xc5\xabn\xc4\x97je). \xc5\xa0\xc4\xaf element\xc4\x85, jei jis n\xc4\x97ra did\xc5\xbeiausias, reikia perstumti keletu lygi\xc5\xb3 \xc5\xbeemiau, kol v\xc4\x97l gausime kr\xc5\xabv\xc4\x85. Tai atlik\xc4\x99, pradedame nauj\xc4\x85j\xc4\x85 iteracij\xc4\x85, tik \xc5\xa1\xc4\xaf kart\xc4\x85 jau nagrin\xc4\x97sime vienetu trumpesn\xc4\xaf masyv\xc4\x85, nes did\xc5\xbeiausias elementas, kuris anks\xc4\x8diau buvo vir\xc5\xa1\xc5\xabn\xc4\x97je, jau atsid\xc5\xabr\xc4\x97 savo vietoje ir jo nagrin\xc4\x97ti nereikia. Toki\xc5\xb3 iteracij\xc5\xb3 skai\xc4\x8dius yra ._NEWLINE_Kr\xc5\xabvos auk\xc5\xa1tis gali b\xc5\xabti rastas formule .\n_START_SECTION_\nAlgoritmo savyb\xc4\x97s\n_START_PARAGRAPH_\n\xc5\xa0is rikiavimo algoritmas n\xc4\x97ra stabilus. Pirmoje algoritmo dalyje nereik\xc4\x97s atlikti daugiau nei  palyginim\xc5\xb3, taigi pirmosios dalies sud\xc4\x97tingumas tiesinis. Antrojoje dalyje pirmasis med\xc5\xbeio elementas sukei\xc4\x8diamas su paskutiniu vietomis ir atkuriama kr\xc5\xabva. Atkuriant kr\xc5\xabv\xc4\x85, element\xc4\x85 blogiausiu atveju gali tekti perkelti i\xc5\xa1 vir\xc5\xa1\xc5\xabn\xc4\x97s \xc4\xaf apatin\xc4\xaf lyg\xc4\xaf, o, kaip min\xc4\x97ta, med\xc5\xbeio lygi\xc5\xb3 skai\xc4\x8dius randamas  (arba , jei tartume kad vir\xc5\xa1\xc5\xabn\xc4\x97 yra  lygyje). Taigi antroji lemiama algoritmo dalis yra  sud\xc4\x97tingumo. B\xc5\xabtent tokio sud\xc4\x97tingumo ir yra algoritmas. Joks rikiavimo algoritmas, naudojantis palyginimus, negali tur\xc4\x97ti ma\xc5\xbeesnio sud\xc4\x97tingumo, ta\xc4\x8diau bendru atveju u\xc5\xbe j\xc4\xaf greitesnis yra greitasis rikiavimo algoritmas. Prie\xc5\xa1ingai nei rikiavimo suliejimu, kurio sud\xc4\x97tingumas taip pat toks pats, \xc5\xa1iam metodui nereikia papildomos atminties._NEWLINE_Rikiavimo medis gali b\xc5\xabti naudojamas kaip prioritet\xc5\xb3 eil\xc4\x97.'