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.