El ordenamiento Shell és un alogoritme d'ordenació. El mètode es denomina Shell en honor del seu inventor Donald Shell. La Seva implementació original, requereix O(n2) comparacions e intercanvis en el pitjor cas. Un canvi menor presentat en el llibre de V. Pratt produeix una implementació amb un rendiment de O(n log2 n) en el pitjor cas.
Això és millor que les O(n2) comparacions requerides por algoritmes simples però pitjor que el optim O(n log n). Encara que és fàcil crear un sentit intuitiu de com funciona aquest algoritme, es molt difícil analitzar el seu temps de execució. El Shell sort es una generalització del ordenament por inserció, tenint en compta dos observacions: 1.
El ordenament per inserció és eficient si la entrada esta "casi ordenada". 2. El ordenament per inserció es ineficient, en general, perquè mou els valors nomes una posició cada vegada. El algoritme Shell sort millora la ordenació per inserció comparant elements separats per un espai de varies posicions.
Això permetre que un element faci "passos més grans cap a la seva posició esperada. Els passos múltiples sobre les dades es fan amb grandàries d'espai cada vegada més petites. L' últim pas del Shell sort és un simple ordenament per inserció, però llavors, ja hi és garanteix que les dades del vector son casi ordenades.
Per exemple, considere una llista de números com [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comencem amb una grandària de pas de 5, podríem visualitzar això dividint la llista de números en una taula amb 5 columnes. això quedaria així:
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
arribats a aquest pas, ara fem una ordenació de cada columna (no fila!!!)
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
Quan ho tenim de nou com una fila: 10, 14,73,25,23,13,27,94,33,39,25,59,94,65,82,45 es veu com s'han mogut els números aquesta llista es de nou ordenada amb un espai de tres posicions i després amb un espai d'una posició.
10,14,73 25,23,13 27,94,33, 39,25,59, 94,65,82 45
10,14,13 25,23,33 27,25,59 39,65,73 45,94,82 94
10,14,13,25,23,33,27,25,59,39,65,73,45,94,82,94 i finalment es posa en ordre mitjançant la ordenació simple.
Mètode Quick short l' algoritme treballa de la següent forma: selecciona un element del llistat de elements i l'anomena pivot. Resituar els altres elements del llistat a cada costat del pivot, de manera que a un costat queden tots els menors que ell, i a l'altre els majors.
Els elements iguals al pivot podran ser posats tant a la seva dreta com a l'esquerra , dependent de la implementació desitjada.
En aquest moment, el pivot ocupa exactament el lloc que li correspon en la llista ordenada. La llista queda separada en dos subllistes, una formada per els elements a ll'esquerra del pivot, i altre per els elements a la seva dreta. Repetir aquest proces de forma recursiva per cada subllista mentres tinguin més d'un element.
Una vegada terminat aquest proces els elements estaran ordenats. Com es pot suposar, la eficiència del algoritme depèn de la posició en la que termina el pivot seleccionat. En el millor cas, el pivot termina en el centre de la llista, dividint-la en dos subllistes de mateix grandària. En aquest cas, l'ordre de complexitat del algoritme és O(n·log n).
En el pitjor cas, el pivot termina en un extrem de la llista. L'orde de complexitat del algoritme és llavors de O(n²). El pitjor cas depèn de la implementació del algoritme, encara que habitualment passa en llistes que estan ordenades, o casi ordenades.
Però principalment depèn del pivot, si por exemple l' algoritme implementat toma com pivot sempre el primer element del array. I l'array que li passem esta ordenat, sempre va a generar a la seva esquerra un array buit, que es ineficient. En el caso ”promedio”, l'orden 0és O(n·log n). No es estrany, doncs, la majoria d'optimitzacions que s' apliquen al algoritme es centren en la elecció del pivot.
Exemple En el següent exemple es marquen el pivot e índex , “i” i “ j” amb les lletres “p,” “i” i “j” respectivament. Comencem amb la llista completa. El element pivot será el 4:
5 - 3 - 7 - 6 - 2 - 1 - 4 p
Comparem amb el 5 per l'esquerra i l' 1 per la dreta. 5 - 3 - 7 - 6 - 2 - 1 - 4 i j p
5 és major que 4 i 1 és menor. Intercanviem: 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p
avancem per la dreta i l'esquerra: 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p
3 és menor que 4 , avancem per l'esquerra . 2 és menor que 4, ho mantendrem ahi. 1 - 3 - 7 - 6 - 2 - 5 - 4 i j p
7 és major que 4 i menor de 2,intercanviem: 1 - 3 - 2 - 6 - 7 - 5 - 4 i j p
avancem per els dos costats: 1 - 3 - 2 - 6 - 7 - 5 - 4 iyj p
En aquest moment termina el cicle principal, perque els índex es creuan. Ara intercanviem llista[i] amb llista[sup] (passos 16-18): 1 - 3 - 2 - 4 - 7 - 5 - 6 p
Apliquem a la subllista de l'esquerra (índices 0 - 2). Tenim el següent 1 - 3 - 2
1 és menor que 2: avancem per l'esquerra. 3 és major: avancem per la dreta. Com s'intercanviam els índex termina el cicles. S'intercanvia llista[i] amb llista[sup]: 1 - 2 - 3
El mateix procediment s'aplicara a l'altre subllista. Al finalitzar i unir totes les subllistas queda la llista inicial ordenada en forma ascendent. 1 - 2 - 3 - 4 - 5 - 6 - 7
No hay comentarios:
Publicar un comentario