Estructuras de Datos I - Ordenamientos Iterativos Inserción

Vista previa del material en texto

Estructuras de Datos I
Ordenamientos Iterativos
Ordenamiento por Inserción [Insert Sort]
Iterativo
Basado en desplazamientos
Consiste en ir insertando un elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada.
Ordenamiento por Inserción [Insert Sort]
3
43
1
23
69
93
El primer elemento siempre esta ordenado
Ordenamiento por Inserción [Insert Sort]
3
43
1
23
69
93
Ordenamiento por Inserción [Insert Sort]
3
43
1
23
69
93
Ordenamiento por Inserción [Insert Sort]
3
43
1
23
69
93
Ordenamiento por Inserción [Insert Sort]
3
43
1
23
69
93
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
69
93
23
1
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Ordenamiento por Inserción [Insert Sort]
3
43
1
69
93
23
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
43
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
43
1
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
43
1
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
43
1
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
43
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
43
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
23
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
23
2
2
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
23
69
93
23
2
2
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
43
69
93
23
2
2
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
43
69
93
23
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
43
69
93
23
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
43
1
43
69
93
23
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
1
43
69
93
23
2
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
1
43
69
93
23
3
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
1
43
69
93
23
3
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
1
43
69
93
1
3
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
1
43
69
93
1
3
3
0
aux
J
1
2
3
4
5
iFunción: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
1
43
69
93
1
3
3
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
43
43
69
93
1
3
3
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
43
43
69
93
1
3
2
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
43
43
69
93
1
3
2
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
43
23
69
93
1
3
2
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
43
23
69
93
1
3
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
23
43
23
69
93
1
3
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
3
43
23
69
93
1
3
1
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
3
43
23
69
93
1
3
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
3
43
23
69
93
1
3
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
3
3
43
23
69
93
1
3
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
1
3
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
1
4
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
1
4
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
69
4
0
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
69
4
4
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
69
4
4
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
69
4
4
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
69
5
4
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
69
5
4
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
93
5
4
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
93
5
5
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
93
5
5
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
93
5
5
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
93
6
5
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	finmientras
1
3
43
23
69
93
93
6
5
0
aux
J
1
2
3
4
5
i
Función: InsertSort
Recibe: datos[ ], ultInd
Regresa: nada
	i = 1
	mientras i <= ultInd
		aux = datos[i]
		J = i
		mientras J > 0 AND aux < datos[J - 1]
			datos[J] = datos[J-1]
			J = J – 1
		fin mientras
		¿ i != J?
			Si: datos[J] = aux
		i = i + 1
	fin mientras
1
3
43
23
69
93
93
6
5
0
aux
J
1
2
3
4
5
i