Algoritmos de ordenamiento, código en C
En la entrada de esta semana se dará una pequeña extensión del tema tratado la semana anterior, esto con la intención de ampliar el contenido del blog. Como la semana pasada se habló sobre algoritmos de ordenamiento y se presentaron códigos de estos, pero en lenguaje Python esta semana ampliaremos esto mostrando los códigos en lenguaje C. Además, podremos así observar la diferencia de manejo de estructuras que hay entre estos lenguajes.
Los códigos presentados son tomados
documento.cap6. “Algoritmos de búsqueda y ordenamiento”.
El primer algoritmo es el algoritmo de selección:
void ordSeleccion (double a [], int
n) {
int
indiceMenor, i, j;
/* ordenar a[0]..a[n-2] y a[n-1] en cada
pasada */
for (i = 0; i < n-1; i++) {
/* comienzo de la exploración en índice i */
indiceMenor
= i;
/* j explora la sublista a[i+1]..a[n-1] */
for
(j = i+1; j < n; j++)
if (a[j] < a[indiceMenor]) indiceMenor
= j;
/* sitúa el elemento más pequeño en a[i]
*/
if (i ! = indiceMenor) {
double aux = a[i];
a[i] = a[indiceMenor];
a[indiceMenor] = aux ;
}
}
}
Algoritmo inserción:
void ordInsercion (int [] a, int n) {
int i, j;
int aux;
for (i = 1; i < n; i++) {
/*
índice j explora la sublista a[i-1] ..a[0] buscando la posición correcta del
elemento destino, lo asigna a a[j] */
j
= i;
aux = a[i];
/* se localiza el punto de inserción
explorando hacia abajo */
while (j > 0 && aux <
a[j-1]) {
/* desplazar elementos hacia arriba para
hacer espacio */
a[j] = a[j-1];
j--;
}
a[j] = aux;
}
}
Algoritmo burbuja:
void ordBurbuja (long a [], int n) {
int interruptor = 1;
int pasada, j;
for (pasada = 0; pasada < n-1
&& interruptor; pasada++) {
/* bucle externo controla la cantidad de
pasadas */
interruptor = 0;
for (j = 0; j < n-pasada-1; j++)
if (a[j] > a[j+1]) {
/*elementos desordenados, es necesario
intercambio*/
long
aux;
interruptor = 1;
aux = a[j];
a[j] = a[j+1];
a[j+1] = aux;
}
}
}
Algoritmo
Quicksort:
void quicksort(double a[], int
primero, int ultimo) {
int i, j, central;
double pivote;
central = (primero + ultimo) /2;
pivote = a[central];
i = primero;
j = ultimo;
do {
while (a[i] < pivote) i++;
while (a[j] > pivote) j--;
if
(i<=j) {
double tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp; /* intercambia a[i] con a[j]
*/
i++;
j--;
}
}
while (i <= j);
if (primero < j)
quicksort (a, primero, j);/* mismo proceso
con sublista izqda */
if (i < ultimo)
quicksort (a, i, ultimo); /* mismo proceso
con sublista drcha */
}
Luego de observar estos códigos y la forma
en la que funcionan, nos permite ver las grandes diferencias entre la codificación
de las estructuras de datos en el lenguaje Python y el lenguaje C.
Fuentes:
http://novella.mhhe.com/sites/dl/free/844814077x/619434/A06.pdf
Comentarios
Publicar un comentario