Leer números de archivo con C y comparar métodos de ordenamiento

Leer 10 mil números y ordenar con C

Dejar un comentario / Ejercicios resueltos, Lenguaje de programación C / Por

En el ejercicio de programación de hoy vamos a trabajar con ANSI C para leer 10000 (diez mil) números de un archivo de texto y ordenarlos usando varios algoritmos, los cuales son:

  • Selección
  • Inserción
  • Burbuja
  • Rápido (Quicksort)
  • Mezcla (Merge)

Vamos a leer el archivo usando fgets y convertir cada número con atol, luego vamos a rellenar un arreglo con esos números (hasta una cierta cantidad de números) y ordenarlos comparando los tiempos de ejecución de cada algoritmo.

Leer números de archivo con C y comparar métodos de ordenamiento
Leer números de archivo con C y comparar métodos de ordenamiento

Descripción del ejercicio

Este ejercicio de programación con C dice así:

Hacer un código de ordenamiento de selección, inserción, burbuja, mezcla y rápido, en el cual cada uno lea 1000, 5000 y finalmente los 10000 números que vienen en el archivo, también debe incluir un código el cual muestre el tiempo que tarda cada método de ordenamiento en ordenar 1000, luego 5000 y finalmente 10000 los 10000.

Los 1000, 5000 y 10000 deben ser números del archivo de los diez mil números.

Comencemos viendo la implementación de cada algoritmo y más adelante veremos cómo llenar un arreglo hasta cierto límite leyendo un archivo de texto así como medir el tiempo de ejecución.

Una salida de ejemplo sería:

Leyendo 1000 numeros...

Seleccion: 0.0020000000 segundos.
Insercion: 0.0010000000 segundos.
Burbuja: 0.0030000000 segundos.
Mezcla: 0.0000000000 segundos.
Rapido: 0.0000000000 segundos.


Leyendo 5000 numeros...

Seleccion: 0.0500000000 segundos.
Insercion: 0.0290000000 segundos.
Burbuja: 0.0820000000 segundos.
Mezcla: 0.0010000000 segundos.
Rapido: 0.0000000000 segundos.


Leyendo 10000 numeros...

Seleccion: 0.2170000000 segundos.
Insercion: 0.1140000000 segundos.
Burbuja: 0.3650000000 segundos.
Mezcla: 0.0020000000 segundos.
Rapido: 0.0010000000 segundos.

Selección – Algoritmo en C

void seleccion(int arreglo[], int longitud)
{
    for (int i = 0; i < longitud - 1; i++)
    {
        for (int j = i + 1; j < longitud; j++)
        {

            if (arreglo[i] > arreglo[j])
            {
                intercambiar(&arreglo[i], &arreglo[j]);
            }
        }
    }
}

Fíjate que se está invocando a una función para intercambiar los valores a través de sus referencias:

void intercambiar(int *a, int *b)
{
    int temporal = *a;
    *a = *b;
    *b = temporal;
}

Ordenamiento por inserción

void insercion(int arreglo[], int longitud)
{
    int i = 1;
    while (i < longitud)
    {
        int j = i;
        while (j > 0 && arreglo[j - 1] > arreglo[j])
        {
            intercambiar(&arreglo[j], &arreglo[j - 1]);
            j--;
        }
        i++;
    }
}

De nuevo se está invocando a la función que intercambia los elementos del arreglo para ordenar los números usando el algoritmo de inserción.

Ordenar arreglo en C con método de burbuja

void burbuja(int arreglo[], int longitud)
{
    for (int x = 0; x < longitud; x++)
    {
        for (int indiceActual = 0; indiceActual < longitud - 1;
             indiceActual++)
        {
            int indiceSiguienteElemento = indiceActual + 1;
            if (arreglo[indiceActual] > arreglo[indiceSiguienteElemento])
            {
                intercambiar(&arreglo[indiceActual], &arreglo[indiceSiguienteElemento]);
            }
        }
    }
}

Merge sort en C

Veamos el ordenamiento por mezcla en C:

