Quicksort

Solo disponible en BuenasTareas
  • Páginas : 2 (345 palabras )
  • Descarga(s) : 0
  • Publicado : 17 de noviembre de 2010
Leer documento completo
Vista previa del texto
DEFINICION
Quicksort es un algoritmo de ordenación, es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos delarreglo. Fue diseñado por Sir Charles Antony Richard Hoare en 1960 un científico en computación.
CARACTERISTICA
• Este método se basa en la táctica “divide y vencerás”: consiste en dividir unproblema en subproblemas y luego juntar las respuestas de estos subproblemas para obtener la solución al problema central (subdividiendo el array en arrays mas pequeños y ordenar estos).
• Esconsiderado entre los mas rápidos y eficientes de los métodos de ordenación interna.

COMO FUNCIONA

• Se toma un elemento X de una posición cualquiera del arreglo.
• Se trata de ubicar a X en laposición correcta del arreglo, de tal forma que todos los elementos que se encuentre a su izquierda sean menores o iguales a X y todos los elementos que se encuentren a su derecha sean mayores oiguales a X
• Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de X en el areglo.
• El procesotermina cuando todos los elementos se encuentran en posición correcta en el areglo.

PUEDE SER LA COMPLEJIDAD: En cuanto a la estabilidad, el quicksort no es estable, el tiempo de ejecución de dichoalgoritmo es variable, desde un tiempo promedio de ordenación de O(n log2n) hasta O(n2) con toda la lista ordenada ya que tiene que hacer subdivisiones de todos los elementos. (Pudiéndose este último casoevitar realizando algunas optimizaciones en el rendimiento.)
Finalmente hay que destacar del quicksort la rapidez de este algoritmo y que no requiere memoria adicional para ejecutarse y por elcontrario tiene una implementación algo complicada, si se utiliza recursividad se utilizan muchos recursos y finalmente hay una gran diferencia en el tiempo utilizado entre el peor y el mejor caso, da una...
tracking img