Ordenamiento

Realizado por: Ing. Katty Ordaz Computación II 1/10

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 solamente mé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 las siguientes declaraciones: y las siguientes asignaciones: 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 del primer 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:

1. Encontrar el mayor elemento 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

Type vector = array [ 1 .. 25 ] of integer; Var v : vector; i,j,N,aux,p : integer;

v[ 1 ] := 6; v[ 2 ] := 25; v[ 3 ] := 7; v[ 4 ] := 2; v[ 5 ] := 14; N := 5;

{ 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;


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 <. El método descrito anteriormente realiza cambios cada vez que encuentra un elemento menor o mayor según sea el caso. Esto puede mejorarse al realizar un solo cambio, después de haber determinado el mayor / menor elemento y su posición.

A continuación se presenta una corrida en frío del 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




Resultado: vector ordenado 25 14 7 6 2

{ Ordenamiento por selección mejorado en forma descendente } for i:= 1 to N-1 do begin p := i; aux := v[i]; for j:= i+1 to n do if v[ j ] > aux then begin p := j; aux := v[ j ]; end; v[ p ] := v[ i ]; v[ i ] := aux; end;


Ordenamiento por burbuja

Ref: Luis Joyanes Aguilar. Programación en Turbo Pascal Ver 5.5, 6.0, 7.0, McGraw-Hill, 2ª. Edición, 1993, pp. 412-417. Este método es clásico y muy 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 en el caso de un ordenamiento ascendente. La técnica de ordenación de la lista por burbuja compara elementos consecutivos de la lista de modo que si en una pasada no ocurrieran intercambios, significaría que la lista esta ordenada.

Pasada 1 Pasada 2 Pasada 3

10 5 5 5 10 8 8 8 10

{ Ordenamiento por burbuja mejorado en forma ascendente } desordenado := true; while desordenado do begin desordenado := false; for i:= 1 to n - 1 do if v[ i ] > v[ I + 1 ] then begin aux := v[ i ]; v[ i ] := v[ i + 1 ]; v[ i + 1] := aux; desordenado := true; end; end;

Prof. María Beatriz Serrano V. 4/10 Computación II

Ordenamiento

Parte 2

Ordenamiento con Matrices

Las diferentes acciones de ordenamiento sobre elementos de una matriz son: 1. Ordenar una fila / columna K de una matriz ( de M filas y N columnas), sin importar la relación

entre las columnas / filas de la matriz. En este caso, al realizar el intercambio solamente se mueven los elementos de la fila K.

10 6 1 8 10 6 1 8 10 6 1 8 5 11 3 9 K 5 11 3 9 3 5 9 114 2 7 12 4 2 7 12 4 2 7 12

Matriz Original Proceso de Ordenamiento Matriz Modificada

Nota: Observe que solamente se ordena la fila K, sin alterar los valores de las columnas correspondientes

{ Ordenamiento de la fila K de la matriz A de M filas y N columnas Sin importar la relación entre columnas } For i := 1 to N-1 do For j := i + 1 to N do If A[ k, i ] > A[ k, j ] then Begin Aux := A[ k, i ]; A[ k, i ] := A[ k, j ]; A[ k, j ] := Aux; End;


2. Ordenar una fila / columna K de una matriz ( de M filas y N columnas), manteniendo la relación entre las columnas / filas de la matriz. Para mantener esta relación es necesario intercambiar todos los elementos de la columna.

3. Ordenar todos los elementos de una matriz de M filas y N columnas. En este caso no puede

ordenarse sobre la misma matriz Matriz Original Proceso Matriz Modificada

10 6 1 8 1 2 3 4 3 5 9 11 5 6 7 8 4 2 7 12 9 10 11 12

10 1 6 2 1 3 8 4 3 5 5 6 9 7 11 8 4 9 2 10 7 11 12 12

10 6 1 8 10 6 1 8 1 10 8 6 5 11 3 9 K 5 11 3 9 3 5 9 114 2 7 12 4 2 7 12 7 4 12 2

Matriz Original Proceso de Ordenamiento Matriz Modificada

Nota: Observe que ordena la fila K, sin embargo para mantener la relación con las columnas correspondientes es necesario intercambiar las columnas completas.

{ Ordenamiento de la fila K de la matriz A de M filas y N columnas Manteniendo la relación entre columnas } For i := 1 to N-1 do For j := i + 1 to N do If A[ k, i ] > A[ k, j ] then { Intercambio de la columna i con la columna j }

For s := 1 to M do Begin Aux := A[ s, i ]; A[ s, i ] := A[ s, j ]; A[ s, j ] := Aux; End;

PASO 3: Copiar vector en matriz

PASO 1: Copiar matriz en vector

PASO 2: Ordenar vector


{ Ordenamiento de todos los elementos de la matriz A de M filas y N columnas } { Paso 1: Copiar matriz en vector } NV := 0; For i := 1 to M do For j := 1 to N do Begin NV := NV + 1; B[ NV ] := A[ i, j ] End; { Paso 2: Ordenar el vector } For i := 1 to NV-1 do For j := i + 1 to NV do If B[ i ] > B[ j ] then Begin Aux := B[ i ]; B[ i ] := B[ j ]; B[ j ] := Aux; End; { Paso 3: Copiar vector en matriz } NV := 0; For i := 1 to M do For j := 1 to N do Begin NV := NV + 1; A[ i, j ] : = B[ NV ]; End;

Prof. Manuel R. Fernández R. 7/10 Computación II

Ejercicios de Ordenamiento

1. Dado un arreglo de N elementos, elabore un programa que ordene el arreglo e imprima el arreglo original y el ordenado uno al lado del otro.

Desordenado Ordenado 20 10 40 20 90 30 10 40 50 50 80 70 70 80 30 90

2. Se tiene en un archivo de nombre muestra.dat un conjunto de valores desordenados entre sí y se desea un programa Pascal que determine la mediana de dichos valores. La mediana es el valor tal que ocupa la posición central del vector una vez ordenado; en caso de existir dos elementos centrales, la mediana es el promedio de estos.

A = 1 2 3 4 6 8 9 N = 7 Mediana = 4

A = 1 2 3 4 6 8 9 12 N = 8

Mediana = (4+6)/2=5.0

3. Elabore un programa Pascal tal que dados los valores enteros de N observaciones a un experimento, determine e imprima la mediana de aquellos valores que terminan en 15

A = 100 115 200 315 215 130 Mediana = 215

A = 105 215 115 120 127 170 Mediana = 165

4. Se tiene en un archivo de datos la información correspondiente a las coordenadas X y Y de los puntos de un juego de tiro al blanco. Elabore un programa que ordene los valores X manteniendo su relación con los valores Y, imprima los puntos y determine la mediana de los valores de X; ¿podría Ud. determinar en estas condiciones la mediana de Y?

5. Dada la información correspondiente a las edades de un grupo de personas. Elabore un programa Pascal que determine la mayor edad y que ordene las edades a partir de la posición del mayor. Imprima los dos vectores el original y el modificado.

Edad 15 17 16 13 12 10

Edad modificado 15 10 12 13 16 17

6. Dado un vector A de N elementos, elabore un programa Pascal que calcule la posición del mayor y el menor valor. Si el menor elemento se encuentra antes del mayor elemento, ordene el vector ascendentemente a partir de la posición del menor hasta la posición del mayor; si el menor elemento se encuentra después del mayor valor, ordene descendentemente a partir de la posición del mayor valor hasta la posición del menor valor.

Vector Original A = -1 4 10 2 4 -2 9

Vector Ordenado A = -1 4 10 4 2 -2 9


7. El empecinado Sr. Fasti, quiere desarrollar un programa para ordenar ascendentemente el vector V de M elementos, que esta en paralelo con el vector W, de atrás hacia adelante; es decir comenzando de las posiciones finales (M) hacia el principio. Pero este ordenamiento solo debe realizarse para la porción comprendida entre las posiciones K y L del vector [ K < L ] y debe mantener la relación con su vector paralelo. Desarrolle el Diagrama de Flujo de un programa que realice esa tarea. A continuación se presenta un ejemplo:

V W V W 2 20 2 20 4 40 4 40 K 9 -90 9 -90 1 -10 8 80 5 50 5 50 L 8 80 1 -10 7 70 7 70 3 30 3 30

ANTES DESPUÉS

8. Una entidad bancaria se encarga de cancelar las pensiones a los jubilados de una empresa. El pago se realiza en función de la centena de la cédula de identidad del pensionado, de la siguiente forma:

1 y 6: Lunes 2 y 7: Martes 3 y 8: Miércoles 4 y 9: Jueves 5 y 0: Viernes

Elabore un programa Pascal que dado un grupo de datos con la siguiente información: Nombre, Cédula y Monto de la Pensión imprima un listado por día donde se muestre:

Día: XXXXXXXX Número de Pensionados: XXX ----- Nombre ------- -- Cédula - - Monto – XXXXXXXXXXXXXXX XXXXXXXX XXXXXXX : : : XXXXXXXXXXXXXXX XXXXXXXX XXXXXXX ----------- Total: XXXXXXX

El listado deberá contener los encabezados adecuados y no más de 40 personas por página ni más de un día de la semana por página.

9. Dada una matriz de orden N, elabore un programa que ordene la fila donde se encuentra el menor elemento, sin importar la relación entre las columnas.

10. Dada una matriz de orden N, elabore un programa que ordene la columna donde se encuentra el mayor elemento, sin importar la relación entre las columnas.

11. Dada una matriz de orden N, elabore un programa que ordene la fila donde se encuentra el menor elemento, manteniendo la relación entre las columnas.

12. Dada una matriz de orden N, elabore un programa que ordene la columna donde se encuentra el mayor elemento, manteniendo la relación entre las columnas.

13. Dada una matriz de orden N, elabore un programa que ordene los elementos ubicados en la diagonal principal

14. Dada una matriz de M filas y N columnas, elabore un programa que ordene los elementos de cada fila a partir de la posición del menor elemento.

15. Dada una matriz de M filas y N columnas, elabore un programa que ordene los elementos de cada columna a partir de la posición del elemento de la diagonal secundaria.


16. Dada la información de los estudiantes de Computación: Cédula de identidad, nombre, y N (N > 8) quices, elabore un programa con subprogramas que determine el promedio de los 8 mejores quices para cada estudiante.

17. Dada la información de los estudiantes de Computación: Cédula de identidad, nombre, sección y N (N > 8) quices, elabore un programa con subprogramas que ordene la información por sección y dentro de cada sección por nombre

18. Dada la información de los estudiantes de la Facultad: Nombre y Fecha de Nacimiento (dia, mes, año) elabore un programa con subprogramas que ordene por fecha de nacimiento y al final determine quien es el nombre del estudiante con mayor edad.

19. a) Elabore una Función que permita ubicar el elemento menor de un vector A de N componentes a partir de la posición K.

