Metodos De Ordenamiento

Métodos de ordenamiento

Métodos de ordenamiento Shell Sort

Es un método que se basa en un algoritmo de inserción, que consiste en dividir el vector en subconjuntos comparándolos

Ejemplo grafico

(Los números se comparan con el color correspondiente) OJO

Tenemos un vector de 8 elementos, la distancia se saca dividiendo en numero de elementos entre 2. 8/2=4

La distancia a comparar es de 4

(a) 8 7 5 2 1 4 3 6.

8<1= NO (intercambian)

7<4= NO (intercambian)

5<3= NO (intercambian)

2<6= SI (intercambian)

(b) 1 4 3 2 8 7 5 6

(Repetimos el mismo procedimiento de (a) , Pero al no haber un intercambio la distancia disminuye).

4/2=2

La distancia a comparar es de 2

(c) 1 4 3 2 8 7 5 6. (

1<3= SI

4<2= NO

3<8= SI

2<7= SI

8<5= NO

7<6= NO

(d) 1 2 3 4 5 6 7 8. (ya están ordenados ya no necesitan ningún intercambio).

Método de ordenamiento Quick Sort

Basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional.

Ejemplo grafico:

(Primero se debe seleccionar el pivote)

Pivote (Elemento el cual permitirá compararse con los elementos que estén dentro de un vector)

Pivote: 5

(a) 5 3 1 6 4 7 2 ( vector de 7 elementos)

(b) 3 1 6 4 7 2

5 < 2= SI (por lo tanto se intercambian)

(c) 2 3 1 6 4 7

5 > 3 = NO (por lo tanto se queda en el lado izquierdo)

(d) 2 3 1 6 4 7

5 < 7 = NO (por lo tanto se queda en el lado derecho)

(e) 2 3 1 6 4 7

5 > 1 = NO (por lo tanto se queda en el lado izquierdo)

(f) 2 3 1 6 4 7

5 > 4 = SI (por lo tanto se intercambian, pero al ver que no hay espacio se deja alli)

(g) 2 3 1 6 4 7

5 > 4 = SI (por lo tanto se queda en el lado izquierdo)

(h) 2 3 1 4 5 6 7 ( subimos el pivote) ( el lado derecho esta ordenado)

(i) 2 3 1 4 5 6 7( SOLO el lado izquierdo se realizara el mismo procedimiento) (pivote=2)

(j) 3 1 4 5 6 7

2>1= NO ( se cola en el lado izquierdo)

(k) 1 3 4 5 6 7

2 > 3= si ( se coloca en el lado derecho).

(l) 1 2 3 4 5 6 7 ( solución )

Búsqueda binaria

Datos de entrada:

vec: vector en el que se desea buscar el dato

tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

dato: elemento que se quiere buscar.

Variables

centro: subíndice central del intervalo

inf: límite inferior del intervalo

sup: límite superior del intervalo

• C

int busquedaBinaria(int vector[], int n, int dato)

{

int centro,inf=0,sup=n-1;

while(inf<=sup){

centro=(sup+inf)/2;

if(vector[centro]==dato) return centro;

else if(dato < vector [centro] ){

sup=centro-1;

}

else {

inf=centro+1;

}

}

return -1;

}

Búsqueda secuencial:

Datos de entrada:

vec: vector en el que se desea buscar el dato

tam: tamaño del vector. Los subíndices válidos van desde 0

...