void mezcla(int arreglo[], int longitudArreglo)
{
    if (longitudArreglo < 2)
    {
        return;
    }

    int mitad = longitudArreglo / 2;
    int mitadIzquierda[mitad];
    int mitadDerecha[longitudArreglo - mitad];

    for (int i = 0; i < mitad; i++)
    {
        mitadIzquierda[i] = arreglo[i];
    }
    for (int i = mitad; i < longitudArreglo; i++)
    {
        mitadDerecha[i - mitad] = arreglo[i];
    }
    mezcla(mitadIzquierda, mitad);
    mezcla(mitadDerecha, longitudArreglo - mitad);
    combinar(arreglo, mitadIzquierda, mitad, mitadDerecha, longitudArreglo - mitad);
}

El algoritmo de mezcla en ANSI C se invoca recursivamente y después combina los arreglos:

void combinar(int arreglo[], int mitadIzquierda[], int longitudArregloIzquierdo, int mitadDerecha[], int longitudArregloDerecho)
{
    int indiceArregloIzquierdo = 0;
    int indiceArregloDerecho = 0;
    int indiceArregloCombinado = 0;

    while (indiceArregloIzquierdo < longitudArregloIzquierdo && indiceArregloDerecho < longitudArregloDerecho)
    {
        if (mitadIzquierda[indiceArregloIzquierdo] <= mitadDerecha[indiceArregloDerecho])
        {
            arreglo[indiceArregloCombinado++] = mitadIzquierda[indiceArregloIzquierdo++];
        }
        else
        {
            arreglo[indiceArregloCombinado++] = mitadDerecha[indiceArregloDerecho++];
        }
    }
    while (indiceArregloIzquierdo < longitudArregloIzquierdo)
    {
        arreglo[indiceArregloCombinado++] = mitadIzquierda[indiceArregloIzquierdo++];
    }

    while (indiceArregloDerecho < longitudArregloDerecho)
    {
        arreglo[indiceArregloCombinado++] = mitadDerecha[indiceArregloDerecho++];
    }
}

Quicksort con ANSI C

El último algoritmo que nos falta revisar es el algoritmo de ordenamiento rápido, también llamado quicksort:

void rapido(int arreglo[], int izquierda, int derecha)
{
    if (izquierda < derecha)
    {
        int indiceParticion = particion(arreglo, izquierda, derecha);
        rapido(arreglo, izquierda, indiceParticion);
        rapido(arreglo, indiceParticion + 1, derecha);
    }
}

Mismo que necesita una función para encontrar el índice en donde el arreglo debe ser dividido:

int particion(int arreglo[], int izquierda, int derecha)
{
    int pivote = arreglo[izquierda];
    while (1)
    {
        while (arreglo[izquierda] < pivote)
        {
            izquierda++;
        }
        while (arreglo[derecha] > pivote)
        {
            derecha--;
        }
        if (izquierda >= derecha)
        {
            return derecha;
        }
        else
        {
            intercambiar(&arreglo[izquierda], &arreglo[derecha]);
            izquierda++;
            derecha--;
        }
    }
}

Rellenar arreglo

Te he mostrado todos los métodos para ordenar un arreglo en el lenguaje de programación C, pero para ordenar esos arrays hay que llenarlos primero, para ello tengo la siguiente función que recibe la cantidad de números que se leerán del archivo de texto:

void rellenarArregloConNumeros(int *arreglo, int cantidadNumeros)
{
    char buferArchivo[MAXIMA_LONGITUD_CADENA];
    FILE *archivo = fopen(NOMBRE_ARCHIVO, "r");
    if (archivo == NULL)
    {
        printf("No se puede abrir el archivo");
        return;
    }
    for (int i = 0; i < cantidadNumeros; i++)
    {
        if (fgets(buferArchivo, MAXIMA_LONGITUD_CADENA, archivo) == NULL)
        {
            break;
        }
        strtok(buferArchivo, "\n");
        arreglo[i] = atol(buferArchivo);
    }
    fclose(archivo);
}

Con la función strtok removemos el salto de línea, y luego usamos atol para convertir la línea recién leída en entero. Debido a que no conocemos la cantidad de números en tiempo de ejecución estoy usando malloc para crear el array dinámico:

int *arreglo = malloc(cantidadNumeros * sizeof(int));

Finalmente veamos la función que rellena el array, lo ordena y mide el tiempo usando clock_t:

