S'ha explicat la classificació ràpida a Java

Convenció a la meitat

Quan el nombre d'elements d'una llista és parell, reduir a la meitat la llista significa que la primera meitat literal de la llista és la primera meitat i la segona meitat literal de la llista és la segona meitat. L'element mitjà (mitjà) de tota la llista és l'últim element de la primera llista. Això significa que l’índex central és llarg / 2 - 1, ja que el recompte d’índexs comença des de zero. La longitud és el nombre d'elements de la llista. Per exemple, si el nombre d'elements és 8, la primera meitat de la llista té 4 elements i la segona meitat de la llista també té 4 elements. Està bé. Com que el recompte d’índexs comença a partir de 0, l’índex central és 3 = 8/2 - 1.

Què passa amb el cas, quan el nombre d'elements de la llista o sub-llista és imparell? Al començament, la longitud encara es divideix per 2. Per convenció, el nombre d'elements de la primera meitat d'aquesta divisió és longitud / 2 + 1/2. El recompte d’índexs comença des de zero. L’índex central ve donat per la longitud / 2 - 1/2. Això es considera el terme mitjà, per convenció. Per exemple, si el nombre d'elements d'una llista és 5, l'índex central és 2 = 5/2 - 1/2. I hi ha tres elements a la primera meitat de la llista i dos elements a la segona meitat. L’element central de tota la llista és el tercer element de l’índex, 2, que és l’índex central perquè el recompte d’índexs comença a partir de 0.

La divisió d’aquesta manera és un exemple d’aritmètica sencera.

Mitjana de tres valors

Pregunta: Quina és la mediana de la seqüència:

C B A

Solució:
Organitzeu la llista en ordre ascendent:

A B C

El terme mitjà, B, és la mediana. És la magnitud que es troba entre les altres dues magnituds.

No és així buscar la mediana en una llista. Per exemple, en una llista de 19 elements sense classificar, pot ser necessària la mediana per al primer element, l'element mitjà i l'últim element. Aquests tres valors poden no estar en ordre ascendent; per tant, cal tenir en compte els seus índexs.

Amb Classificació ràpida, es requereix la mediana per a tota la llista i les subllistes. El pseudocodi per buscar la mediana de tres valors espaiats en una llista (matriu) és:

El terme arr significa matriu. Aquest segment de codi busca la mediana i també fa una certa classificació. Aquest segment de codi sembla senzill, però pot resultar bastant confús. Per tant, presteu atenció a la següent explicació:

L'ordenació d'aquest tutorial generarà una llista on el primer valor és el valor més petit i l'últim valor és el valor més gran. Amb l’alfabet, A és inferior a Z.

Aquí, el pivot és la mediana resultant. Baix és l'índex més baix de la llista o sub-llista (no necessàriament per obtenir el valor més baix); high és l'índex més alt de la llista o sub-llista (no necessàriament per obtenir el valor més alt), i middle és l'índex convencional mitjà (no necessàriament per al valor mitjà de tota la llista).

Per tant, la mediana a obtenir es troba entre el valor de l’índex més baix, el valor de l’índex mitjà i el valor de l’índex més alt.

En el codi, primer s’obté l’índex mitjà convencional. En aquest començament, la llista no està classificada. La comparació i una certa reordenació en ordre ascendent dels tres valors es realitzaran al mateix temps. La primera sentència if compara el valor de l’índex més baix i el de l’índex mitjà. Si el de l’índex mitjà és inferior al de l’índex més baix, els dos valors canvien de posició. Això comença a ordenar i canvia la disposició dels valors a la llista o sub-llista. La segona afirmació if compara el valor de l'índex més alt i el de l'índex més baix. Si el de l’índex més alt és inferior al de l’índex més baix, els dos valors canvien de posició. Això comporta una certa classificació i canvi de la disposició dels valors a la llista o sub-llista. La tercera afirmació if compara el valor de l’índex mitjà i el de l’índex més alt. Si el de l'índex més alt és inferior a l'índex mitjà, els dos valors canvien de posició. Aquí també es pot produir alguna classificació o reordenació. Aquesta tercera condició si no és com les dues anteriors.

Al final d'aquests tres permutes, el valor mitjà dels tres valors en qüestió seria A [alt], el contingut original del qual podria haver estat canviat al segment de codi. Per exemple, considerem la seqüència no classificada:

C B A

Ja sabem que la mediana és B. Tot i això, s’hauria de demostrar. L'objectiu aquí és obtenir la mediana d'aquests tres valors mitjançant el segment de codi anterior. La primera sentència if compara B i C. Si B és menor que C, llavors les posicions de B i C s'han d'intercanviar. B és inferior a C, de manera que la nova disposició es converteix en:

