Algoritmos de OrdenamientoComparativa

Alumno : Víctor Hugo Orellana Jaque"Análisis de Algoritmos Sección 112"Profesora : Sra. Pilar Pardo Hidalgo"

5-junio-2014"

Burbuja   Burbuja  Bidireccional  

Quicksort   Heapsort   Shellsort   Inserción  

Descripción   Se  basa  en  el  principio  de  comparar  pares  de  elementos  adyacentes  e  intercambiarlos  entre  sí  hasta  que  estén  todos  ordenados.  

La  manera  de  trabajar  de  este  algoritmo  es  ir  ordenando  al  mismo  <empo  por  los  dos  extremos  del  vector.  Hacemos  un  recorrido  ascendente  (del  primer  elemento  al  úl<mo),  cogemos  el  primer  elemento  y  lo  comparamos  con  el  siguiente,  si  el  siguiente  es  menor  lo  pasamos  al  puesto  anterior,  de  esta  forma  al  final  de  la  lista  nos  queda  el  mayor.    Se  conoce  también  como  “cocktail  s  

Funciona  según  el  principio  de  divide  y  vencerás.  Se  divide  la  lista  de  elementos  en  dos  sublistas,  basado  en  un  elemento  pivote.  Todos  los  elementos  de  la  primera  sublista  se  acomodan  para  ser  menores  que  el  pivote  (mismo  caso  con  los  mayores).  El  mismo  proceso  de  par<ción  y  organización  se  realiza  repe<damente,  hasta  que  se  ordena  la  lista  completa  de  elementos.    

Basaso  en  comparaciones  de  elementos  que  u<liza  un  heap  para  ordenarlos.  Almacena  todos  los  elementos  del  vector  a  ordenar  en  un  monPculo  y  luego  extrae  el  nodo  que  queda  como  raíz  en  sucesivas  iteraciones  obteniendo  el  conjunto  ordenado.  La  cima  siempre  contendra  el  mayor  o  el  menor  elemento  del  monPculo    

Ordena  la  estructura  de  una  manera  similar  a  la  de  burbuja,  pero  no  ordena  entre  los  elementos  adyacentes,  sino  que  segmenta  los  datos.  La  segmentación  puede  ser  de  cualquier  tamaño  de  acuerdo  a  una  secuencia  de  valores  que  empiezan  con  un  valor  grande  y  van  disminuyendo  hasta  llegar  al  “1”.  

Construye  una  lista  ordenada  en  el  interior  del  array  a  ordenar.  Hace  comparaciones,  así  que  para  que  realice  su  trabajo  de  ordenación  son  imprescindibles  dos  cosas:  un  array  o  estructura  similar  de  elementos  comparables  y  un  criterio  claro  de  comparación,  tal  que  dados  dos  elementos  nos  diga  si  están  en  orden  o  no.    Se  realizan  varias  pasadas  sobre  el  array.  En  cada  pasada  se  analiza  un  elemento,  y  se  intenta  encontrar  su  orden  rela<vo  entre  los  analizados  en  pasadas  anteriores.    

Mejor  Caso   n   n   n  log  n   n  log  n   n   n  

Caso  Promedio   n2    

n2    

n  log  n   n  log  n    

n  log2  n  o  n3/2  

n2    

Peor  Caso   n2    

n2    

n2   n  log  n    

n  log2  n     n2    

Burbuja   Burbuja  Bidireccional  

Quicksort   Heapsort   Shellsort   Inserción  

Ventajas   •  Fácil  implementación  

•  No  requiere  memoria  adicional  

•  Fácil  implementación  (un  poco  mayor  de  dificultad  que  burbuja)  

•  Demora  menos  de  lo  que  demora  burbuja  

•  No  requiere  memoria  adicional  

•  Muy  rápido  •  No  

requiere  memoria  adicional  

•  El  método  funciona  mejor  con  datos  desordenados.  

•  No  u<liza  memoria  adicional  

•  Su  desempeño  en  promedio  es  como  Quicksort  pero  se  comporta  mejor  que  éste  en  peor  caso.  

•  Muy  simple,  <empo  de  ejecución  aceptable  

•  Muy  rápido  •  No  requiere  

memoria  adicional  

•  Fácil  Implementación  

•  Requerimientos  mínimos  de  memoria  

Desventajas   •  Muy  lento  •  Realiza  

muchas  comparaciones  

•  Realiza  muchos  intercambios  

•  Muy  lento  •  Realiza  muchas  

comparaciones  •  Realiza  muchos  

intercambios  

•  Implementación  un  poco  complicada  

•  Recursividad  (muchos  recursos)  

•  Mucha  diferencia  entre  el  mejor  y  el  peor  caso  

•  No  es  estable,  se  comporta  de  manera  ineficaz  con  datos  del  mismo  valor  

•  Método  complejo  

•  Diacil  de  calcular  su  complejidad,  depende  de  la  secuencia  de  incrementos  que  use  

•  No  es  estable  porque  puede  perder  el  orden  rela<vo  con  facilidad  

•  Lento  •  Realiza  

muchas  comparaciones  

F I N

Gracias por su atención"