Algoritmos de ordenación en C

Algoritmos de ordenación en C

Vamos a dedicar ésta publicación a describir algunos algoritmos de ordenación en C. Veremos los métodos de la burbuja, de inserción y el de quicksort.

Estos algoritmos son, quizás, lo más útiles y comunes en programación. Su objetivo principal es el de faciltar la búsqueda de uno o más elementos de un conjunto de datos.

algoritmo bubble sort

Éste método se aplica para ordenar un conjunto de datos de forma ascendente o descendente. En un algoritmo muy sencillo. A cambio, éste procedimiento exigen una gran cantidad de tiempo de procesamiento.

void burbuja (int tabla[], int n){

	int k, nuevapos, aux, encontrado;

	for (k=1; k<n; k++){
		aux = tabla [k];
		encontrado = 0;
		while ((k>0) &amp;&amp; (!encontrado)) {
			if (tabla[k-1] > aux) {
				tabla [k] = tabla [k-1];
				k--;
			}
			else encontrado = 1;
		} /*del while*/
		nuevapos = k;
		tabla [nuevapos] = aux;
	} /*del for*/
}

algoritmo quicksort

El algoritmo quicksort es el más rápido de los tres que tenemos en ésta publicación, y el que menos recursos precisa. Realmente es un algoritmo que usa la técnica divide y vencerás. La idea se basa en la partición de la lista a ordenar.

void qs(int lista[],int limite_izq,int limite_der)
	{
	    int izq,der,temporal,pivote;
	    izq=limite_izq;
	    der = limite_der;
	    pivote = lista[(izq+der)/2];

	    do{
	        while(lista[izq]<pivote &amp;&amp; izq<limite_der)izq++;
	        while(pivote<lista[der] &amp;&amp; der > limite_izq)der--;
	        if(izq <=der)
	        {
	            temporal= lista[izq];
	            lista[izq]=lista[der];
	            lista[der]=temporal;
	            izq++;
	            der--; 
	        }

	    }while(izq<=der);
	    if(limite_izq<der){qs(lista,limite_izq,der);}
	    if(limite_der>izq){qs(lista,izq,limite_der);}
	}

algoritmo de insert sort

Consiste en ordenar los dos primeros elementos de la lista, luego se inserta el tercer elemento en la posición correcta respecto a los dos primeros. A continuación se inserta el cuarto elemento en la posición correcta respecto a los tres primeros.

void insertionSort(int arr[], int n)  
{  
    int i, key, j;  
    for (i = 1; i < n; i++) 
    {  
        key = arr[i];  
        j = i - 1;  
  
        /* Move elements of arr[0..i-1], that are  
        greater than key, to one position ahead  
        of their current position */
        while (j >= 0 &amp;&amp; arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}  

Para éste algoritmo, es necesario una serie de funciones y procedimientos auxiliares que os dejo a continuación:

void printArray(int arr[], int n)  
{  
    int i;  
    for (i = 0; i < n; i++)  
        cout << arr[i] << " ";  
    cout << endl; 
}  
  
int main()  
{  
    int arr[] = { 12, 11, 13, 5, 6 };  
    int n = sizeof(arr) / sizeof(arr[0]);  
  
    insertionSort(arr, n);  
    printArray(arr, n);  
  
    return 0;  
}  

En posteriores artículos iremos dejando más ejemplos de algoritmos de ordenación.

No Comments

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.