A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Triedenie priamym vkladaním (anglicky: Insert Sort) je jednoduchý triediaci algoritmus usporadúvajúci prvky poľa zloženého z celých, reálnych čísel a reťazcov. Patrí medzi porovnávacie (komparačné) a asociatívne algoritmy.
Vlastnosti
Insert Sort nepatrí medzi výhodné algoritmy triedenia, nakoľko pracuje s operačnou zložitosťou O(n²). Oproti vylepšeným triediacim algoritmom ako napr. Quicksort, triedenie haldou alebo Dobosiewiczovo triedenie je málo efektívny. Ale výsledkom jeho triedenia je stabilné pole (čiže zachová relatívne usporiadanie duplicitných kľúčov triedených prvkov). Insert Sort sa vyznačuje taktiež jednoduchou realizáciou a vhodný je hlavne na takmer usporiadané pole s malým počtom prvkov(pod 2 000). Pri usporadúvaní už usporiadaného poľa je Insert Sort dokonca rýchlejší ako Quicksort, pretože každý nový prvok porovnáva len s posledným v danom poli.
Algoritmus triedenia
Algoritmus Insert Sortu vyberá postupne po jednom prvku z poľa a porovnáva ho s ostatnými prvkami, pričom sa tento krok opakuje počet prvkov - 1 krát. Keď narazí na menšiu hodnotu, nájdený prvok sa presunie za vybraný prvok. Týmto sa pole rozdelí na usporiadanú (ľavá) a neusporiadanú (pravá) časť. Vždy sa vkladajú prvky len jednosmerne a to z neusporiadanej časti do usporiadanej. Takto sa vzostupne usporiada celé pole prvkov. Vhodnou modifikáciou podmienok algoritmu možno dosiahnuť i zostupné usporiadanie.
Hodnoty
Pri vhodnom vstupnom poli je minimálny počet porovnaní n-1 a presunov 2(n - 1). Najhorší prípad nastane pri totálne neusporiadanom poli s veľkým množstvom prvkov, kedy počet porovnaní narastie až na (n² + n - 2)/2 a počet presunov na (n² + 3n - 4)/2. Priamo úmerne narastá tiež náročnosť na veľkosť operačnej pamäte počítača.
Externé odkazy
- Algoritmy usporadúvania
- Insert Sort v praxi Archivované 2008-08-09 na Wayback Machine
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk