ejemplos Ordenamiento

4. Algoritmos de Ordenación4. Algoritmos de Ordenación4.1. Métodos Directos4.1. Métodos DirectosMétodo de Selección Directa: Método de Selección Directa:

En cada paso, I, coloco en la posición I el menor elemento entre En cada paso, I, coloco en la posición I el menor elemento entre I y N. Para seleccionarlo busco el mínimo.I y N. Para seleccionarlo busco el mínimo.

AlgoritmoAlgoritmo Selección (V, N) Selección (V, N) esesV: vector [1..N] de T;V: vector [1..N] de T;N n mé icoN n mé icoN: numérico;N: numérico;I, J: numérico;I, J: numérico;min: T;min: T;InicioInicioInicioInicio

Para I de 1 a N Para I de 1 a N ––1 hacer1 hacermin := I;min := I;para J de I+1 a N hacerpara J de I+1 a N hacerpara J de I+1 a N hacerpara J de I+1 a N hacer

si V(J) < V(min) entonces si V(J) < V(min) entonces min := J;min := J;

finsifinsifinsifinsiFinparaFinpara;;si min <> I entonces si min <> I entonces

intercambia (V, min, I);intercambia (V, min, I);( , , );( , , );finsifinsi

FinparaFinparaFinFin

Ejemplo de Selección directaEjemplo de Selección directaVector antes: Vector antes:

44, 55, 12, 42, 94, 18, 06, 6744, 55, 12, 42, 94, 18, 06, 67MinimoMinimo en posición 7 y tras intercambio:en posición 7 y tras intercambio:MinimoMinimo en posición 7 y tras intercambio:en posición 7 y tras intercambio:

06, 55, 12, 42, 94, 18, 44, 6706, 55, 12, 42, 94, 18, 44, 67MinimoMinimo en en posicionposicion 3 y tras intercambio:3 y tras intercambio:

06 12 55 42 94 18 44 6706 12 55 42 94 18 44 6706, 12, 55, 42, 94, 18, 44, 6706, 12, 55, 42, 94, 18, 44, 67MinimoMinimo en en posicionposicion 6 y tras intercambio:6 y tras intercambio:

06, 12, 18, 42, 94, 55, 44, 6706, 12, 18, 42, 94, 55, 44, 67Mi iMi i i ii i 4 t i t bi4 t i t biMinimoMinimo en en posicionposicion 4 y tras intercambio:4 y tras intercambio:




06, 12, 18, 42, 44, 55, 67, 9406, 12, 18, 42, 44, 55, 67, 94Vector después: Vector después: pp

06, 12, 18, 42, 44, 55, 67, 9406, 12, 18, 42, 44, 55, 67, 94

Método de la Burbuja o de Intercambio Directo: Método de la Burbuja o de Intercambio Directo: En cada paso llevo el menor a la posición I.En cada paso llevo el menor a la posición I.p pp pDesde N hasta I, un elemento, como una Desde N hasta I, un elemento, como una burbujaburbuja, se va , se va intercambiando intercambiando (flotando),(flotando), hasta que llega a la posición I el hasta que llega a la posición I el elemento menor.elemento menor.

AlgoritmoAlgoritmo Burbuja (V, N) Burbuja (V, N) esesV ecto [1 N] de TV ecto [1 N] de TV: vector [1..N] de T;V: vector [1..N] de T;N: numérico;N: numérico;I, J: numérico;I, J: numérico;InicioInicio

Para I de 2 a N hacerPara I de 2 a N hacerPara J de N a I paso Para J de N a I paso ––1 hacer1 hacerPara J de N a I paso Para J de N a I paso 1 hacer1 hacer

si V(J) < V(Jsi V(J) < V(J--1) entonces 1) entonces Intercambio (V, J, JIntercambio (V, J, J--1);1);

finsifinsi; ; FinparaFinpara;;

FinparaFinparappFinFin

Ejemplo de Intercambio directo o burbujaEjemplo de Intercambio directo o burbuja

