Algoritmos Computacionales exposicion II Intercambio y Seleccion

Algoritmos
Computacionales

Algoritmo de Ordenacion Por Intercambio

Y
Algoritmo de Ordenacion Por Seleccion

Algoritmo de
Ordenacion
Ordenar:
Es
simplemente
colocar información de una
manera especial basándonos en
un criterio de ordenamiento. Un
ordenamiento es conveniente
usarlo cuándo se requiere hacer
una cantidad considerable de
búsquedas y es importante el
factor tiempo.
Ordenamiento: Esla operación
de arreglar los registros de una
tabla en algún orden secuencial
de acuerdo a un criterio de
ordenamiento.

Un
Algoritmo
de
ordenamiento: es aquel
que pone elementos de
una lista o un vector en
una secuencia dada por
una relación de orden.
El propósito principal de
un ordenamiento es el de
facilitar las búsquedas de
los miembros del conjunto
ordenado, los algoritmos
de
ordenamientonos
permiten,
como
su
nombre lo dice, ordenar.

En este caso, nos servirán para ordenar
vectores o matrices con valores asignados
aleatoriamente.
Los métodos de ordenamientos son muy
importantes, ya que estos nos permiten tener
un buen punto de partida para resolver
problemas complejos.
Un algoritmo de ordenación pone elementos
de una lista o un vector en una secuencia dada
por una relación deorden, es decir, el resultado
de salida ha de ser una permutación o
reordenamiento de la entrada que satisfaga la
relación de orden dada.

Que es una permutacion?
Es la variación del orden o de la disposición
de los elementos de un conjunto.

Por ejemplo, en el conjunto {1,2,3},
cada
ordenación
posible
de
sus
elementos, sin repetirlos, es una
permutación.
Existe un total de 6 permutaciones para
estoselementos:
"1,2,3", "1,3,2", "2,1,3", "2,3,1", "3,1,2"
y "3,2,1".

Método de
Intercambio

Ordenación

Este algoritmo se basa en la
lectura sucesiva de la lista a
ordenar,
comparando
el
elemento inferior de la lista
con
los
restantes
y
efectuando intercambio de
posiciones cuando el orden
resultante de la comparación
no sea el correcto. Se
encarga de ordenar los
elementos de una lista en
ordenascendente.

Por

Teniendo en cuenta que el algoritmo de
ordenamiento por intercambio se realiza
siempre de la misma manera independiente de
los datos que estén almacenados, no existe un
mejor, peor o caso promedio y su complejidad
siempre
será
O(n2),
Orden
complejidad
Cuadrático.
En cada paso del algoritmo se compara el
primer elemento del conjunto x[i], con los
demás elementos del mismo x[j](j=i+1 .. n) y
cuando x[i] es mayor que x[j], se intercambian
sus valores. Cuando se termina de recorrer el
arreglo el proceso nos garantiza que en x[i] está
el menor elemento del conjunto

Ejemplo
Se ilustra con la lista original 8, 4, 6, 2 que
ha de convertirse en la lista ordenada 2, 4,
6, 8. El algoritmo realiza n−1 pasadas (3
pasadas en este ejemplo), siendo n el
número de elementos, y ejecutalas
siguientes operaciones. a[0] a[1] a[2]
a[3].

El Ordenamiento Por
Intercambio

Ejemplo de Ord. Por
Intercambio

Ventajas del método de Intercambio:
-Es bastante sencillo
-En un código reducido que realiza el
ordenamiento
-Eficaz
Desventajas del método por
intercambio
-Consume bastante tiempo de computadora
-Requiere muchas lecturas/escrituras en
memoria

Método
Ordenamiento
Selección

dePor

Se basa en
dos principios básicos:
Seleccionar el elemento más pequeño (o
más grande) del arreglo, colocarlo en la
posición más baja (o más alta) del arreglo.
En este método el elemento más pequeño (o
más grande) es el que se coloca en la
posición final que le corresponde.

Es decir, si el array A
tiene n elementos, se
trata de ordenar los
valores del array de
modo
que
el
dato
contenido enA[0] sea el
valor más pequeño, el
valor almacenado en
A[1] el siguiente más
pequeño, y así hasta
A[n-1],
que
ha
de
contener el elemento de
mayor valor.

A[]

El algoritmo se apoya en
sucesivas
pasadas
que
intercambian el elemento
más pequeño sucesivamente
con el primer elemento de la
lista, A[0] en la primera
pasada. En síntesis, se busca
el elemento más pequeño de
la lista y se intercambia con...