lab de algoritmos( metodos de ordenamiento)

un metodo de ordenamiento es la operacion realizada para acomodar u ordenar un grupo de datos ya sean numericos alfabeticos o alfanumericos su proposito principal es el de facilitar una busqueda de los miembros del grupo se combiene usar un metodo de ordenamiento cuando se necesita realizar un gran numero de busquedas dentro de el grupo existen dos metodos de ordenamiento los cuales son internos y externos los internos son a los que los valores a ordenar estan en la memoria principal por lo cual se asume que el tiempo de acceso a cualquier elemento es el mismo.
y los externos son los que sus valores estan en una memoria secundaria por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la ultima posición accesada algunos tipos de ordenamiento son:

insercion directa este metodo consiste en acomodar los elementos del arreglo comparandolos desde la parte izqierda de dos en dos y si el de la posicion mas adelantada es mas pequeño se produce un intercambio y asi sucesivamente pondre un ejemplo para que sea mas entendible

A [12,23,43,1,4,56,32,60]

para implemetar el metodo comparamos las primeras dos casillas de izquierda a derecha
A[2]<A[1](23<12)=no se intercambian por que el menor sigue estando en la izquierda
A[3]<A[2](43<23)=no se intercambian por que el menor esta en el lado isquierdo
y no se comparan los anteriores ya que no se realizo cambio en la comparacion anterior
A[4]<A[3](1<43)=si se efectua un cambio ya que es menor el uno que el 43
A[3]<A[2](1<23)=se efectua cambio ya que el 1 es menor que el 23
A[2]<A[1](1<12)=se efctua cambio ya que el 1 es menor que 12

A[1,12,23,43,4,56,32,60] y el arreglo esta tomando forma se siguen realizando comparaciones

A[5]<A[4](4<43)=se efectua cambio 4 es menor que 43
A[4]<A[3](4<23)=se efectua cambio 4 menor que 23
A[3]<A[2](4<12)=se efectua cambio 4 menor que 12
A[2]<A[1](4<1)=no se efectua cambio y que 4 es myor que 1

A[1,4,12,23,43,56,32,60]


A[6]<A[5](56<43)=no se efectua cambio 56 mayor que 43 y no se realizan las comaraciones siguentes por que el valor es mas grande que el ultimo

A[7]<A[6](32<56)=se efectua cambio 32 menor que 56
A[6]<A[5](32<43)=se efectua cambio 32 menor que 43
A[5]<A[4](32<23)=no s efectua cambio 32 mayor que 23 y no se realizan las comparaciones anteriores

A[1,4,12,23,32,43,56,60] como ven el arreglo ya esta acomodado de menor a mayor pero se tiene que aser la ultima comparacion

A[8]<A[7](60<56)=no se efectua operacion 60 mayor que 56 y se acabo el ordenamiento

codigo

void insercion_directa(int n)

{

int i,j,aux;

i=j=1;

for(;j<n;j++)

   for(i=j;i > 0 && (arr[i] < arr[i-1]); i--)

    {

   aux=arr[i];

      arr[i]=arr[i+1];

      arr[i+1]=aux;

    }

}

metodo burbuja:

 

consiste en acomodar el vector moviendo al mayor hasta la ultima casilla comenzando desde la primer casilla del vector hasta acomodar el numero mas grande en la ultima poscicion ya que se encuentra el mas grande prosigue a encontrar el siguiente mas grande comparando de nuevo los numeros desde el inicio y asi sucesivamente hasta acomodar todos los elementos del arreglo lo que hace a este metodo muy tardado y no tan eficiente como los demas ya que comparas todos los numeros uno por uno y te regresas al inicio de nuevo a comparar todos los numeros 

ejemplo:

A[12,34,1,21]

aplicamos el metodo 

A[1]<A[2](12<34)=si es menor se queda igual

A[2]<A[3](34<1)=es mayor 34 se recorre una casilla

A[3]<A[4](34<21)=es mayor 34 se recorre una casilla

