Fundamentos de Programación: 2012

Método de ordenamiento por Selección

El ordenamiento por selección (Selection Sort) es un algoritmo de ordenamiento que requiere O $(n^2)$ operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

Buscar el mínimo elemento de la lista
Intercambiarlo con el primero
Buscar el mínimo en el resto de la lista
Intercambiarlo con el segundo

Y en general:

Buscar el mínimo elemento entre una posición i y el final de la lista
Intercambiar el mínimo con el elemento de la posición i

Ejemplo en c++:

#include <iostream>
#include <vector>
using namespace std;
 
 
template <class T>
void ordena_seleccion(vector<T>& v) {
    for (int i = 0; i < v.size(); ++i) {
        int min = i;
        for (int c = i + 1; c < v.size(); ++c) {
            if (v[min] > v[c]) min = c;
        }
        T aux = v[i];
        v[i] = v[min];
        v[min] = aux;
    }
}

Método de ordenación Merge Sort

El algoritmo de ordenamiento por mezcla (merge sort) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de Complejidad O(nlog n).

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.

Los algoritmos que utilizan este principio son en la mayoría de los casos netamente recursivos como es el caso de mergesort.

El algoritmo de Mergesort es un ejemplo clásico de algoritmo que utiliza el principio de dividir para conquistar. Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas.

Ejemplo en c++:

// En el código usamos la clase vector (#include <vector.h>) para crear los vectores,
// obviamente funciona igual de bien si se utilizan los arrays tipo C: TIPO V[]
template <class T, class U>
void fusiona(vector<T>& v, U ini, U med, U fin) {
    vector<T> aux(fin - ini + 1);
    int i = ini; // Índice de la parte izquierda
    int j = med + 1; // Índice de la parte derecha
    int k = 0; // Índice del vector aux
 
 
    /* Mientras ninguno de los indices llegue a su fin vamos realizando
       comparaciones. El elemento más pequeño se copia al vector aux */
    while (i <= med && j <= fin) {
        if (v[i] < v[j]) {
            aux[k] = v[i];
            i++;
        }
        else {
            aux[k] = v[j];
            j++;
        }
        k++;
    }
 
    /* Uno de los dos sub-vectores ya ha sido copiado del todo, simplemente
       debemos copiar todo el sub-vector que nos falte */
    while (i <= med) {
        aux[k] = v[i];
        i++;
        k++;
    }
 
    while (j <= fin) {
        aux[k] = v[j];
        j++;
        k++;
    }
 
    /* Copiamos los elementos ordenados de aux al vector original v */
    for (int n = 0; n < aux.size(); ++n) v[ini + n] = aux[n];
}
 
template <class T, class U>
void merge_sort(vector<T>& v, U ini, U fin) {
    /* Si ini = fin el sub-vector es de un solo elemento y, por lo tanto
       ya está ordenado por definición */
    if (ini < fin) {
/*Considerar que el valor de med siempre es redondeado hacia abajo.*/
        int med = (ini + fin)/2;
        merge_sort(v, ini, med);
        merge_sort(v, med + 1, fin);
        fusiona(v, ini, med, fin);
    }
}

Método de ordenación por inserción

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elementok+1 debiendo desplazarse los demás elementos.

Ejemplo en c++:

template <class T> void insertionSort(std::vector<T>& v, int fin) {
    int i, j, index;
    for (i=1; i <fin; i++)
 {
        index = v.at(i);
        j = i-1;
        while (j >= 0 && v.at(j)>index) {
            v.at(j+1)=v.at(j);
            j--;
        }
        v.erase(v.begin()+j+1);
        v.insert(v.begin()+j+1,index);
    }
}

Método de ordenación Shell

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados. El numero de operaciones necesarias es O(n^1.25).

Ejemplo en c++:

#include< stdio.h>
#include< conio.h>

void shellsort(int a[],int n)
{
int j,i,k,m,mid;
for(m = n/2;m>0;m/=2)
{
for(j = m;j< n;j++)
{
for(i=j-m;i>=0;i-=m)
{
if(a[i+m]>=a[i])
break;
else
{
mid = a[i];
a[i] = a[i+m];
a[i+m] = mid;
}
}
}
}
}

main()
{
int a[10],i,n;
clrscr();

printf("Ingrese numero de elementos\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElemento %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nVector antes de ordenar : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
shellsort(a,n);

printf("\nVector luego de ordenar : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT

Ingrese numero de elementos : 5
Elemento 1 : 21
Elemento 2 : 36
Elemento 3 : 54
Elemento 4 : 2
Elemento 5 : 0

Vector antes de ordenar : 21 36 54 2 0
Vector luego de ordenar : 0 2 21 36 54
*/

Metodo de ordenamiento Sort o Inserción

Gráficamente:

Ejemplo en c++:

template <class T> void insertionSort(std::vector<T>& v, int fin) {
    int i, j, index;
    for (i=1; i <fin; i++)
 {
        index = v.at(i);
        j = i-1;
        while (j >= 0 && v.at(j)>index) {
            v.at(j+1)=v.at(j);
            j--;
        }
        v.erase(v.begin()+j+1);
        v.insert(v.begin()+j+1,index);
    }
}

Método de ordenación burbuja

La Ordenación 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.

Ejemplo en c++:

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] );
}

Tipos de ordenamiento de vectores

Ordenamiento interno.
Se lleva a cabo completamente en memoria principal. Todos los objetos que se ordenan caben en la memoria principal de la computadora.

Ordenamiento externo.
No cabe toda la información en memoria principal y es necesario ocupar memoria secundaria. El ordenamiento ocurre transfiriendo bloques de información a memoria principal en donde se ordena el bloque y este es regresado, ya ordenado, a la memoria secundaria.

Hay métodos muy simples de implementar que son útiles en los casos en donde el número de elementos a ordenar no es muy grande. Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son más eficientes en cuestión de tiempo de ejecución. La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, tomandose a n como el número de elementos que tiene el arreglo a ordenar.

lunes, 10 de septiembre de 2012