void ordenarEImprimirResultados(int cantidadNumeros, int imprimirArreglo)
{
    clock_t t_inicio, t_final;
    double t_intervalo;
    int *arreglo = malloc(cantidadNumeros * sizeof(int));
    if (arreglo == NULL)
    {
        printf("Error asignando memoria");
    }

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    seleccion(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nSeleccion: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    insercion(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nInsercion: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    burbuja(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nBurbuja: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    mezcla(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nMezcla: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    rapido(arreglo, 0, cantidadNumeros - 1);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nRapido: %.10f segundos.", t_intervalo);
    printf("\n");
    if (imprimirArreglo)
    {
        for (int x = 0; x < cantidadNumeros; x++)
        {
            printf("A[%d]=%d\n", x, arreglo[x]);
        }
    }
    free(arreglo);
}

Poniendo todo junto

El código completo queda como se ve a continuación:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAXIMA_LONGITUD_CADENA 1000
#define NOMBRE_ARCHIVO "10mil_numeros.txt"

void intercambiar(int *a, int *b);
void seleccion(int arreglo[], int longitud);
void insercion(int arreglo[], int longitud);
void burbuja(int arreglo[], int longitud);
void rapido(int arreglo[], int izquierda, int derecha);
int particion(int arreglo[], int izquierda, int derecha);
void mezcla(int arreglo[], int longitudArreglo);
void combinar(int arreglo[], int mitadIzquierda[], int longitudArregloIzquierdo, int mitadDerecha[], int longitudArregloDerecho);
void rellenarArregloConNumeros(int *arreglo, int cantidadNumeros);
void ordenarEImprimirResultados(int cantidadNumeros, int imprimirArreglo);

int main()
{
    int cantidades[] = {1000, 5000, 10000};
    for (int i = 0; i < sizeof(cantidades) / sizeof(int); i++)
    {
        printf("\n\nLeyendo %d numeros...\n", cantidades[i]);
        ordenarEImprimirResultados(cantidades[i], 0);
    }
    return 0;
}

void ordenarEImprimirResultados(int cantidadNumeros, int imprimirArreglo)
{
    clock_t t_inicio, t_final;
    double t_intervalo;
    int *arreglo = malloc(cantidadNumeros * sizeof(int));
    if (arreglo == NULL)
    {
        printf("Error asignando memoria");
    }

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    seleccion(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nSeleccion: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    insercion(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nInsercion: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    burbuja(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nBurbuja: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    mezcla(arreglo, cantidadNumeros);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nMezcla: %.10f segundos.", t_intervalo);

    rellenarArregloConNumeros(arreglo, cantidadNumeros);
    t_inicio = clock();
    rapido(arreglo, 0, cantidadNumeros - 1);
    t_final = clock();
    t_intervalo = (double)(t_final - t_inicio) / CLOCKS_PER_SEC;
    printf("\nRapido: %.10f segundos.", t_intervalo);
    printf("\n");
    if (imprimirArreglo)
    {
        for (int x = 0; x < cantidadNumeros; x++)
        {
            printf("A[%d]=%d\n", x, arreglo[x]);
        }
    }
    free(arreglo);
}

void rellenarArregloConNumeros(int *arreglo, int cantidadNumeros)
{
    char buferArchivo[MAXIMA_LONGITUD_CADENA];
    FILE *archivo = fopen(NOMBRE_ARCHIVO, "r");
    if (archivo == NULL)
    {
        printf("No se puede abrir el archivo");
        return;
    }
    for (int i = 0; i < cantidadNumeros; i++)
    {
        if (fgets(buferArchivo, MAXIMA_LONGITUD_CADENA, archivo) == NULL)
        {
            break;
        }
        strtok(buferArchivo, "\n");
        arreglo[i] = atol(buferArchivo);
    }
    fclose(archivo);
}

void mezcla(int arreglo[], int longitudArreglo)
{
    if (longitudArreglo < 2)
    {
        return;
    }

    int mitad = longitudArreglo / 2;
    int mitadIzquierda[mitad];
    int mitadDerecha[longitudArreglo - mitad];

    for (int i = 0; i < mitad; i++)
    {
        mitadIzquierda[i] = arreglo[i];
    }
    for (int i = mitad; i < longitudArreglo; i++)
    {
        mitadDerecha[i - mitad] = arreglo[i];
    }
    mezcla(mitadIzquierda, mitad);
    mezcla(mitadDerecha, longitudArreglo - mitad);
    combinar(arreglo, mitadIzquierda, mitad, mitadDerecha, longitudArreglo - mitad);
}

void combinar(int arreglo[], int mitadIzquierda[], int longitudArregloIzquierdo, int mitadDerecha[], int longitudArregloDerecho)
{
    int indiceArregloIzquierdo = 0;
    int indiceArregloDerecho = 0;
    int indiceArregloCombinado = 0;

    while (indiceArregloIzquierdo < longitudArregloIzquierdo && indiceArregloDerecho < longitudArregloDerecho)
    {
        if (mitadIzquierda[indiceArregloIzquierdo] <= mitadDerecha[indiceArregloDerecho])
        {
            arreglo[indiceArregloCombinado++] = mitadIzquierda[indiceArregloIzquierdo++];
        }
        else
        {
            arreglo[indiceArregloCombinado++] = mitadDerecha[indiceArregloDerecho++];
        }
    }
    while (indiceArregloIzquierdo < longitudArregloIzquierdo)
    {
        arreglo[indiceArregloCombinado++] = mitadIzquierda[indiceArregloIzquierdo++];
    }

    while (indiceArregloDerecho < longitudArregloDerecho)
    {
        arreglo[indiceArregloCombinado++] = mitadDerecha[indiceArregloDerecho++];
    }
}

void rapido(int arreglo[], int izquierda, int derecha)
{
    if (izquierda < derecha)
    {
        int indiceParticion = particion(arreglo, izquierda, derecha);
        rapido(arreglo, izquierda, indiceParticion);
        rapido(arreglo, indiceParticion + 1, derecha);
    }
}

int particion(int arreglo[], int izquierda, int derecha)
{
    int pivote = arreglo[izquierda];
    while (1)
    {
        while (arreglo[izquierda] < pivote)
        {
            izquierda++;
        }
        while (arreglo[derecha] > pivote)
        {
            derecha--;
        }
        if (izquierda >= derecha)
        {
            return derecha;
        }
        else
        {
            intercambiar(&arreglo[izquierda], &arreglo[derecha]);
            izquierda++;
            derecha--;
        }
    }
}

void intercambiar(int *a, int *b)
{
    int temporal = *a;
    *a = *b;
    *b = temporal;
}

void burbuja(int arreglo[], int longitud)
{
    for (int x = 0; x < longitud; x++)
    {
        for (int indiceActual = 0; indiceActual < longitud - 1;
             indiceActual++)
        {
            int indiceSiguienteElemento = indiceActual + 1;
            if (arreglo[indiceActual] > arreglo[indiceSiguienteElemento])
            {
                intercambiar(&arreglo[indiceActual], &arreglo[indiceSiguienteElemento]);
            }
        }
    }
}

void insercion(int arreglo[], int longitud)
{
    int i = 1;
    while (i < longitud)
    {
        int j = i;
        while (j > 0 && arreglo[j - 1] > arreglo[j])
        {
            intercambiar(&arreglo[j], &arreglo[j - 1]);
            j--;
        }
        i++;
    }
}

void seleccion(int arreglo[], int longitud)
{
    for (int i = 0; i < longitud - 1; i++)
    {
        for (int j = i + 1; j < longitud; j++)
        {

            if (arreglo[i] > arreglo[j])
            {
                intercambiar(&arreglo[i], &arreglo[j]);
            }
        }
    }
}

Y por si te lo preguntas, el algoritmo más rápido de todos los presentados para ordenar un arreglo usando C es quicksort. Por cierto, no puedo dejar el archivo con los diez mil números aquí pero puedes generarlo usando cualquier programa de tu preferencia.

Puedes usar shuf de Linux: shuf -i 1-10000 -n 10000 > 10mil_numeros.txt

O también puedes usar mi generador de números aleatorios para crear el archivo.

Estoy aquí para ayudarte 🤝💻

Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.

Dejar un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *