Content

• Gràfic de comparació
• Definició de Quick Sort
• Definició de Merge Sort
• Conclusió

Els algorismes d’ordenació ràpida d’ordenació i fusió es basen en l’algoritme de divisió i conquesta que funciona de manera bastant similar. La diferència prèvia entre l’ordenació ràpida i la fusió és que en l’ordenació ràpida l’element pivot s’utilitza per a l’ordenació. D'altra banda, l'ordenació de combinació no utilitza cap element pivot per realitzar l'ordenació.

Les dues tècniques d’ordenació, ordenació ràpida i ordenació de combinació es basen en el mètode de divisió i conquesta en què s’elabora el conjunt d’elements i que després es combinen després d’una reordenació. L’ordenació ràpida generalment requereix més comparacions que l’ordenació de combinació per ordenar un conjunt gran d’elements.

1. 1. Gràfic de comparació
   2. Definició
   3. Diferències claus
   4. Conclusió

Gràfic de comparació

Bases per a la comparació	Classificació ràpida	Sort de fusió
Partició dels elements de la matriu	La divisió d’una llista d’elements no necessàriament es divideix en la meitat.	La matriu es divideix sempre en la meitat (n / 2).
Peor complexitat dels casos	O (n2)	O (n log n)
Funciona bé	Matriu més petita	Funciona bé en qualsevol tipus de matriu.
Velocitat	Més ràpid que altres algorismes d’ordenació per a conjunts de dades petites.	Velocitat consistent en tot tipus de conjunts de dades.
Necessitat addicional d’espai d’emmagatzematge	Menys	Més
Eficiència	Ineficaç per a matrius més grans.	Més eficient.
Mètode d’ordenació	Intern	Extern

Definició de Quick Sort

Classificació ràpida s'utilitza de manera perversiva l'algorisme d'ordenació ja que és ràpid per a les matrius curtes. El conjunt dels elements es divideix en parts repetidament fins que no és possible dividir-lo més. El tipus ràpid també es coneix com a tipus d’intercanvi de particions. Utilitza un element clau (conegut com a pivot) per particionar els elements. Una partició conté aquells elements que són més petits que l'element clau. Una altra partició conté aquells elements que són superiors a l'element clau. Els elements estan ordenats recursivament.

Suposem que A és una matriu A, A, A, …… .., A de n nombres que s’han d’ordenar. L’algoritme d’ordenació ràpida comprèn els passos següents.

1. El primer element o qualsevol element aleatori seleccionat com a clau, assumiu la clau = A (1).
2. El punter “baix” es col·loca al segon i el punter “amunt” es situa al darrer element de la matriu, és a dir, baix = 2 i amunt = n;
3. Incrementar el punter “baix” per una posició fins a la tecla (A>).
4. Decretar constantment el punter "amunt" per una posició fins a (tecla A <=).
5. Si és superior a l'intercanvi A baix amb A.
6. Repetiu el pas 3,4 i 5 fins que falla la condició del pas 5 (és a dir, amunt <= baix) i, a continuació, intercanvieu A amb la clau.
7. Si els elements de la clau de l'esquerra són menors que la clau i els elements de la clau són majors que la clau, la matriu es repartirà en dos subreys.
8. El procediment anterior s’aplica repetidament a les subarracles fins que s’ordena tota la matriu.

   

   
   

Avantatges i inconvenients

Té un bon comportament mitjà de casos. La complexitat del temps de funcionament de l’ordenació ràpida és bona, ja que és més ràpida que els algoritmes com ara el tipus de bombolles, el tipus d’inserció i el tipus de selecció. Tot i això, és complex i molt recursiu, per la qual cosa no és adequat per a grans matrius.

Definició de Merge Sort

Sort de fusió és un algorisme que també es basa en l'estratègia de divisió i conquesta. Els elements es divideixen en subreys (n / 2) una i altra vegada fins que només queda un element, cosa que redueix significativament el temps d’ordenació. Utilitza emmagatzematge addicional per emmagatzemar la matriu auxiliar. Unió de combinacions utilitza tres matrius en què es fan servir dues per emmagatzemar cada meitat i la tercera s'utilitza per emmagatzemar la llista classificada final. Tot seguit, cada matriu s'ordena de manera recursiva. Finalment, els subarrays es fusionen per convertir-lo en la mida d'element de la matriu. La llista sempre es divideix en només la meitat (n / 2) diferent per ordenar ràpidament.

Sigui A la matriu de n nombre d’elements que s’han d’ordenar A, A, ………, A. L’ordenació de combinació segueix els passos donats.

1. Dividiu la matriu A en un sub-array ordenat aproximadament per 2, el que significa que els elements de les subrejades (A, A), (A, A), (A, A), (A, A) estar ordenat.
2. Combina cada parell per obtenir la llista de subàrees ordenades de mida 4; els elements de les subordres també estan ordenats, (A, A, A, A), ......, (A, A, A, A), ......, (A, A, A, A).
3. El pas 2 es realitza repetidament fins que només hi hagi un conjunt ordenat de mida n.

   

Avantatges i inconvenients

L’algoritme d’ordenació de combinació funciona de la mateixa manera i precisió independentment del nombre d’elements implicats en l’ordenació. Funciona bé fins i tot amb el gran conjunt de dades. Tanmateix, consumeix una part més gran de memòria.

1. En el tipus de fusió, la matriu s'ha de dividir en dues meitats (és a dir, n / 2). En contraposició, de manera ràpida, no hi ha cap obligació de dividir la llista en elements iguals.
2. La pitjor complexitat dels casos de tipus ràpid és O (n²) ja que es necessiten moltes més comparacions en el pitjor estat. En canvi, els tipus de combinació tenen el mateix pitjor cas i complexitat de casos mitjana, és a dir O (n log n).
3. El tipus de fusió pot funcionar bé en qualsevol tipus de conjunts de dades, siguin grans o petites. Per contra, l’ordenació ràpida no pot funcionar bé amb grans conjunts de dades.
4. L’ordenació ràpida és més ràpida que l’ordenació combinada en alguns casos, com per exemple en conjunts de dades petits.
5. La classificació de fusions requereix espai de memòria addicional per emmagatzemar les matrius auxiliars. D’altra banda, l’ordenació ràpida no requereix gaire espai per a emmagatzematge addicional.
6. El tipus de fusió és més eficient que l’ordenació ràpida.
7. L’ordenació ràpida és un mètode d’ordenació intern on s’ajusten les dades que s’han d’ordenar alhora a la memòria principal. Per contra, l’ordenació de combinació és un mètode d’ordenació extern en el qual les dades que s’han d’ordenar no poden allotjar-se a la memòria alhora i algunes s’han de conservar a la memòria auxiliar.

Conclusió

L’ordenació ràpida són casos més ràpids, però és ineficient en algunes situacions i també realitza moltes comparacions en comparació amb el tipus de fusió. Tot i que el tipus de fusió requereix menys comparació, necessita un espai de memòria addicional de 0 (n) per emmagatzemar la matriu addicional mentre que l’ordenació ràpida necessita espai d’O (log n).