b) Elabore un Procedimiento que permita intercambiar dos elementos de un vector.

c) Elabore un Procedimiento que permita intercambiar dos filas K y L de una matriz

d) Elabore un Programa PASCAL que permita leer los datos de M estudiantes (Cédula y las notas de los tres parciales), las cédulas en un vector y las notas en una matriz. Ordene la información en forma creciente según el promedio de notas de los parciales haciendo uso exclusivamente de los 3 subprogramas anteriores. Imprimir la información ya ordenada.

20. a) Desarrolle un subprograma PASCAL que lea una matriz R de LxK elementos.

b) Desarrolle un subprograma PASCAL que imprima una matriz Q de KxL elementos.

c) Dada una matriz H de MxN elementos, un vector fila Q de N elementos y un valor K (1 ≤ K ≤ M+1), elabore un subprograma en PASCAL que modifique la matriz de la siguiente forma:

Si 1 ≤ K ≤ M, inserte el vector en la fila K

Si K=M+1, anexe el vector colocándolo como última fila de la matriz

d) Dada una matriz A de orden PxQ y tres valores enteros K, L y M, elabore un subprograma PASCAL que ordene la fila K a partir de la columna L hasta la columna M de la matriz.

e) Dada una matriz Z de orden K, elabore un subprograma PASCAL que usando el subprograma anterior, ordene cada fila a partir del elemento ubicado en la diagonal secundaria.