Vector antes: Vector antes: 44, 55, 12, 42, 94, 18, 6, 6744, 55, 12, 42, 94, 18, 6, 67

Vector trasVector tras iteracioniteracion 1:1:Vector tras Vector tras iteracioniteracion 1:1:06, 44, 55, 12, 42, 94, 18, 6706, 44, 55, 12, 42, 94, 18, 67

Vector tras Vector tras iteracioniteracion 2:2:06 12 44 55 18 42 94 6706 12 44 55 18 42 94 6706, 12, 44, 55, 18, 42, 94, 6706, 12, 44, 55, 18, 42, 94, 67

Vector tras Vector tras iteracioniteracion 3:3:06, 12, 18, 44, 55, 42, 67, 9406, 12, 18, 44, 55, 42, 67, 94

V t tV t t it iit i 44Vector tras Vector tras iteracioniteracion 4:4:06, 12, 18, 42, 44, 55, 67, 9406, 12, 18, 42, 44, 55, 67, 94




Vector después:Vector después:pp6, 12, 18, 42, 44, 55, 67, 946, 12, 18, 42, 44, 55, 67, 94

Método de Inserción Directa: Método de Inserción Directa: Asumiendo que está ordenado entre 1 e I, se inserta V(I+1) en la posición Asumiendo que está ordenado entre 1 e I, se inserta V(I+1) en la posición que le corresponda. Para ello se desplazan los elementos hacia la derecha que le corresponda. Para ello se desplazan los elementos hacia la derecha q p pq p phasta que se encuentra el sitio de V(I+1) o hasta que se llega a V(1).hasta que se encuentra el sitio de V(I+1) o hasta que se llega a V(1).

AlgoritmoAlgoritmo Inserción_DirectaInserción_Directa (V,(V, N)N) esesVV:: vectorvector [[11 N]N] dede TT;;VV:: vectorvector [[11....N]N] dede TT;;NN:: numériconumérico;;I,I, JJ:: numériconumérico;;AuxAux:: TT;;InicioInicioParaPara II dede 22 aa NN hacerhacer

AuxAux ::== V(I)V(I);;JJ ::== II ––11;;JJ ::== II 11;;MientrasMientras AuxAux <=<= V(J)V(J) yy JJ >> 11 hacerhacer

V(J+V(J+11)) ::== V(J)V(J);; {Hago{Hago sitio}sitio}JJ ::== JJ –– 11;; {retrocedo}{retrocedo}

FinmientrasFinmientras;; {Aux{Aux >> V(J)V(J) OROR JJ == 11}}sisi AuxAux >> V(J)V(J) entoncesentonces

V(J+V(J+11)) ::== AuxAux;;sinosinosinosino

V(J+V(J+11)) ::== V(J)V(J);;V(J)V(J) ::== AuxAux;;

finsifinsiFinFin paraparaFinFin

Ejemplo de Inserción directaEjemplo de Inserción directaVector antes: Vector antes:

44, 55, 12, 42, 94, 18, 06, 6744, 55, 12, 42, 94, 18, 06, 67Vector trasVector tras iteracioniteracion 1:1:Vector tras Vector tras iteracioniteracion 1: 1:

44, 55, 12, 42, 94, 18, 06, 6744, 55, 12, 42, 94, 18, 06, 67Vector tras Vector tras iteracioniteracion 2: 2:

12 44 55 42 94 18 06 6712 44 55 42 94 18 06 6712, 44, 55, 42, 94, 18, 06, 6712, 44, 55, 42, 94, 18, 06, 67Vector tras Vector tras iteracioniteracion 3: 3:

12, 42, 44, 55, 94, 18, 06, 6712, 42, 44, 55, 94, 18, 06, 67V t tV t t it iit i 44Vector tras Vector tras iteracioniteracion 4: 4:




06, 12, 18, 42, 44, 55, 67, 9406, 12, 18, 42, 44, 55, 67, 94Vector después: Vector después: pp

06, 12, 18, 42, 44, 55, 67, 9406, 12, 18, 42, 44, 55, 67, 94

Documents

ejemplos Ordenamiento