Algoritmo BM

Tabla que indica la complejidad según la cantidad de cálculos que corresponden a cada método de ordenamiento e indica si es estable o no

Método mejor caso peor caso caso promedio estabilidad

Inserción a(n) o(n²) o(n²) ?

Selección o(n²) o (n²) o (n²) x

Burbuja o (n²) o (n²) o (n²) ?

Shellsort o(nlogn)
O (n²) o (n²) x

Mezclas o(nlogn) o(nlogn) o(nlogn) ?

(mergel)

Rapidp o(nlogn) o (n²) o(nlogn) x

______________________________________________________________________________

Método de la burbuja

El método de la burbuja es una de los mas sencillos, es tan fácil como comparar todos los elementos de una lista contra todos, si se cumple que una es mayor o menor a otro, entonces los intercambia de posición. Se recorre el arreglo n veces hasta que no haya cambios a realizar.

_______________________________________________________________________________

Burbuja mejorada

Es mejorada ya que el algoritmo termina cuando los datos ya están ordenados esto se logra con el uso de una bandera, la cual detecta que los datos ya están ordenados porque no se produce un intercambio al terminar el segundo ciclo.

_______________________________________________________________________________

Ordenamiento por inserción

Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son indispensables dos cosas:

Un arreglo o una estructura similar de elementos comparables y un criterio claro de comprobación, tal que dados dos elementos nos diga si están en orden o no.

El algoritmo consiste en realizar varias pasadas sobre un arreglo. En cada pasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores, con esto se logra ir manteniendo una lista ordenada constantemente cada elemento a analizar se desplaza por esa lista hasta encontrar su lugar.

Cuando todos los elementos han sido analizados, la lista completamente ordenada; por lo cual en el algoritmo por inserción el arreglo no está totalmente ordenado hasta que el algoritmo termina. Por otro lado, en cada pasada no se recorre todo el arreglo, si no solo los elementos analizados y ordenados en pasadas anteriores; esto lo convierte en un algoritmo “en línea”, es decir, un algoritmo que no necesita disponer de todos los elementos a ordenar desde el principio, si no que puede aceptarlos de 1 en 1 y procesarlos a medida que los recibe.

______________________________________________________________________________

Ordenación por el método de Shell

Basado en comparaciones e intercambios y con unos resultados fundamentalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección o el de inserción.

Se trata de un algoritmo de ordenación interna pero podría utilizarse para ordenación externa.

Necesita que el tiempo de acceso a cualquier dato sea constante (es decir fue ideado para trabajar con arreglos, apuntadores, etc.). En otras estructuras como listas enlazadas, en ese caso el tiempo de acceso es no es constante.

El algoritmo se considera no estable, ya que , dados dos elementos que al compararlos sean iguales no mantiene necesariamente el orden relativo inicial entre ellos.

La implementación original de Shell tiene una complejidad en el peor caso de O(n²), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que otros algoritmos de ordenación interna que también son de orden O(n²).

_______________________________________________________________________________

Ordenamiento por medios (mergesort)

Este algoritmo consiste básicamente en dividir en partes iguales la lista de números y luego “mezxlarlos”comparándolos, dejándolos ordenados. Esto es un algortitmo recursivo con un numero de comparasiones mínimo basado en la técnica divide y vencerás.

El tiempo de ejecución es 0(N log N) para el mejor caso. Su desventaja es que trabaja sobre un arreglo auxiliar lo cual tiene dos consecuencias.

Uso de memoria externa

Trabajo(tiempo) extra consumido en las capas entre arreglos.

En cada recurcion se toma un arreglo de elementos desordenados, lo divide en dos mitades, se aplica recurcion en cada una de estas i hasta quedar en arreglos de 1 elemento y luego se intercalan (mezclan) cada división para obtener el arreglo ordenado.

La interralacion toma dos secuencias o arreglos de elementos y a partir de esta construye una tercera concecuensia que contiene todos los elementos de estos en orden.

_______________________________________________________________________________

Ordenación rápida quicksort

Introducción

El método de ordenamiento rápido es probablemente el mas utilizado de todos, el algoritmo básico fue desarrollado en 1960 por C.A.R , este método es popular porque es fácil de implementar, genera buenos resultados generales y en muchos casos consume menos recursos que cualquier método de ordenación.

Ebtre las ventajas destacan que en el caso promedio tiene una eficiencia de 0(nlogn) y tiene un bucle interno extremadamente corto, uno de los inconvenientes puede ser es recursivo aunque hay versiones no recursivas y otro seria que es frágil durante la implementación pasa inadvertido un simple error puede causar un mal comportamiento.

Se han implementado y analizado muchas versiones mejoradas pero es fácil decepcionarse porque este algoritmo es ------- bien equilibrado que los efectos de mejoras en una parte del programa puede estar descompensando por las concecuensias de un mal rendimiento de otra.

_______________________________________________________________________________

El algoritmo básico

Al igual que el algoritmo de ordenación por mezclas, el algoritmo de ordenación rápida utiliza la técnica de divide y vencerás, se basa en que cada recurcion, dividir el arreglo en subarreglos, resolverlos cada uno por separado y unir la solucionesp

_______________________________________________________________________________

Eligiendo el algoritmo de ordenamiendo mas adecuado

Cada algoritmo se comporta de modo diferente de acuerdo a la cantidad y la forma en que se presenten los datos, entre otras cosas no existe el algoritmo adecuado,solo existe el mejor para cada caso particular, por lo cual hay que conocer a fondo el problema que se quiere resolver y aplicar el mas adecuado.

Hay algunas preguntas que nos pueden ayudar a elegir:

• ¿Qué grado de orden tendrá la información que vamos a manejar?

Si la información esta casi ordenada, un algoritmo sencillo como el método de la burbuja será sufieciente si los datos están muy desordenados un algoritmo mas eficiente como el quicksort puede ser el mas indicado.

• ¿Que cantidad de datos vamos a manipular?

Si la cantidad es pequeña, no es necesario utilizar un algoritmo complejo es preferible uno de fácil implementación. En cantidades muy grandes hay que evitar utilizar un algoritmo que requiera mucha memoria adicional,

• ¿Qué tipo de datos queremos ordenar?

Algunos algoritmos solo funcionan con un tipo de datos específicos como enteros, enteros positivos) y otros son generales, aplicables. En Cualquier tipo de dato.

• ¿Qué tamaño tienen los registros de tu lista o arreglo?

En los algoritmos que usan múltiples intercambios si los registros son de gran tamaño estos intercambios son mas lentos.

_______________________________________________________________________________