saagad

Ordenamiento por intercambio
El algoritmo del intercambio aunque es el más sencillo de implementar es uno de los mas pobres en rendimiento, se basa en la idea de buscar cada vez el menor elementodel conjunto y ubicarlo al principio del mismo, repitiendo este proceso cada vez con el conjunto sin su primer elemento (el menor del conjunto anterior), hasta llegar a un conjunto de un solo elementoque por definición ya está ordenado.
En cada paso del algoritmo se compara el primer elemento del conjunto x[i], con los demás elementos del mismo x[j] (j=i+1 .. n) y cuando x[i]es mayor que x[j], seintercambian sus valores. Cuando se termina de recorrer el arreglo el proceso nos garantiza que en x[i] está el menor elemento del conjunto.
Ordenamiento Shell
Es un algoritmo de ordenamiento. Elmétodo se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V.Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunquees fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por inserción, teniendoen cuenta dos observaciones:
El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólouna posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos másgrandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción,...