B C A

Fixeu-vos que els valors de l’índex més baix i de l’índex mitjà han canviat. La segona afirmació if compara A i B. Si A és menor que B, llavors les posicions d'A i B s'han d'intercanviar. A és inferior a B, de manera que la nova disposició es converteix en:

A C B

Fixeu-vos que els valors de l’índex més alt i de l’índex més baix han canviat. La tercera afirmació if compara C i B. Si C és menor que B, llavors cal canviar les posicions de C i B. C no és inferior a B, de manera que no es produeix cap intercanvi. El nou acord es manté com l'anterior, és a dir:

A C B

B és la mediana, és a dir, A [alta], i és el pivot. Per tant, el pivot neix a l’extrem extrem de la llista o sub-llista.

La funció d'intercanvi

Una altra característica necessària per a l’ordenació ràpida és la funció d’intercanvi. La funció d'intercanvi intercanvia els valors de dues variables. El pseudocodi per a la funció d'intercanvi és:

Aquí, x i y fan referència als valors reals i no a les còpies.

L'ordenació d'aquest article produirà una llista on el primer valor és el valor més petit i l'últim valor és el valor més gran.

Contingut de l'article

• Algorisme d'ordenació ràpida
• Un pseudocodi de partició
• Il·lustració d'ordenació ràpida
• Codificació Java
• Conclusió

Algorisme d'ordenació ràpida

La forma normal d’ordenar una llista no classificada és considerar els dos primers valors. Si no estan en ordre, poseu-los en ordre. A continuació, considerem els tres primers valors. Escanegeu els dos primers per veure on encaixa el tercer valor i encaixeu-lo adequadament. A continuació, tingueu en compte els quatre primers valors. Escanegeu els tres primers valors per veure on encaixa el quart valor i ajusteu-lo adequadament. Continueu amb aquest procediment fins que s'ordeni tota la llista.

Aquest procediment, també conegut com a tipus de força bruta, en el llenguatge de programació d’ordinadors, és massa lent. L’algorisme d’ordenació ràpida inclou un procediment molt més ràpid.

Els passos per a l'algorisme quicksort són els següents:

1. Assegureu-vos que hi hagi almenys 2 números per ordenar a la llista sense classificar.
2. Obteniu un valor central estimat per a la llista, anomenat pivot. La mediana, tal com s’ha descrit anteriorment, és una forma d’obtenir el pivot. Diferents maneres vénen amb els seus avantatges i desavantatges. - Ens veiem després.
3. Particioneu la llista. Això vol dir, col·loqueu el pivot a la llista. De tal manera, tots els elements de l'esquerra són inferiors al valor de pivot i tots els elements de la dreta són majors o iguals al valor de pivot. Hi ha diferents maneres de particionar. Cada mètode de partició inclou els seus avantatges i desavantatges. Particionar és dividir en el paradigma de dividir i conquerir.
4. Repetiu els passos 1, 2 i 3 recursivament per als nous parells de subllistes que apareixen fins que s'ordena tota la llista. Això està guanyant en el paradigma de dividir i conquerir.

El pseudocodi d’ordenació ràpida és:

Un pseudocodi de partició

El pseudocodi de partició utilitzat en aquest tutorial és:

A la il·lustració d’Ordenació ràpida a continuació, s’utilitza aquest codi:

Il·lustració d'ordenació ràpida

Penseu en la següent llista (matriu) no classificada de lletres alfabètiques:

Q W E R T Y U I O P

Per inspecció, la llista ordenada és:

E I O P Q R T U W Y

Ara es demostrarà la llista ordenada, mitjançant l'algorisme i els segments de pseudocodi anteriors, de la llista no classificada:

Q W E R T Y U I O P

El primer pivot es determina a partir d’arr [0] = Q, arr [4] = T i arr [9] = P, i s’identifica com a Q i es situa a l’extrema dreta de la llista. Per tant, la llista amb qualsevol ordre de funció pivot es converteix en:

P W E R T Y U I O Q

El pivot actual és P. El procediment de pivot va fer una petita classificació i va situar P a la primera posició. La llista resultant s'ha de reordenar (particionar), de manera que tots els elements de l'esquerra tinguin un valor més petit, llavors el pivot i tots els elements de la dreta del pivot són iguals o superiors al pivot. L'ordinador no pot fer particions per inspecció. Per tant, ho fa utilitzant els índexs i l'algorisme de partició anterior.

