Preogramacion basica

Métodos de Ordenamiento
Los métodos de ordenamiento son muy útiles porque nos permiten buscar valores, tanto por valor y por su posición, de una manera eficiente. Imaginen que tan útil seria un diccionario si las palabras no estuvieran ordenadas alfabéticamente! Antes de estudiar algunos de los métodos de ordenamiento es necesario definir el problema y el entorno en el cual se desea trabajar.Para realizar un ordenamiento se necesita un conjunto de valores ordenables, es decir, que exista un criterio de ordenamiento, por ejemplo las letras se basan en el alfabeto, los números en la cantidad representada. Además se asume que los valores no están repetidos [ esto solo para efecto de los ejemplos, ya que la presencia de valores repetidos no altera el método ]. Además, se trataran solamentemétodos de ordenamiento en los que la instrucción base es la comparación entre dos valores y que se obtiene el ordenamiento por medio de intercambio de valores. Estas consideraciones son la base de los métodos. Son muchos los métodos de ordenamiento, sin embargo, en este curso se hará énfasis en los siguientes métodos: Ordenamiento por selección, por inserción, burbuja. Para tal efecto asuma lassiguientes declaraciones: Type vector = array [ 1 .. 25 ] of integer; Var v : vector; i,j,N,aux,p : integer; y las siguientes asignaciones: v[ 1 ] := 6; v[ 2 ] := 25; v[ 3 ] := 7; v[ 4 ] := 2; v[ 5 ] := 14; N := 5; Ordenamiento por selección Ref.: Luis Joyanes Aguilar. Programación en Turbo Pascal Ver 5.5, 6.0, 7.0, McGraw-Hill, 2ª. Edición, 1993, pp. 420-422. Este método se basa en la búsqueda delprimer mayor / menor, del segundo, del tercero y así sucesivamente hasta agotar la lista de valores a procesar. El algoritmo de ordenación por selección de una lista tiene los siguientes pasos: { Ordenamiento por seleccion en forma descendente } for i:= 1 to N-1 do for j:= i+1 to N do if v[ i ] < v[ j ] then begin aux := v[ j ]; v[ j ] := v[ i ]; v[ i ] := aux; end;

1. Encontrar el mayorelemento de la lista 2. Intercambiar el mayor elemento con el elemento del subíndice 1 3. A continuación se busca el mayor elemento en la sublista de subíndices de 2 hasta n y se intercambia con el elemento de subíndice 2; por consiguiente, se sitúa el segundo elemento mayor en la posición 2 4. A continuación se busca el elemento mayor en la sublista de 3 hasta n, y así sucesivamente

Realizado por:Ing. Katty Ordaz Computación II

1/10

Nota: Si desea realizar el ordenamiento de forma ascendente, se sigue el mismo criterio pero en lugar de intercambiar al encontrar un mayor se intercambia al encontrar un menor. Esto se traduce en cambiar la condición de > a aux then begin p := j; aux := v[ j ]; end; v[ p ] := v[ i ]; v[ i ] := aux; end;

A continuación se presenta una corrida en fríodel algoritmo a fin de observar el movimiento de los valores en el arreglo hasta quedar ordenados. Note que se intercambia una sola vez por cada iteración. Los elementos a reubicarse están indicados con las flechas, el elemento resaltado indica la posición del índice.

Iteración

Descripción del proceso

Movimiento en el arreglo

i
1 Identificado 25 como mayor 6 25 7 2 14

i
2Identificado 14 como mayor 25 6 7 2 14

i
3 Identificado 7 como mayor 25 14 7 2 6

i
4 Identificado 6 como mayor 25 14 7 2 6 Resultado: vector ordenado 25 14 7 6 2

Realizado por: Ing. Katty Ordaz Computación II

2/10

Ordenamiento por burbuja Ref: Luis Joyanes Aguilar. Edición, 1993, pp. 412-417. Programación en Turbo Pascal Ver 5.5, 6.0, 7.0, McGraw-Hill, 2ª.

Este método es clásico ymuy sencillo aunque poco eficiente. La ordenación por burbuja [ bubble sort ] se basa en: 1. La comparación de elementos adyacentes del vector e 2. Intercambio de sus valores si estos están desordenados De este modo se dice que los valores más pequeños burbujean hacia la parte superior de la lista [hacia el primer elemento], mientras que los valores más grandes se hunden hacia el fondo de la lista...