Algoritmo de ordenamiento

Solo disponible en BuenasTareas
  • Páginas : 5 (1007 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de noviembre de 2010
Leer documento completo
Vista previa del texto
METODOS DE ORDENAMIENTOS
Método de Burbujeo
Una pasada por la ordenación de burbujeo consiste en un recorrido completo a través del arreglo, en el que se comparan los contenidos de las casillas adyacentes, y se cambian si no están en orden. La ordenación por burbujeo completa consiste en una serie de pasadas ("burbujeo") que termina con una en la que ya no se hacen cambios porque todo está enorden.
void Burbujeo( int A[], int n)
{
int i,j;
for( i=0; i < n-1; i++ )
for( j=n-1; j > i; j--)
if( A[j] < A[j-1] )
Intercambia( &A[j], &A[j-1] );

void Burbujeo( int A[], int n)
{
int i,j;
for( i=0; i < n-1; i++ )
for( j=n-1; j > i; j--)
if( A[j] < A[j-1] )
Intercambia( &A[j], &A[j-1] );
}

Método de Selección
Los métodos de ordenación porselección se basan 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.
A diferencia del método de la burbuja, 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.

Método de Inserción
El fundamento de este método consiste en insertarlos elementos no ordenados del arreglo en subarreglos del mismo que ya estén ordenados. Dependiendo del método elegido para encontrar la posición de inserción tendremos distintas versiones del método de inserción.

Lista de algoritmos de ordenamiento
Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional.
Estables |
Nombre traducido |Nombre original | Complejidad | Memoria | Método |
Ordenamiento de burbuja | Bubblesort | O(n²) | O(1) | Intercambio |
Ordenamiento de burbuja bidireccional | Cocktail sort | O(n²) | O(1) | Intercambio |
Ordenamiento por inserción | Insertion sort | O(n²) | O(1) | Inserción |
Ordenamiento por casilleros | Bucket sort | O(n) | O(n) | No comparativo |
Ordenamiento por cuentas | Counting sort| O(n+k) | O(n+k) | No comparativo |
Ordenamiento por mezcla | Merge sort | O(n log n) | O(n) | Mezcla |
Ordenamiento con árbol binario | Binary tree sort | O(n log n) | O(n) | Inserción |
| Pigeonhole sort | O(n+k) | O(k) | |
Ordenamiento Radix | Radix sort | O(nk) | O(n) | No comparativo |
| Distribution sort | O(n³) versión recursiva | O(n²) | |
| Gnome sort | O(n²) | | |Inestables |
Nombre traducido | Nombre original | Complejidad | Memoria | Método |
Ordenamiento Shell | Shell sort | O(n1.25) | O(1) | Inserción |
| Comb sort | O(n log n) | O(1) | Intercambio |
Ordenamiento por selección | Selection sort | O(n²) | O(1) | Selección |
Ordenamiento por montículos | Heapsort | O(n log n) | O(1) | Selección |
| Smoothsort | O(n log n) | O(1) | Selección|
Ordenamiento rápido | Quicksort | Promedio: O(n log n),
peor caso: O(n²) | O(log n) | Partición |
| Several Unique Sort | Promedio: O(n u),
peor caso: O(n²);
u=n; u = número único de registros | | |
Cuestionables, imprácticos |
Nombre traducido | Nombre original | Complejidad | Memoria | Método |
| Bogosort | O(n × n!), peor: no termina | | |
| Pancake sorting | O(n),excepto en
máquinas de Von Neumann | | |
| Randomsort | | | |

METODOS DE BUSQUEDA
Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o la mejor movida en una partida de ajedrez.
La variante más simple del problema esla búsqueda de un número en un vector.
Búsqueda secuencial
Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del array hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no...
tracking img