I) OBJETIVOS
Algoritmos de ordenación La ordenación es muy probable la operación mas importante y mejor estudiada en computación. Principalmente implementaremos algoritmos que realizan la ordenación en la memoria principal, también se puede realizar en el disco duro o en cintas a este tipo de ordenación se conoce como ordenación externa. Esquemas simples de ordenación o clasificación Ordenación o clasificación por Burbuja Uno de los métodos mas simples es la clasificación por burbuja (bubblesort). La idea básica de la clasificación de burbuja es imaginar que los registros a ordenar están almacenados en un arreglo vertical. Los registros con claves menores son “ligeros” y suben. Se recorre varias veces el arreglo de abajo hacia arriba, y al hacer esto, si hay dos elementos adyacentes que no están en orden, esto es, si el “más ligero” está abajo, se invierten. El efecto que produce por esta operación es que el primer recorrido, el registro “más ligero” de todos, es decir, el registro que posee la clave con menor valor, sube hasta la superficie (o parte superior del arreglo). En el segundo recorrido, la segunda clave menor sube hasta la segunda posición, y así sucesivamente.
Algoritmo for i=1 to n-1 do for j=n to downto i+1 do if A[j].clave < A[j-1].clave then intercambia(A[j], A[j-1])Clasificación por Inserción En el i-ésimo recorrido se “Inserta” el i-ésimo elemento A[i] en el lugar correcto, entre A[1], A[2], … ,A[i-1], los cuales fueron ordenados previamente. Después de hacer esta inserción, se encuentran clasificados los registros colocados en A[1], A[2], … ,A[i].
Algoritmo A[0].clave = -∞begin j=i; while A[j]<A[j-1] do begin intercambia(A[j],A[j-1]) j=j-1 endendEn el i-ésimo recorrido se selecciona el registro con la clave mas pequeña, entre A[j],.. ,A[n], y se intercambia con A[i]. Como resultado, después de i pasadas, los i registros menores ocuparán A[1], …, A[i] en el orden clasificado.
Algoritmo for i=1 to n-1 dobegin {Elegir el menor entre A[i], ..., A[n] e intercambiarlo con A[i] } indice_menor = i clave_menor = A[i].clave for j=i to n do begin {Comparar la clave con la actual clave menor} if (A[j].clave < clave_menor) then begin clave_menor = A[j].clave indice_menor = j; end intercambia(A[i],A[indice_menor]) endendComplejidad de tiempo de los métodos Las clasificaciones de burbuja, por inserción y por selección llevan un tiempo O(N2), y llevarán un tiempo 𝛀(N2) tanto en el peor caso y promedio, en buena parte de las secuencias de entrada de n elementos.La clasificación por selección es superior a las clasificaciones de burbuja y por inserción. Limitaciones de los algoritmos simples la clasificación de shell es una generalización de burbuja de O(N1.5) III) PRÁCTICAS DE LABORATORIO 1) Implementar el algoritmo de ordenación Burbuja. namespace AlgoritmosOrdenacionSimples{ class Program { static void Main(string[] args) { // Un arreglo de elementos int[] arreglo = { 12, 5, 3, 8, 11, 9, 12, 1, 4, 7 }; // ordenar el arreglo utilizando el método de burbuja clasificacionPorBurbuja(ref arreglo); // Mostrar el arreglo ordenado for (int i = 0; i < arreglo.Length; i++) { Console.WriteLine("Elemento[{0}]: {1}",i,arreglo[i]); } Console.ReadKey(); } /* * */ static void clasificacionPorBurbuja(ref int[] arreglo) { // N recorridos por el arreglo for (int i = 0; i < arreglo.Length - 1; i++) { // Comparar elementos adyacentes para subir // elementos de menor valor a la superficie for (int j = arreglo.Length-1; j >= i+1; j--) { if (arreglo[j] < arreglo[j - 1]) { // Permutar o intercambiar elementos del arreglo int temp = arreglo[j]; arreglo[j] = arreglo[j - 1]; arreglo[j - 1] = temp; } } } } }}2) Implementar el algoritmo de ordenación por Inserción.
/* * Implementación de la Clasificación por Inserción */ static void clasificacionPorInsercion(ref int[] arreglo) { // Considerar un valor (A[-1].clave = -∞) // cuyo valor de clave sea menor a todos los valores del arreglo int min = -9999; int j; // Realizar n pasadas for (int i = 1; i < arreglo.Length; i++) { // En cada recorrido ubicar el i-ésimo elemento en su posición ordenada j = i; while (arreglo[j] < arreglo[j - 1]) { intercambiar(ref arreglo[j], ref arreglo[j - 1]); // Comparar con el valor mínimo // Consideramos esta condición pues en arreglos de // C# no se considera indices menores a 0. if (j<=0) { if (arreglo[j] < min) { intercambiar(ref arreglo[j], ref min); } break; // abandonar la iteración } j = j - 1; } } } /* * Método para peermutar los valores de dos variables enteras. */ static void intercambiar(ref int a, ref int b) { // intercambia(A[j],A[j-1]) int temp = a; a = b; b = temp; }3) Implementar el algoritmo de ordenación por Selección.
/* * Método para implementar la Clasificación u ordenación por Selección. */ static void clasificacionPorSeleccion(ref int[] arreglo) { int indice_menor; int clave_menor; for (int i = 0; i < arreglo.Length-1; i++) { // Elegir el menor entre A[i], ..., A[n] e intercambiarlo con A[i] indice_menor = i; clave_menor = arreglo[i]; for (int j = i; j < arreglo.Length; j++) { // Comparar la clave con la actual clave menor if (arreglo[j] < clave_menor) { clave_menor = arreglo[j]; indice_menor = j; } } intercambiar(ref arreglo[i], ref arreglo[indice_menor]); } }IV) TAREA:
V) REFERENCIAS BIBLIOGRÁFICAS
|