f) Dada una matriz C de orden K, elabore una función en PASCAL que calcule la suma de los elementos de la triangular inferior. g) Dada una matriz C de orden K, elabore una función en PASCAL que calcule la suma de los elementos de la triangular superior. h) Dada una matriz AB de orden M, elabore un programa PASCAL que lea la matriz y si la suma de los elementos de la triangular inferior son iguales a la suma de los elementos de la triangular superior, ordene las filas de la matriz a partir de los elementos de la diagonal secundaria, sino, inserte un vector de elementos nulos en la primera fila de la matriz.

−

−−

−−

=⇒

−

−−

−−

=

3104

84310

3118

6210

1430

43810

1318

6210

ZZ


21. a) Desarrolle un subprograma PASCAL tipo función que dada una matriz A de MxN y un valor escalar K, determine el menor valor de la fila K.

b) Desarrolle un subprograma que dada una matriz A de LxP, genere un vector Z donde cada elemento sea igual a la suma de los elementos de cada fila mayores al valor mínimo. Debe usar el subprograma anterior.

c) Desarrolle un subprograma tipo procedimiento que dada una matriz A de LxP elementos y un vector Z de L componentes, ordene el vector en forma descendente, manteniendo la relación con las componentes de las filas de la matriz.

d) Desarrolle un programa Pascal que haciendo uso de los subprogramas anteriores y los que Ud. considere necesarios, haga lo siguiente:

i) Lea el contenido de una matriz C de NxM, donde N representa el número de vendedores

den una empresa y M la cantidad de diferentes artículos que vende la tienda; el contenido [I,J] de la matriz corresponderá a la cantidad vendida del artículo J por el vendedor I. M y N son conocidos y son valores de entrada.

ii) Calcule el promedio de ventas de cada vendedor, el cual será igual a:

iii) Ordene el vector en forma descendente, manteniendo la relación con las componentes de

las filas.

iv) Imprimir la matriz y el vector promedio uno al lado del otro.

13 esr menor valo el 2, K Para 781

1520139511

=

=A

=

=

153520

781

1520139511

ZA

=

=⇒

=

=

152035

7819511

152013

153520

781

1520139511

ZAZA

1-MMenor Venta - Ventas de Suma

Documents

Ordenamiento