1
TEMAS DE INTRO I- Pilas (datos/estructuras de control)- Filas (datos/estructuras de control)- Modularización y Parámetros- Variables- Método de Desarrollo- Funciones- Arreglos- Matrices (filminas incluye tipos, constantes y
string)- Revisión general / Trabajo Especial
Métodos de Ordenamiento
Los métodos de ordenamiento mas sencillos buscan intercambiar los elementoso llevarlos al lugar adecuado de manera de dejar las estructura dedatos ordenada.
Algunos de los métodos mas sencillos son:- Método De selección - Método De inserción- Método de intercambio o burbujeo
Los métodos de arreglo son generales .
2
Método de Selección
• Para ordenar un arreglo A de n elementos se busca el menor (o mayor) y se lo ubica al comienzo (en A[1]). A continuación se busca el segundo y se lo ubica en A[2] y así sucesivamente…..hasta llegar al anteúltimo elemento (el último elemento queda ordenado automáticamente)
Ejemplo
41253 Arreglo Original con 5 elementos
41253 Paso 1: Intercambia a[1] con A[4]
43251 Paso 2: Intercambia a[2] con A[3]
43521 Paso 3: Intercambia a[3] con A[4]
45321 Paso 4: Intercambia a[4] con A[5]
54321 En 4 pasadas se ordena el arreglo
3
Método de Intercambio o burbujeo
Realiza n-1 pasadas para arreglar un arreglo de N elementos. Mueve los elementos de a un lugar, es decir, compara los adyacentes y los intercambia si están ordenados.Al final de la primer pasada, se habrán comparado N-1 elementos y el elemento más grande (o más chico) se fue arrastrando hasta el final. En la segunda pasada, el segundo más grande (o más chic) queda en la posición N-1.. Y así siguiendo…..
Ejemplo41253 Arreglo Original con 5 elementos
41253 Pasada 1
41253
41523
45123
54123 El A[5] queda ubicado
4
Ejemplo
54132
Pasada 2 54123
El A[4] queda ubicado54312
54312Pasada 3
54321 El A[3] queda ubicado
Ejemplo
54321 Pasada 4
El A[2] queda ubicado
54321 En 4 pasadas en arreglo queda ordenado
5
Método de inserción
• Este algoritmo va ordenando al arreglo tomando cada elemento e insertándolo de manera ordenada en su lugar. Considera al primer elemento como ordenado. Luego toma el segundo y lo compara con el que ya está: si es mayor, lo pone a la derecha, y si es menor a la izquierda. Después el tercero y la compara con los que ya están ordenados hasta encontrar su posición. Se continúa haciendo esto, insertando cada elemento en la posición que le corresponde hasta llegar al último.
• De manera general (en forma creciente):Inicialmente el primer elemento está ordenado. Después, cuando hay K elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con los K elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1.
Ejemplo41253 Pasada 1, considera el A[1] ordenado
41253 Pasada 2
41253
415532
41533
41532
6
45532
41532
41532
1
45332
45322
45321
55321
45321
54321
4
7
Matrices
Arreglos de más de una dimensión
Var Matriz: Array [ inicio1. .fin1, inicio2. .fin2, ] of tipo Primitivo
Matriz[1,3]Se accede por celda indicando cada dimensión
inicio1
inicio2
fin1
fin2
8
Se puede “graficar” de las dos maneras, pero luego se debe respetar la convención, no mezclar los índices.
Materias: Array [año1..año4,cuatri1..cuatri2] of TipoPrimitivo
9
• Definir un matriz de dos dimensiones de enteros y cargarla por teclado
• Implementar un módulo que pase como parámetro una matriz de dos dimensiones de enteros, y un valor a buscar y devuelva la primer posición en la que está. Si el elemento no está, devuelve (-1,-1). Una vez que encuentra la primer ocurrencia del elemento, abandona la búsqueda
10
11
12
Tipo String• Es una secuencia de caracteres (cadena)
de longitud variable.
• Var Palabra: string (long. Variable con un máximo de 255)
• Var Palabra: string[10] (long. Variable con un máximo de 10)
String
Var nombre: string;….nombre:= ´Jorge´ ;
13
14
Alguna funciones con String….
• Length(´abcde´) � 5• Copy(´1234567´, 3, 2) � ´34´
15
Constantes
• Palabra reservada: Const
• Permite definir un literal (nombre, rótulo) y asignarle un valor que NO cambiara en todo el programa
ConstminimoAprobado = 4;
• Permite LEGILIBILIDAD y MODIFICABILIDAD
16
Tipos
• Un tipo es un “molde” que define los posibles valores que se pueden tener y las operaciones
– Tipos primitivos simples (integer, boolean…)– Tipos estructurados (arreglos…)– Tipos definidos por el usuario (Pila, Fila, …)
17
program LluviaSemanal;
constlunes=1;domingo=7;sinvalor=-1;
varlluvias: array[lunes..domingo] of integer;dia:integer;
beginFor dia:=1 to domingo do lluvias[dia]:=sinvalor;
end.
program LluviaSemanal;
constlunes=1;domingo=7;sinvalor=-1;
Typelluvias= array[lunes..domingo] of integer;
varlluviaSemana1, lluviaSemana2: lluvias;dia:integer;
beginFor dia:= lunes to domingo do lluviaSemana1[dia]:=sinvalor;
end.
18
Ventajas de Definir Tipos y constantes
• Hacen mas comprensible y autocontenido el código• Disminuyen la posibilidad de cometer errores• Brindan más velocidad y seguridad a la hora de incorporar cambios en el código• Pascal No permite definir el tipo “array” como parámetro formal, por lo tanto hay que utilizar un tipo definido por el usuario• Las constantes y los tipos se pueden usar en forma global porque su valor NO cambia durante la ejecución ( por esa razón se usa =)•Todas estas ventajas se potencian cuando más se reutiliza su definición, es decir, cuanto más variables o mas código utilizan constantes o tipos.