Tööd tehakse alati samapalju. Sorteerimine kuhjaga – kahendkuhi (kahendpuu kujuline andmestruktuur, realiseeritakse massiivi abil). Kuhjas olevad elemendid teatud reegli abil järjestatud, vastavalt kuhja omadusele. Iga tipp on üks element kuhjas. Puu juur on kõige suurem element indeksiga 1. Keerukus O(n log n). Tugev külg – ei vaja lisamälu. Nõrk külg – sorteeritud massiiv hakkab tekkima massiivi lõpust. Meetodi kirjeldus: arvudemassiivist moodustatakse väärtuste ümberpaigutamise teel kuhi ning sorteeritakse vastava algoritmiga. Shell’i sorteerimine – väheneva sammu meetod. Sammu 1) võrreldakse ühe sammu kaugusel olevaid kirjeid, kui eespool olev kirje on suurem, siis toimub vahetus 2) korratakse, kuni pole vaja enam ühtegi sammu teha 3) vähendatakse sammu. Keerukus O(n2). Tugev külg – kiirem tööaeg, töötab paremini osaliselt sorteeritud massiivil. Nõrk külg – sammu valik.
11. Sorteerimisülesanne. Sorteermine kuhjaga (Heaps.), lisamissorteerimine (Insertion s.), mestimisega sorteerimine (Merge s.), loendamissorteerimine (Counting s.). Meetodite keerukus, tugevad ja nõrgad küljed. Mõtle ka näitele algoritmi töö selgitamiseks. 11.1 Sorteerimine kuhjaga (Heaps sort) • Meetod kasutab kahendkuhja • Suuremat vajadust lisamälu järele ei ole. • Sorteerimine toimub kahes etapis: 1. Arvudemassiivist moodustatakse väärtuste ümberpaigutamise teel kuhi. 2. Kuhi sorteeritakse vastava algoritmiga. o Kui massiivist on sel viisil kuhi moodustatud, järgneb sorteerimine: 1. Tipmine element võetakse kuhjast ära (tema on kõige suurem), selleks vahetatakse 1. ja viimane element ning kuhja suurust vähendatakse ühe võrra. Algoritmid ja andmestruktuurid 2015 26 2
annaabi.ee 
