Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice
Acasa » scoala » informatica
Sortarea prin insertie cu diminuarea incrementului

Sortarea prin insertie cu diminuarea incrementului


Sortarea prin insertie cu diminuarea incrementului

    • La inceput, toate articolele care sunt despartite prin cate 4 pozitii, sunt grupate si sortate separat prin metoda insertiei.
      • Acest proces se numeste sortare-4.
      • In exemplul din fig.324, unde se sorteaza 8 elemente, s-au format 4 grupe de elemente separate prin cate 4 pozitii.
    • Dupa aceasta prima trecere, se formeaza grupuri in care elementele sunt separate prin cate doua pozitii si din nou sunt sortate prin insertie.
      • Acest proces se numeste sortare-2.
    • In final, la cea de-a treia trecere, elementele sunt sortate obisnuit (sortare-1).
      • Se precizeaza faptul ca fiecare k-sortare este de fapt o sortare prin insertie la care pasul este k  (nu 1 ca la insertia normala).




34 65 12 22 83 18 04 67

sortare-4



34 18 04 22 83 65 12 67

sortare-2


04 18 12 22 34 65 83 67


sortare-1

04 12 18 22 34 65 67 83


Fig. 3.2.4. Sortare prin insertie cu diminuarea incrementului

  • Desi la prima vedere aceasta metoda care presupune cateva treceri asupra tuturor elementelor, nu pare foarte performanta, totusi la o analiza mai atenta, fiecare trecere realizeaza relativ putine modificari ale pozitiilor elementelor.
  • Este evident ca metoda conduce la sortarea elementelor si ca fiecare pas profita de cei anteriori (fiecare sortare-i combina grupuri deja sortate-j).
  • Este posibila orice secventa de incrementi atata timp cat ultimul este egal cu unitatea: in cel mai rau caz in acest pas se va realiza in intregime procesul de sortare.
  • Este mai putin evident, dar practica demonstreaza ca o secventa de incrementi descrescatori care nu sunt puteri ale lui 2 asigura o eficienta superioara procesului de sortare.
  • Analiza metodei shellsort. Analiza acestui algoritm pune probleme deosebite din punct de vedere matematic, multe din ele inca nerezolvate.
  • In particular, nu se cunoaste nici macar secventa de incrementi cea mai potrivita. Ceea ce este deosebit de interesant este faptul ca incrementii nu trebuie sa fie unii multiplii altora.
  • Pentru o eficienta sporita a sortarii este de dorit ca intre diferitele lanturi de parcurgere sa aiba loc cat mai multe interactiuni.
  • De asemenea este valabila urmatoarea teorema pe care de fapt se bazeaza metoda.
    • Daca o secventa sortata-k este sortata-i ea ramane si sortata-k.
    • Cu alte cuvinte, procesul de sortare cu diminuarea incrementului este cumulativ.


Politica de confidentialitate


creeaza.com logo mic.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.