ygghhgh

Quick_sort (cont.)

4.2. Métodos de ordenación
logarítmicos como ejemplos de
aplicación de Divide y Vencerás

Esto nos lleva a realizar una partición:
Tomamos un elemento X de un vector.Buscamos dejar los elementos mayores que X a su
derecha y los elementos menores a su izquierda.
Se inspecciona a la izquierda de X hasta que se
encuentra un ai > x, y se inspecciona a la derecha
hastaque se encuentre un aj < x. Entonces se
intercambian.
Se procede de la misma manera hasta que ambos
recorridos se encuentren (aproximadamente en la
mitad del vector).
Ejemplo: Partición delsiguiente vector

4.2.1. Ordenación rápida o quick_sort()
No será necesario hacer recombinación
de las soluciones parciales
Basado en el principio de intercambio, pero
mejorado:
Los intercambiosson más efectivos cuanta mayor
sea la distancia entre elementos.
Supongamos que tenemos n elementos en orden
inverso al que deben tener.
Se puede ordenar con n/2 cambios: 1 y n, 2 y n-1,
3 y n-2,...
Pero esto sólo es posible si se conoce que están
exactamente en su orden inverso.

14

27

15

100

7

42

14

8

27

15

100

7

42

14

1

8

8

7

15100

27

42

2

Quick_sort (cont.)

Quick_sort (cont.)

Algoritmo Partición (V, inf, sup) es
V: Vector [1..100] de T; {par. dato-resultado}
Inf, Sup: numérico; {par. dato}
I, J:Numérico; {var. internas}
X: T;
Inicio
I: = Inf;
J := Sup;
X := V((Inf + Sup) div 2);
Repetir
mientras V(I) < X hacer
I := I + 1;
fin mientras;
mientras V(J) > X hacer
J := J - 1;
fin mientras;si I J;

Algoritmo Partición (V, inf, sup, I, J) es
V: Vector [1..100] de T; {par. dato-resultado}
Inf, Sup: numérico; {par. dato}
I, J: Numérico; {par. resultado: necesarios
quick_sort}
X: T;Inicio
I: = Inf;
J := Sup;
X := V((Inf + Sup) div 2);
Repetir
mientras V(I) < X hacer
I := I + 1;
fin mientras;
mientras V(J) > X hacer
J := J - 1;
fin mientras;
si I J;

Fin

para...