Els índexs baix i alt ara són 0 i 9. Per tant, l’ordinador començarà escanejant des de l’índex 0 fins que arribi a un índex, el valor del qual sigui igual o superior al pivot i s’hi detingui temporalment. També escanejarà des de l'extrem superior (dret), índex 9, baixant, fins que arribi a un índex el valor del qual sigui inferior o igual al pivot i s'hi detingui temporalment. Això significa dues posicions de parada. Si i, la variable d'índex incremental, de baixa encara no és igual o superior a la variable d'índex decreixent, j de alta, es canvien aquests dos valors. En la situació actual, l'exploració des dels dos extrems es va aturar a W i O. Per tant, la llista es converteix en:

P O E R T Y U I W Q

El pivot continua sent P. L'escaneig en direccions oposades continua i s'atura en conseqüència. Si i encara no és igual o superior a j, es canvien els dos valors en què es deté l'escaneig des dels dos extrems. Aquesta vegada, l'exploració des dels dos extrems s'ha aturat a R i I. Per tant, la disposició de la llista es converteix en:

P O E I T Y U R W Q

El pivot continua sent P. L'escaneig en direccions oposades continua i s'atura en conseqüència. Si i encara no és igual o superior a j, es canvien els dos valors en què es va aturar l'exploració. Aquesta vegada, l'exploració des dels dos extrems s'ha aturat a T per a i I per a j. jo i j ens hem conegut o ens hem creuat. Per tant, no hi pot haver intercanvi. La llista continua sent la mateixa que:

P O E I T Y U R W Q

En aquest moment, el pivot, Q, s'ha de situar a la seva posició final en la classificació. Això es fa canviant arr [i] amb arr [high], canviant T i Q. La llista es converteix en:

P O E I Q Y U R W T

En aquest moment, s’ha acabat la partició per a tota la llista. El pivot = Q ha jugat el seu paper. Ara hi ha tres subllistes, que són:

P O E I Q Y U R W T

La partició és la divisió i la conquesta (classificació) en el paradigma. Q es troba en la seva posició d’ordenació correcta. Tots els elements a l'esquerra de Q són més petits que Q i tots els elements a la dreta de Q són més grans que Q. Tanmateix, la llista esquerra encara no està ordenada; i la llista correcta encara no està ordenada. S’ha de cridar tota la funció d’ordenació ràpida de manera recursiva per ordenar la subllista esquerra i la subllista dreta. Aquest record de Quick Sort ha de continuar; es desenvoluparan noves subllistes fins que tota la llista original estigui completament ordenada. Per a cada recuperació de la funció d’ordenació ràpida, primer s’atén la subllista esquerra abans d’atendre la subllista dreta corresponent. Cal obtenir un nou pivot per a cada subllista.

Per a la subllista:

P O E I

Es determina el pivot (mediana) de P, O i I. El pivot seria O. Per a aquesta sub-llista, i relacionat amb la llista completa, el nou arr [baix] és arr [0] i el nou arr [alt] és el darrer arr [i-1] = arr [ 4-1] = arr [3], on i és l'índex de pivot final de la partició anterior. Després de cridar la funció pivot (), el nou valor pivot, pivot = O. No confongueu entre la funció pivot i el valor pivot. La funció de pivot pot fer una petita classificació i col·locar el pivot a l'extrem dret de la sub-llista. Aquesta sub-llista esdevé,

I P E O

Amb aquest esquema, el pivot sempre acaba a l'extrem dret de la llista o sub-llista després de la seva crida de funció. L’escaneig des dels dos extrems comença des de arr [0] i arr [3] fins que i i j es troben o creuen. La comparació es fa amb pivot = O. Les primeres parades són a P i E. Es canvien i la nova sub-llista es converteix en:

I E P O

L’escaneig des dels dos extrems continua i les noves parades es troben a P per a i a E per a j. Ara jo i j ens hem trobat o creuat. Per tant, la sub-llista continua sent la mateixa que:

I E P O

El particionament d'una sub-llista o llista finalitza quan el pivot s'ha posat a la seva posició final. Per tant, els nous valors per arr [i] i arr [high] s’intercanvien. És a dir, P i O s’intercanvien. La nova subllista es converteix en:

I E O P

O és ara a la seva posició final per a tota la llista. El seu paper com a pivot ha acabat. Actualment, la sub-llista està particionada en tres llistes més, que són:

I E O P

En aquest moment, s’ha de trucar a Classificació ràpida de la primera llista secundària dreta. Tot i això, no es cridarà. En lloc d'això, s'anotarà i es reservarà, per anomenar-se més endavant. A mesura que s’executaven les sentències de la funció de particionament, des de la part superior de la funció, és l’Ordenació ràpida de la sub-llista esquerra la que s’ha de cridar ara (després que s’hagi cridat pivot ()). Es cridarà a la llista:

