Estructura de datos

Búsqueda y Ordenación
T T E E M M A A 1 1
1.1. Introducción 1.2.1. Búsqueda Secuencial 1.2.2. Búsqueda Binaria 1.2.3. Búsqueda en Cadenas 1.2.4. Hashing 1.3. Ordenación 1.3.1. Ordenación porInserción 1.3.2. Ordenación por Selección 1.3.3. Ordenación por Intercambio
Metodología de Programación

Introducción
Objetivos • Uso de las estructuras de datos antes • Estructura de datos seleccionadaAlgoritmo diseñado • Tipos de Algoritmos Interno / Externo
Metodología de Programación

Búsqueda
• Operación frecuente en Programación Diversidad de Algoritmos • Diferentes Técnicas de BúsquedaBúsqueda en Listas: Algoritmos, Eficiencia Lista Elementos componentes: Tipo de Datos Simple
Vector = ARRAY[0..N-1]DE TipoElemento

Búsqueda Secuencial
Aplicabilidad: • Desconocimiento acerca de laorganización de los datos • Estructura solo accedida secuencialmente Idea Clave: • Visitar todas las posiciones del array, hasta que se encuentre el elemento o se llegue al final del mismo (elementono esta)
PROC Secuencial(↓ ↓x:TipoElemento) VAR ind:NATURAL Inicio ind ← 0 MIENTRAS (ind V1,....,V4 ordenados. 1 3 7 9 5 23 15 20 1,....,V2

Ordenación por Inserción
20

1

3

5

7
1,....,9

23

15

insertamos V6 1 3 5 7

1,....,V6

9

V5 ordenados, ordenados. 23 15 20

¿Cómo realizar la inserción? • Inserción directa Abrir un hueco en la sucesión V1,....Vi-1 paraencajar Vi Ejemplo:
Paso4: i:=5. Suponemos V1,...., V4 ordenados, insertamos V5 => V1,......, V5 ordenados. 1 3 7 9 5 23 15 20 1 3 5 7 9 23 15 20
Metodología de Programación

1,...., V6 ordenados,insertamos V7 => V1,....,V7 ordenados. 1 3 5 7 9 15 23 20

1,...., V4 ordenados, insertamos V5 => V1,....,V5 ordenados.

1,...., V7 ordenados, insertamos V8 => V1,....,V8 ordenados. 1 3 5 7 9 15 2023

Metodología de Programación

Ordenación por Inserción
FUNC buscar_posicion (↓valor: TipoElemento; ↓ V:Vector; ↓ fin: Indice): Indice VAR i:Indice Inicio i ← 1 MIENTRAS (i ≤ fin) ∧ (V[i] <...