'P' 'P' 'P' 'P' 'P'
Arreglos
Búsquedas & Ordenamientos
Lic. en Sistemas - UNRN
Problema de Búsqueda
Se dispone de información almacenada en una estructura de datos indexada, sobre las
ventas de una Carnicería durante el último mes. Se sabe que la carnicería trabaja solo 26
días al mes.
Algún día Existió alguna
se vendió venta de
más de X exactamente
X pesos
pesos?
Algún día
Una Solución....2 3 4 se vendió
5
más de X
pesos?
Vector de Ventas, dónde cada índice
indica el día. 0 día 1, 1, día 2 ....etc
1. Recorrer el vector comenzando desde el principo
día1 día26 2. En cada posición evaluar Si la venta supera el
valor X, en caso afirmativo terminar SINO
3. Avanzar a la siguiente posición
0 25
Algún día
Solución...con el
2 vector ordenado
3 4 se vendió
5
más de X
pesos?
Vector de Ventas, dónde cada índice
indica el día. 0 día 1, 1, día 2 ....etc
1. Recorrer el vector comenzando desde el principo
día1 día26 2. En cada posición evaluar Si la venta supera el
valor x, en caso afirmativo terminar SINO
3. Avanzar a la siguiente posición
0 25
Búsqueda
Implica localizar un dato, dentro de un conjunto; el dato a
localizar puede o no estar entre los elementos del conjunto.
La e ciencia de las soluciones (algoritmos) se mide por la
velocidad con que un dato es encontrado.
Problema: Dado un vector y un elemento E,
Búsqueda
determinar si E existe o no en el vector.
En caso que exista recuperar la posición en
la que se encuentra
Buscar
AlgoritmoBUSCAR(Arreglo,tamaño,elemento)
Búsqueda Secuencial
Arreglos - Operaciones
Consiste en ir comparando cada elemento del arreglo con el búscado,
hasta que se encuentra o hasta recorrer todo el arreglo
Cuándo el
vector está
ordenado, se
establece un
punto de corte
El vector
Búsqueda Binaria ... debe estar
ordenado
Arreglos - Operaciones
Consiste en ir dividiendo el vector en dos y tomar la posición media, si el
valor de esa posición coincide con el buscado entonces se termina el
proceso, en otro caso se determina en cuál de los 2 subvectores buscar y se
aplica el mismo proceso hasta que el vector ya no se puede dividir o hasta
que se encuentra el elemento buscado
Algoritmo busquedaBinaria(int vector[], int X, int inicio,
int n, int *pos)
INICIO
encontre = Falso
*pos = -1
Mientras no(encontre) y (inicio < n)
Arreglos - Operaciones
medio = ( n + inicio)/2
SI (vector[medio] == X) ENTONCES
encontre = Verdadero
SINO
SI (vector[medio] < X) ENTONCES
n = medio-1
SINO
inicio = medio+1
Si encontre == Verdadero
*pos = medio
FIN
Ordenamiento
Ordenar los datos de una ED consiste en clasificar su
contenido siguiendo algún determinado orden con
respecto a algun contenido considerado Clave.
Orden: Relación de una cosa con respecto a otra.
Clave: Campo por el cual se ordena.
Algoritmos Ordenamiento - Criterios de E ciencia
La cantidad de pasos.
La cantidad de comparaciones entre los elementos.
La cantidad de movimientos o intercambios de elementos
necesarios para ordenar N elementos
Arreglos - Ordenamiento Burbujeo
Se va recorriendo el vector comenzando
por el primer elemento y hasta llegar al
último, y en cada recorrida se lleva el
elemento más grande (en este ejemplo)
hacia el fondo. Así en la próxima recorrida
el límite superior del recorrido disminuye
en 1 ...y así sucesivamente hasta llegar a 0
Arreglos - Ordenamiento Burbujeo
Material tomado de https://slideplayer.es/slide/26625/
void burbujeo(vector, tam):
permuta = 1; //true void intercambiar(vector, pos1,pos2):
iteracion = 0 aux = vector[pos1]
while (permutation == 1) vector[pos1] = vector[pos2]
{ permutation = 0 //False vector[pos2] = aux
iteración = iteración + 1
for (actual =0, actual < tam - iteración; actual ++)
{
if vector[actual] > vector[actual + 1]
permutation = 1
intercambiar(vector, actual, actual + 1)
}
}
Vectores- Ordenamiento por
Selección
Consiste en recorrer el vector, identificando el
menor de todos los elementos del mismo e
intercambiarlo con el de la primera posición.
Luego el segundo mas pequeño y así
sucesivamente hasta ordenar todo el arreglo
void seleccionOrd(vector, tam):
for(actual =0; actual <tam; actual++){
min= actual
for (j =actual +1; actual <tam; actual++){
if (vector[j] < vector[min] )
min= j
if (min != actual )
temp = vector[actual]
vector[actual] = vector[min]
vector[min] = temp
Arreglos - Ordenamiento por Inserción
Consiste en dividir el arreglo en dos partes
ordenada y desordenada. Y una a uno, insertar
los valores desordenados en las posiciones
correctas dentro del subarreglo
void InsercionOrden(Vector, tam):
{
for (i=actual +1; actual <tam; actual++)
{ actual = Vector[i]
j=i
#Desplazamiento de los elementos
while (j>0) and (Vector[j-1]>actual)
{
Vector[j]=Vector[j-1]
j = j-1
#insertar el elemento en su lugar
Vector[j]=actual
}
}
miVector [N] de enteros
15 '23 ..........
Algoritmos a fondo: con implementaciones en C y Java
Bibliografía
& Otros
recursos
http://lwh.free.fr/pages/algo/tri/tri_insertion_es.html
https://visualgo.net/en/sorting