el numero mayor ya esta en su posicion ahora se realiza de nuevo esto para acomodar el seundo mayor

 

A[ 12,1,21,34]

A[1]<A[2](12<1)=es mayor 12 se recorre una casilla

A[2]<A[3](12<21)=no es mayor se queda igual

A[3]<A[4](21<34)=no es mayor se queda igual

 

y ahora ya esta ordenado el vector pero comoquiera se tiene que realizar una comparacion mas por que el metodo asi lo requiere 

 

 A[ 1,12,21,34]

A[1]<A[2](1<12)=no es mayor se queda igual

A[2]<A[3](12<21)=no es mayor se queda igual

A[3]<A[4](21<34)=no es mayor se queda igual

ahora si ya acabamos de ordenar por el metodo burbuja si se dan cuenta es muy deficiente por que realiza pasos que no son necesarios

metodo de shell:

se denomina asi gracias a su inventor Donald Shell e pero de los casos de este ordenamiento es O(n2) , pero un cambio realizado por V. Pratt produce una implementacion con un rendimiento de O(n log2 n) en el pero de los casos esto es mejor que O(n2) aunque peor que el ideal O(n log n).

el ordenamiento shell mejora el ordenamiento por insercion comparando elementos separados por un espacio de varias posiciones permitiendo a dicho elemento realizar pasos mas grandes hacia su posicion esperada y se reduce los pasos multiples a espacios mas pequeños y al final es un simple ordenamiento por insercion pero ya casi esta ordenado el vector.

por ejemplo:

A[34,56,32,43,12,43,12,78]

para ordenarlo se divide el vector en 3 posciciones

 34,56,32
43,12,43
12,78


ahora ordenamos cada columna por metodo de insercion


12,12,32
34,56,43
43,78


ahora reagrupamos el vector y nos queda


A[12,12,32,34,56,43,43,78]


solo usmos un ultimo paso que es usando metodo de insercion pero si notan ya casi esta acomodado el vetor


A[12,12,32,34,43,43,56,78]


y listo ese es el metodo de shell que es mas eficiente que los dos anteriores sobretodo cuando se trata de vectores muy largos


metodo de quick sort:


es el metodo mas eficiente de todos los anteriores es una mejora de el metodo de intercambio directo y su nombre lo recibe gracias a la velocidad con la cual ordena los elementos del arreglo, su funcionamiento es tomar un valor el que sea como termino medio para comenzar se trata de colocr en su lugar correcto de tal forma que los elementos a la izquierda sean menores y los de la derecha mayores se repiten los pasos pero ahora para los datos de la izquierda por separado de los de la derecha a que sabemos que son los mas chicos a la izquierda y los mas grandes a la derecha.


ejemplo:


A[23,45,12,65,45]

tomamos un numero al azar que sea x, por ejemplo 12

y comparamos de derecha a izquierda 


45>=12= no hay intercambio
65>=12=no hay intercambio


ahora de izquierda a derecha


23<=12=si hay intercambio

y nos queda A[12,23,45,65,45]


como el numero que usamos ya se encuentra en su lugar seguimos comparando con el numero siguiente 23 y empezamos de derecha a izquierda


45>=23=no hay intercambio
65>=23=no hay intercambio
45>=23=no hay intercambio


cambiamos de numero inicial al que sigue 45 y comparamos de derecha a izquierda


45>=45=no hay intercambio
65>=45=no hay intercambio


cambiamos de numero inicial 65 comparamos derecha a izquierda


45>=65=si hay intercambio
y terminamos y el vector resultante es:


A[12,23,45,45,65]


bueno esto es todo por mi parte las fuentes de consulta que realize fueron:


http://sistemas.itlp.edu.mx/tutoriales/estructdatos2/tema2_2.htm
http://www.monografias.com/trabajos/algordenam/algordenam.shtml

http://latecladeescape.com/con-nombre-propio/ordenacion-por-insercion-directa-insertionsort.html
http://es.wikipedia.org/wiki/Ordenamiento_Shell


http://www.angelfire.com/wy2/est_info/quicksort.html