Jo E

Començarà buscant la mediana de I i E. Aquí, arr [baix] = I, arr [mitja] = I i arr [alt] = E. Per tant, la mediana, pivot, hauria de ser determinada per l'algorisme de pivot com , I. Tanmateix, el pseudocodi pivot anterior determinarà el pivot com a E. Aquest error es produeix aquí perquè el pseudocodi anterior està destinat a tres elements i no a dos. A la implementació següent, hi ha algun ajust al codi. La sub-llista esdevé,

I jo

El pivot sempre acaba a l'extrem dret de la llista o sub-llista després de la trucada de funció. L’escaneig des dels dos extrems comença des de arr [0] i arr [1] exclusiu fins que i i j es troben o creuen. La comparació es fa amb pivot = I. Les primeres i úniques parades són a I i E: a I per a i a E per a j. Ara jo i j ens hem trobat o creuat. Per tant, la sub-llista continua sent la mateixa que:

I jo

El particionament d'una sub-llista o llista finalitza quan el pivot s'ha posat a la seva posició final. Per tant, els nous valors per arr [i] i arr [high] s’intercanvien. Aquí passa que arr [i] = I i arr [alt] = I. Per tant, es canvia el mateix valor amb ell mateix. La nova subllista es converteix en:

I jo

Ara estic a la seva posició final per a tota la llista. El seu paper com a pivot ha acabat. La sub-llista ara està particionada en dues llistes més, que són,

I jo

Ara, els pivots fins ara han estat Q, O i I. Els pivots acaben a les seves posicions finals. Una sub-llista d’un sol element, com la P anterior, també acaba a la seva posició final.

En aquest moment, la primera sub-llista esquerra s'ha ordenat completament. I el procediment de classificació es troba ara a:

E I O P Q Y U R W T

La primera sub-llista dreta:

Y U R W T

encara s’ha d’ordenar.

Conquistant la primera llista secundària dreta
Recordeu que la trucada d'ordenació ràpida per a la primera sub-llista dreta es va observar i reservar en lloc d'executar-la. En aquest moment, s’executarà. Així, el nou arr [low] = arr [5] = arr [QPivotIndex + 1], i el nou arr [high] continua sent arr [9]. Aquí es produirà un conjunt d'activitats similars a la primera subllista esquerra. I aquesta primera sub-llista dreta s’ordena a:

R T U W Y

I la llista original sense classificar s'ha ordenat a:

E I O P Q R T U W Y

Codificació Java

Posar l'algorisme a Java és només posar tots els segments de pseudocodi anteriors en mètodes Java d'una classe. No oblideu que cal que hi hagi un mètode main () a la classe que anomeni la funció quicksort () amb la matriu sense classificar.

El mètode pivot ()

El mètode Java pivot () que retorna el valor, pivot, ha de ser:

El mètode swap ()

El mètode swap () hauria de ser:

El mètode quicksort ()

El mètode quicksort () hauria de ser:

El mètode partició ()

El mètode partition () ha de ser:

El mètode principal ()

El mètode principal () pot ser:

Tots els mètodes anteriors es poden classificar en una sola classe.

Conclusió

Quick Sort és un algorisme d’ordenació que utilitza el paradigma de dividir i conquerir. Comença dividint una llista no classificada en dues o tres subllistes. En aquest tutorial, Sort ràpida ha dividit una llista en tres subllistes: una subllista esquerra, una llista central d’un sol element i una subllista dreta. La conquesta a l’ordenació ràpida consisteix en dividir una llista o sub-llista mentre s’ordena, mitjançant un valor pivot. Aquest tutorial ha explicat una implementació de Quick Sort en el llenguatge informàtic Java.

Sobre l'autor

Chrysanthus Forcha

Descobridor de la integració matemàtica a partir dels primers principis i sèries relacionades. Màster universitari en educació tècnica, especialitat en electrònica i programari informàtic. BSc Electronics. També tinc coneixements i experiència a nivell de màster en informàtica i telecomunicacions. De 20.000 escriptors, vaig ser el 37è millor escriptor de devarticles.com. Fa més de deu anys que treballo en aquests camps.

POSTS DE PUNTS DE LINUX RELACIONATS

• Comparació de cadenes a Java
• Com utilitzar HashMap a Java
• S'ha explicat la classificació ràpida a Java
• Traversal de reserva de l'arbre binari a Java
• S'ha explicat la combinació d'ordenacions a Java
• Com utilitzar Scanner a Java
• Java escriu al fitxer