158 Ordenamiento, Búsqueda e Intercalación cual las técnicas pueden extenderse a estructuras más complicadas.Por razones de ahorro de memoria, estudiaremos el ordenamiento de un arreglo sobre sí mismo, es decir sin emplear arreglos auxiliares, y consideraremos sólo el ordenamiento creciente, ya que para el decreciente bastaría cambiar el sentido de las desigualdades. 7.1.1 Ordenamiento por selección Dado un arreglo de n componentes, el método de selección para ordenarlo en forma ascen- dente, es el siguiente: encontrar el menor valor del arreglo (seleccionar el valor mínimo del arreglo) intercambiar el elemento encontrado con el primero del arreglo. repetir estas operaciones con los n-1 elementos restantes, seleccionando, el segundo elemento, así sucesivamente. A continuación veremos cómo funciona el método a través de un ejemplo. Supongamos que disponemos de un arreglo unidimensional de 8 componentes enteras 8 6 -1 2 0 3 -4 3 Determinamos la componente con valor mínimo -4 (podría eventualmente haber más de una, en dicho caso seleccionamos la primera encontrada), y la intercambiamos con la primera compo- nente del arreglo original. Al intercambiar resulta: -4 | 6 -1 2 0 3 8 3 La primera componente del arreglo ha quedado ordenada, en el sentido de que es menor o igual que todas las siguientes . Ahora se trata de reordenar las n-1 componentes que siguen a la primera. Empleamos el mismo criterio: intercambiar la componente a ordenar con el mínimo de las que le siguen. Es decir, para ordenar la segunda componente, el mínimo es -1 y resulta: -4 -1 | 6 2 0 3 8 3 donde las dos primeras componentes están ordenadas. Así seguimos hasta ordenar la componente n-1, pues al ser ésta menor o igual que las que le siguen, la n queda también ordenada. -4 -1 0 | 2 6 3 8 3 -4 -1 0 2 | 6 3 8 3 -4 -1 0 2 3 | 6 8 3 -4 -1 0 2 3 3 | 8 6 -4 -1 0 2 3 3 6 | 8 Veamos la implementación de un algoritmo para realizar este proceso. Para ello, sea un ar- reglo de elementos reales a ordenar. Suponemos n < 10000 y declaramos un arreglo de tamaño fijo de 10000 componentes, de las cuales ordenamos las n primeras.
7.1 Ordenamiento 159 AlgoritmoSeleccion entero n, i, j ,lugar real V[10000], min inicio Leer (n) ! cantidad de elementos, suponemos 0<n<=10000 Repetir Para i 1, n Leer (V[i]) fin para ! Comienza el ordenamiento RepetirPara i 1, n-1 ! i es la componente a ordenar min V[i] lugar i RepetirPara j i+1, n Si (V[j] < min) entonces min V[j] ! cambiar el mínimo lugar j ! posición del mínimo fin si fin para V[lugar] V[i] ! intercambiar V[i] min fin para Repetir Para i 1, n Escribir (V[i]) fin para fin ¿Qué sucede si n = 1? Simplemente el “Repetir Para” desde 1 hasta 0 no se ejecuta, y el arreglo de 1 elemento queda como está.Observar que en caso de haber dos o más componentes de igual valor mínimo, la que se selecciona es la que se encontró primero, pues la acción “si V[j] < min” implica que no se ejecuta con valores iguales. 7.1.2 Ordenamiento por intercambio o método de la burbuja Este método comienza comparando cada elemento del arreglo con su siguiente, e intercam- biándolos si es necesario para que queden ordenados. Considerando el arreglo desordenado: 8 6 -1 2 0 3 -4 3 si queremos ordenarlo de menor a mayor, comparamos el primer elemento (8) con el segundo (6), y vemos que hay que intercambiarlos, obteniendo: 6 8 -1 2 0 3 -4 3 Luego hacemos lo mismo con el segundo (8) y el tercero (-1):
Created with BuildVu