Programación C: algoritmos de ordenamiento, búsqueda y apuntadores
Último artículo sobre la serie de programación C, con una vuelta a las estructuras de datos que ya se vieron en artículos anteriores, como los registros, arreglos, etc. Pero en esta ocasión, para ir un poco más allá y acercarte a los algoritmos de ordenamiento y búsqueda, y a los apuntadores.
Una forma de poder agregar métodos a tu programa para ordenar datos y buscar información, o manejar la memoria de forma eficiente para facilitar la manipulación de datos durante la programación…
ÍNDICE:
Ordenación
En programación con C hay recursos para poder clasificar los datos de los ficheros o arreglos. Por ejemplo, se puede usar un orden ascendente o descendente por su valor numérico, alfabéticamente, etc.
En función del tipo de elemento a ordenar, se puede distinguir entre:
- Interna: (véase siguiente apartado)
- Externa: es más lenta que la interna, ya que los datos a ordenar se encuentran fuera, como en un fichero.
Ordenación interna
En este tipo, los datos se encuentran en memoria, como pueden ser listas, arreglos, etc., para su acceso aleatorio o directo. Además, existen varios métodos de ordenación que se pueden agrupar en:
- Directo: son métodos más simples como:
- Burbuja (bubble sort): se comparan pares de elementos contiguos y se intercambian, comenzando desde el inicio hasta la última posición en orden ascendente. Su nombre es bastante intuitivo, ya que el elemento va elevándose poco a poco hasta ordenarse, como si de una burbuja ascendiendo a la superficie se tratase. Por ejemplo, imagina que en el siguiente ejemplo introduces los valores 4, 3, 5, 2, 1. En este caso, compararía 4-3, y pondría a 3 en primera posición (3,4,5,2,1). Luego pasaría a comparar 5-2 y pondría 2 delante de 5 (3,4,2,5,1). Lo siguiente es comparar 5-1 y pondría 1 delante (3,4,2,1,5). Luego se seguirían dando pasadas hasta dejarlo (1,2,3,4,5).
#include <stdio.h>
void burbuja(long [], long);
int main()
{
long arreglo[5], n, c;
printf("Introduce el número de elementos del arreglo\n");
scanf("%ld", &n);
printf("Introduce %ld enteros\n", n);
for (c = 0; c < n; c++)
scanf("%ld", &arreglo[c]);
burbuja(arreglo, n);
printf("Ordenar la lista en orden ascendente:\n");
for (c = 0; c < n; c++)
printf("%ld\n", arreglo[c]);
return 0;
}
void burbuja(long lista[], long n)
{
long c, d, t;
for (c = 0 ; c < n - 1; c++) {
for (d = 0 ; d < n - c - 1; d++) {
if (lista[d] > lista[d+1]) {
/* Intercambio */
t = lista[d];
list[d] = lista[d+1];
list[d+1] = t;
}
}
}
}
-
- Selección (selection sort): se buscará el elemento menor del vector de datos y se intercambia este con la primera posición. Luego se busca el segundo elemento más pequeño y se intercambia con la segunda posición, y así sucesivamente hasta completarlos todos. Si se siguiese el mismo ejemplo anterior, con (4, 3, 5, 2, 1), comenzaría a intercambiando 4 por 1 (1,3,5,2,4), luego 3 por 2 (1,2,5,3,4), luego (1,2,3,5,4) y finalizar con (1,2,3,4,5).
#include <stdio.h>
int main()
{
int arreglo[5], n, c, d, posicion, t;
printf("Introduce el número de elementos\n");
scanf("%d", &n);
printf("Introduce %d enteros\n", n);
for (c = 0; c < n; c++)
scanf("%d", &arreglo[c]);
for (c = 0; c < (n - 1); c++) // Encontrar el elemento mínimo
{
position = c;
for (d = c + 1; d < n; d++)
{
if (arreglo[posicion] > arreglo[d])
posicion = d;
}
if (posicion != c)
{
t = arreglo[c];
arreglo[c] = arreglo[posicion];
arreglo[posicion] = t;
}
}
printf("Lista ordenada ascendentemente:\n");
for (c = 0; c < n; c++)
printf("%d\n", arreglo[c]);
return 0;
}
-
- Inserción directa o baraja (direct insertion sort): se inserta cada nuevo elemento para hacer que la lista resultante quede ya ordenada.
#include <stdio.h>
int main()
{
int n, arreglo[5], c, d, t, flag = 0;
printf("Introduce el número de elementos\n");
scanf("%d", &n);
printf("Introduce %d enteros\n", n);
for (c = 0; c < n; c++)
scanf("%d", &arreglo[c]);
for (c = 1 ; c <= n - 1; c++) {
t = arreglo[c];
for (d = c - 1 ; d >= 0; d--) {
if (arreglo[d] > t) {
arreglo[d+1] = arreglo[d];
flag = 1;
}
else
break;
}
if (flag)
arreglo[d+1] = t;
}
printf("La lista ordenada ascendentemente es:\n");
for (c = 0; c <= n - 1; c++) {
printf("%d\n", arreglo[c]);
}
return 0;
}
- Indirecto: métodos avanzados, como los algoritmos:
- Ordenación por mezcla (merge sort): si la longitud de la lista de datos es 0 o 1, entonces lo da por ordenado. En cualquier otro caso, divide la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño. Luego ordena cada sublista recursivamente y mezcla las dos sublistas en una sola ordenada.
#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf("Introduce el número de elementos:");
scanf("%d",&n);
printf("Introduce los elementos:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nLa lista ordenada es:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void mergesort(int a[],int i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid); //Recursión a la izquierda
mergesort(a,mid+1,j); //Recursión a la derecha
merge(a,i,mid,mid+1,j); //Dos sublistas
}
}
void merge(int a[],int i1,int j1,int i2,int j2)
{
int temp[50]; //Arreglo usado para la mezcla
int i,j,k;
i=i1; //Comenzando por la primera lista
j=i2; //Comenzando por la segunda lista
k=0;
while(i<=j1 && j<=j2) //mientras haya elementos en ambas
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1) //copiando elementos restantes de la primera lista
temp[k++]=a[i++];
while(j<=j2) //copiando elementos restantes de la segunda lista
temp[k++]=a[j++];
//Transfiriendo elementos
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}
-
- Ordenación rápida (quick sort): se selecciona un elemento del conjunto a ordenar denominado pivote. Luego se re-sitúan todos los demás elementos de la lista menores que él a un lado, y los mayores que él al otro. Eso hace que la lista quede formada por dos partes, una a la izquierda del pivote y otra a la derecha, como las sublistas del caso anterior. Luego se repetirá el proceso de forma recursiva para cada sublista hasta que mientras que éstas contengan más de un elemento. Una vez terminen, estarán todos ordenados.
#include<stdio.h>
#include<conio.h>
#define MAX_SIZE 5
void quick_sort(int, int);
int arreglo[MAX_SIZE];
int main() {
int i;
printf("\nIntroduce %d elementos a ordenar\n", MAX_SIZE);
for (i = 0; i < MAX_SIZE; i++)
scanf("%d", &arreglo[i]);
printf("\nTus datos:");
for (i = 0; i < MAX_SIZE; i++) {
printf("\t%d", arreglo[i]);
}
quick_sort(0, MAX_SIZE - 1);
printf("\n\nLista ordenada:");
for (i = 0; i < MAX_SIZE; i++) {
printf("\t%d", arreglo[i]);
}
getch();
}
void quick_sort(int f, int l) {
int i, j, t, p = 0;
if (f < l) {
p = f;
i = f;
j = l;
while (i < j) {
while (arreglo[i] <= arreglo[p] && i < l)
i++;
while (arreglo[j] > arreglo[p])
j--;
if (i < j) {
t = arreglo[i];
arreglo[i] = arreglo[j];
arreglo[j] = t;
}
}
t = arreglo[p];
arreglo[p] = arreglo[j];
arreglo[j] = t;
quick_sort(f, j - 1);
quick_sort(j + 1, l);
}
}
-
- Shell sort: se emplea cuando el número de elementos a ordenar es muy grande. En él se van comparando varios elementos que distan uno del otro (salto de n/2, siendo n el número de elementos). Así se irán dando pasadas hasta que no se intercambie ningún elemento de sitio. En ese instante, 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 valga 1.
#include <stdio.h>
void shell(int arreglo[], int num)
{
int i, j, k, tmp;
for (i = num / 2; i > 0; i = i / 2)
{
for (j = i; j < num; j++)
{
for(k = j - i; k >= 0; k = k - i)
{
if (arreglo[k+i] >= arreglo[k])
break;
else
{
tmp = arreglo[k];
arreglo[k] = arreglo[k+i];
arreglo[k+i] = tmp;
}
}
}
}
}
int main()
{
int arreglo[30];
int k, num;
printf("Introduce el total de elementos: ");
scanf("%d", &num);
printf("\nIntroduce %d enteros: ", num);
for (k = 0 ; k < num; k++)
{
scanf("%d", &arreglo[k]);
}
shell(arreglo, num);
printf("\n La lista ordenada es: ");
for (k = 0; k < num; k++)
printf("%d ", arreglo[k]);
return 0;
}
Búsqueda
En cuanto a los métodos de búsqueda de elementos o datos, también se puede diferenciar entre:
- Secuencial o lineal (linear search): es un método muy simple, y es recorrer el vector desde el inicio hasta la última posición, de uno en uno. Si se encuentra el resultado, será devuelta la posición donde estaba el elemento localizado, de lo contrario se devuelve 0.
#include <stdio.h>
int main()
{
int arreglo[5], search, c, n;
printf("Introduce el número de elementos\n");
scanf("%d", &n);
printf("Introduce %d enteros\n", n);
for (c = 0; c < n; c++)
scanf("%d", &arreglo[c]);
printf("Introduce un número a buscar\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (arreglo[c] == search) /* Si el elemento requerido es encontrado */
{
printf("%d es la localización %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d no está presente en el areglo.\n", search);
return 0;
}
- Binaria (binary searh): el anterior método tiene problemas cuando se trata de un vector de datos muy grande y los datos se encuentran sobre el final. En este otro método se obtiene mayor rapidez. Para eso, se debe partir de un vector ya ordenado, luego se divide a la mitad, comparando el elemento central con el buscado. Si es igual, el valor se ha encontrado. Si es menor, se busca a la izquierda, y si es mayor a la derecha.
#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, arreglo[5];
printf("Introduce el número de elementos\n");
scanf("%d", &n);
printf("Introduce %d enteros\n", n);
for (c = 0; c < n; c++)
scanf("%d", &arreglo[c]);
printf("Introduce el valor a buscar\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (arreglo[middle] < search)
first = middle + 1;
else if (arreglo[middle] == search) {
printf("%d encontrado en la localización %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("No encontrado. %d no está presente en la lista.\n", search);
return 0;
}
Apuntadores
Por último, los apuntadores, o punteros, no son más que variables que contienen una dirección de memoria que apunta hacia alguno de los valores de los vectores de datos.
La dirección de la variable será un número hexadecimal, y como curiosidad, decir que lo puedes obtener muy fácilmente. Por ejemplo, imagina que tienes la variable entera num y quieres saber el código hexadecimal (x) en el que se almacena. Para ello puedes emplear &:
int num;
printf("La dirección de num es: %x", &num):
Para declarar el puntero, se puede usar el tipo de apuntador y * seguido del nombre del apuntador. Por ejemplo:
//Algunos ejemplos de declaración de punteros de diferentes tipos: int num = 4; int *puntero1, *puntero2; char *caracter1; float *flotante1;
Además, también se le puede asignar a un puntero direcciones de variables a través del unario &, o incluso direcciones almacenadas en otros punteros, así como apuntadores hacia otros apuntadores… Por ejemplo:
int num = 4;
int *puntero1, *puntero2;
//Asignar a puntero1 la dirección de num
puntero1 = #
//Asignar a puntero2 la dirección almacenada en puntero1
puntero2 = puntero1;
//Para obtener el valor se puede usar *, en este caso devuelve 4:
int num = 4;
int *puntero1;
puntero1 = #
printf("El valor de num es: %d",*puntero1);
//Incluso se pueden realizar operaciones, por ejemplo, para obtener 8:
int num = 4, num2;
int *puntero1;
puntero1 = #
num2 = *puntero1 * 2;
printf("El valor de num2 es: %d", num2);
//Ejemplos de punteros a otros punteros, usando tantos * como sea necesario
int num = 1;
int *punteroA = #
int **punteroB = &punteroA:
int ***punteroC = &punteroB;
Jo .. que recuerdos … de cuando los discos eran de 5,1/4 …