interclasare
3
Sortarea prin interclasare. Algoritmul de sortare prin interclasare se bazează pe următoarea idee: pentru a sorta un vector cu n elemente îl împărţim în doi vectori care, odată sortaţi, se interclasează. Conform strategiei Divide et Impera, problema este descompusă în alte două subprobleme de acelasi tip si, după rezolvarea lor, rezultatele se combină (în particular se interclasează). Descompunerea unui vector în alţi doi vectori care urmează a fi sortaţi are loc până când avem de sortat vectori de una sau două componente.
-
Upload
stevebenson -
Category
Documents
-
view
212 -
download
0
description
Sortare prin interclasare
Transcript of interclasare
-
Sortarea prin interclasare.
Algoritmul de sortare prin interclasare se bazeaz pe urmtoarea idee: pentru a sorta un vector cu n elemente l mprim n doi vectori care, odat sortai, se interclaseaz. Conform strategiei Divide et Impera, problema este descompus n alte dou subprobleme de acelasi tip si, dup rezolvarea lor, rezultatele se combin (n particular se interclaseaz). Descompunerea unui vector n ali doi vectori care urmeaz a fi sortai are loc pn cnd avem de sortat vectori de una sau dou componente.
-
382743382910
3827
82910
3827433
433
10
829
43
38
82
10
27
3
9
38
27
43
82
10
3
9
3
27
38
43
9
10
82
3
27
38
43
9
10
82
- Algoritm descris n pseudocod:Sort(p,q,A);dac A[p]>A[q] atunci interschimba A[p]A[q]sfSortInterc(p,q,m,A)ip;jm+1;k0;ct timp i