Vectores

Métodos de ordenamiento y
búsqueda en vectores

Ordenación (clasificación)
• Es la operación de organizar un conjunto
de datos en algún orden o secuencia
específica, tal como creciente o
decreciente para datos numéricos o
alfabéticamente para datos de tipo
carácter.
• Operaciones típicas de ordenación son:
lista de números, archivos de clientes de
banco, nombres en una agendatelefónica.

Ordenación (clasificación)
• En síntesis, la ordenación significa poner
objetos en orden ascendente o
descendente. El propósito final de la
clasificación es facilitar la manipulación de
datos en un vector.

Ordenación (clasificación)
Los métodos directos son los que se
realizan en el espacio ocupado por el
arreglo. Los que vamos a estudiar son:
• Método de intercambio oburbuja.
• Ordenación por Inserción
• Ordenación por Selección

Método de intercambio o de
burbuja
Se basa en el principio de comparar pares
de elementos adyacentes e
intercambiarlos entre sí hasta que estén
todos ordenados.

Método de intercambio o de
burbuja
El elemento cuyo valor es mayor sube
posición a posición hacia el final de la
lista, al igual que las burbujas de aire en
undepósito. Tras realizar un recorrido
completo por todo el vector, el elemento
mencionado habrá subido en la lista y
ocupará la última posición. En el segundo
recorrido, el segundo elemento llegará a la
penúltima posición, y así sucesivamente.

Método de intercambio o de
burbuja
Los pasos a dar son:
1. Comparar A[1] y A[2], si están en orden, se
mantienen como están, en caso contrariose
intercambian entre si.
2. A continuación se comparan los elementos 2 y
3, de nuevo se intercambian si es necesario.
3. El proceso continúa hasta que cada elemento
del vector ha sido comparado con sus
elementos adyacentes y se han realizado los
intercambios necesarios.

Método de intercambio o de
burbuja
La acción de intercambiar entre sí los
valores de dos elementos A[i], A[i+1]es
una acción compuesta que contiene las
siguientes acciones, utilizando una
variable auxiliar:
A[i]

2

1

A[i+1]

3
AUX

Método de intercambio o de
burbuja
En pseudocódigo:
AUX ← A[i]
A[i] ← A[i+1]
A[i+1] ← AUX

Método de intercambio o de
burbuja
algoritmo burbuja1
tipo
array [1..N] de entero: vector
var
vector: X
entero: i, j
inicio
desde i ← 1 hasta N hacerleer(X[i])
fin_desde
desde i ← 1 hasta N-1 hacer
desde j ← 1 hasta N-1 hacer
si X[j] > X[j+1] entonces
AUX ← X[j]
X[j] ← X[j+1]
X[j+1] ← AUX
fin_si
fin_desde
fin_desde
desde i ← 1 hasta N hacer
escribir(X[i])
fin_desde
fin

algoritmo burbuja2
tipo
array [1..N] de entero: vector
var
vector: X
entero: i, j
inicio
desde i ← 1 hasta N hacer
leer(X[i])
fin_desde
desde i ← 1hasta N-1 hacer
desde j ← 1 hasta N-i hacer
si X[j] > X[j+1] entonces
AUX ← X[j]
X[j] ← X[j+1]
X[j+1] ← AUX
fin_si
fin_desde
fin_desde
desde i ← 1 hasta N hacer
escribir(X[i])
fin_desde
fin

Método de intercambio o de
burbuja
Suponga que se quiere ordenar de forma
ascendente el vector:

Método de ordenación por
inserción
Este método consiste en insertar un
elemento en elvector en una parte ya
ordenada de este vector y comenzar de
nuevo con los elementos restantes.
Por ser utilizado cuando uno juega cartas
también se conoce con el nombre de
método de la baraja.

Método de ordenación por
inserción

Método de ordenación por
inserción
El método se basa en comparaciones y
desplazamientos sucesivos. El algoritmo
de ordenación de un vector X de N
elementosse realiza con un recorrido de
todo el vector y la inserción del elemento
correspondiente en el lugar adecuado.

Método de ordenación por
inserción
algoritmo método_inserción
tipo
array [1..N] de entero:
vector
var
vector: X
entero: i, j
inicio
desde i ← 2 hasta N hacer
AUX ← X[i]
K←i–1
SW ← falso
mientras (AUX < X[K]
hacer
X[K+1] ← X[K]
K←K–1
fin_mientras
X[K+1] ← AUX...