El Ordenamiento de Burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo.
Visual Basic for Applications
Sub ORDENAR()
Dim X As Integer
Dim I As Integer
Dim y As Double
Dim j As Integer
X = 1
For I = 1 To 10
Cells(I, 1) = Rnd
Next I
For I = 1 To 9
For j = I + 1 To 10
If Cells(I, 1) < Cells(j, 1) Then
y = Cells(j, 1)
Cells(j, 1) = Cells(I, 1)
Cells(I, 1) = y
End If
Next j
Next I
End Sub
Visual Basic .NET
Module Burbuja
" Con Este algoritmo podras ordenar un conjunto de numeros que esten dentro de un vector de menor a mayor e imprimirlos al final "
( Es una aplicacion de consola como veran )
Sub Main()
Dim i, v(10), j, aux As Integer
'''Se dimencionan las variables i y j para los siclos repetitivos ( for)
y el vector v con que va a contener 10 posiciones V(10) y la variable aux que nos servira como auxiliar para el intercambio de valores '.''
For i = 1 To 10
Console.WriteLine(" Digite Un numero para la casilla " & i & " del vector :")
v(i) = Console.ReadLine
Next
For i = 1 To 10
For j = 1 To 10 - 1
If v(j) > v(j + 1) Then
aux = v(j)
v(j) = v(j + 1)
v(j + 1) = aux
End If
Next
Next
For i = 1 To 10
Console.WriteLine(v(i))
Console.ReadLine()
Next
End Sub
End Module
C
void bubble(int *start, int *end) //Ordena un conjunto de números enteros de menor a mayor
{
short fin;
do
{
fin=0;
for (int *i=start;i!=*end;i++)
{
if (*i>*(i+1))
{
intercambia(i, i+1);
fin=1;
}
}
}while (fin!=1);
}
C (Ejemplo 2)
void bubble(int A[], int tamano_arreglo) //Ordena un arreglo de números enteros de menor a mayor
{
int temp, j, i;
for(i = (tamano_arreglo-1); i >= 0; i--)
{
for(j = 1; j <= i; j++)
{
if(A[j-1] > A[j])
{
/* Intercambio de numeros*/
temp = A[j-1];
A[j-1] = A[j];
A[j] = temp;
}
}
}
}
miércoles, 22 de octubre de 2008
jueves, 16 de octubre de 2008
Método intercambio directo
Intercambio directo, conocido coloquialmente con el nombre de la burbuja, es el más utilizado por los estudiantes principiantes de computación, por su fácil comprensión y programación.
Definición Breve: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
El método de intercambio directo puede trabajar de dos maneras diferentes.
llevando los elementos más pequeños hacia la parte izquierda del arreglo.
llevando los elementos más grandes hacia la parte derecha del mismo.
La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan N-1 pasadas, transportando en cada una de las mismas el menor o mayor elemento (Según sea el caso) su posición ideal. Al final de las N-1 pasadas los elementos del arreglo estarán ordenados.
Ejemplo: Arreglo {40,21,4,9,10,35}:
Primera pasada:{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.
{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.
{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.
Segunda pasada:{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.
{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.
{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.
Definición Breve: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
El método de intercambio directo puede trabajar de dos maneras diferentes.
llevando los elementos más pequeños hacia la parte izquierda del arreglo.
llevando los elementos más grandes hacia la parte derecha del mismo.
La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan N-1 pasadas, transportando en cada una de las mismas el menor o mayor elemento (Según sea el caso) su posición ideal. Al final de las N-1 pasadas los elementos del arreglo estarán ordenados.
Ejemplo: Arreglo {40,21,4,9,10,35}:
Primera pasada:{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.
{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.
{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.
Segunda pasada:{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.
{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.
{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.
Método de Ordenación
Método de Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
Método de Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.
Método de Inserción Directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada.
Método HeapSort:
El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.
Ejemplo en:
http://es.wikipedia.org/wiki/Heapsort
Método QuickSort: Este método se basa en la táctica "divide y vencerás", que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo.Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
Método MergeSort:
Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:
Dividir: Se divide el problema en partes más pequeñas.
Conquistar: Se resuelven recursivamente los problemas más chicos.
Combinar: Los problemas mas chicos de combinan para resolver el grande.
Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado. La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2) Pero : K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.
Método de Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.
Método de Inserción Directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada.
Método Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Método HeapSort:
El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.
Ejemplo en:
http://es.wikipedia.org/wiki/Heapsort
Método QuickSort: Este método se basa en la táctica "divide y vencerás", que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo.Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
Método MergeSort:
Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:
Dividir: Se divide el problema en partes más pequeñas.
Conquistar: Se resuelven recursivamente los problemas más chicos.
Combinar: Los problemas mas chicos de combinan para resolver el grande.
Mezcla.
Ordenación por mezcla (Merg Sort).
Intercalación de archivos ó mezcla de archivos.Por intercalación de archivos se entiende la unión o fusión de dos o más archivos ordenados de acuerdo con un determinado campo en un solo archivo.
Ejemplo:
A: 06 09 18 20 35
B: 10 16 25 28 66 82 87
C: 06 09 10 16 18 20 25 28 35 66 82 87
Monticulo:
Ordenación por el método de heapsort
El método de ordenación heapsort es también conocido con el nombre "montículo" en el mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautió así. Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de este algoritmo consiste en lo siguiente:
- Construir un montículo.
-Eliminar la raíza del montículo en forma repetida.
Definición. un montículo se define como "Para todo nodo del árbol se debe cumplir que su valor de cualquiera de sus hijos".
Para representar un montículo en un arreglo lineal:
El nodo k se almacena en la posición k correspondiente del arreglo.
El hijo izquierda del nodo k, se almacena en la posición 2 * k.
El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
Inserción de un elemento en un montículo.
La inserción de un elemento en un motnículo se lleva a cabo de la siguiente manera:
Se inserta el elemento en la primera posición disponible.
Se verifica si su valor es mayor que el de su padre. Si se cumple está condición entonces se efectúa el intercambio. Sino se cumple está condición, entonces, el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo. Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.
METODO RADIX
El siguiente método que consideramos se denomina ordenamiento de raíz. Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Por ejemplo, el numero 235 es en notación decimal que se escribe con un 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades. El mas grande de dos enteros de igual longitud se determina del modo siguiente: empezar en el digito mas significativo y avanzar por los dígitos menos significativos mientras coincidan los dígitos correspondientes en los dos números. El numero con el digito mas grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos. Por supuesto, si coinciden todos los dígitos de ambos números, los números son iguales.
Búsqueda por hash
Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado. La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2) Pero : K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.
Suscribirse a:
Entradas (Atom)
