programas - metodos de ordenamiento en c

¿Una buena tarjeta de referencia/hoja de trucos con los algoritmos básicos de clasificación en C?

Question

He estado buscando (sin mucha suerte) la tarjeta de referencia perfecta con todos los algos básicos de clasificación en C (o tal vez en el pseudo código). Wikipedia es una excelente fuente de información, pero esta vez estoy buscando algo definitivamente más portátil (de bolsillo si es posible) y, por supuesto, imprimible. ¡Cualquier sugerencia sería muy apreciada!

Answer 1

En términos generales, las personas no se preocupan demasiado por los diferentes algoritmos, y muchas personas usan la función qsort() biblioteca estándar (que puede o no usar una Quicksort) para hacer su clasificación. Cuando no lo usan, generalmente tienen requisitos más complejos. Esto puede deberse a que necesitan una clasificación externa (derrame de datos en el disco) o por razones relacionadas con el rendimiento. Ocasionalmente, la sobrecarga percibida de la función-llamada-por-comparación asociada con el uso de qsort() (o, de hecho, bsearch() ) es demasiado grande. A veces, las personas no quieren arriesgar el potencial O (N ^ 2) peor comportamiento del Quicksort, pero la mayoría de los algoritmos qsort() producción lo evitarán.

Aparte de los diversos libros sobre algoritmos, Sedgewick es uno de ellos, pero hay muchos más, también puedes echar un vistazo a los libros "Programming Pearls" o "More Programming Pearls" de Jon Bentley. Esto sería bueno, de todos modos, son excelentes, pero "Más perlas de programación" también incluye una biblioteca de algoritmos simples escritos en awk, que incluyen ordenación de inserción, clasificación de montones y clasificación rápida. Se pierde Bubble Sort, Shell Sort y BogoSort. Tampoco incluye Radix Sort.

Answer 2

Hice esto para un amigo mío que estudia C, tal vez lo encuentres útil:

#include <stdlib.h>
#include <string.h>

static void swap(int *a, int *b) {
    if (a != b) {
        int c = *a;
        *a = *b;
        *b = c;
    }
}

void bubblesort(int *a, int l) {
    int i, j;

    for (i = l - 2; i >= 0; i--)
        for (j = i; j < l - 1 && a[j] > a[j + 1]; j++)
            swap(a + j, a + j + 1);
}

void selectionsort(int *a, int l) {
    int i, j, k;
    for (i = 0; i < l; i++) {
        for (j = (k = i) + 1; j < l; j++)
            if (a[j] < a[k])
                k = j;
        swap(a + i, a + k);
    }
}

static void hsort_helper(int *a, int i, int l) {
    int j;

    for (j = 2 * i + 1; j < l; i = j, j = 2 * j + 1)
        if (a[i] < a[j])
            if (j + 1 < l && a[j] < a[j + 1])
                swap(a + i, a + ++j);
            else
                swap(a + i, a + j);
        else if (j + 1 < l && a[i] < a[j + 1])
            swap(a + i, a + ++j);
        else
            break;
}

void heapsort(int *a, int l) {
    int i;

    for (i = (l - 2) / 2; i >= 0; i--)
        hsort_helper(a, i, l);

    while (l-- > 0) {
        swap(a, a + l);
        hsort_helper(a, 0, l);
    }
}

static void msort_helper(int *a, int *b, int l) {
    int i, j, k, m;

    switch (l) {
        case 1:
            a[0] = b[0];
        case 0:
            return;
    }

    m = l / 2;
    msort_helper(b, a, m);
    msort_helper(b + m, a + m, l - m);
    for (i = 0, j = 0, k = m; i < l; i++)
        a[i] = b[j < m && !(k < l && b[j] > b[k]) ? j++ : k++];
}

void mergesort(int *a, int l) {
    int *b;

    if (l < 0)
        return;

    b = malloc(l * sizeof(int));
    memcpy(b, a, l * sizeof(int));
    msort_helper(a, b, l);
    free(b);
}

static int pivot(int *a, int l) {
    int i, j;

    for (i = j = 1; i < l; i++)
        if (a[i] <= a[0])
            swap(a + i, a + j++);

    swap(a, a + j - 1);

    return j;
}

void quicksort(int *a, int l) {
    int m;

    if (l <= 1)
        return;

    m = pivot(a, l);
    quicksort(a, m - 1);
    quicksort(a + m, l - m);
}

struct node {
    int value;
    struct node *left, *right;
};

void btreesort(int *a, int l) {
    int i;
    struct node *root = NULL, **ptr;

    for (i = 0; i < l; i++) {
        for (ptr = &root; *ptr;)
            ptr = a[i] < (*ptr)->value ? &(*ptr)->left : &(*ptr)->right;
        *ptr = malloc(sizeof(struct node));
        **ptr = (struct node){.value = a[i]};
    }

    for (i = 0; i < l; i++) {
        struct node *node;
        for (ptr = &root; (*ptr)->left; ptr = &(*ptr)->left);
        a[i] = (*ptr)->value;
        node = (*ptr)->right;
        free(*ptr);
        (*ptr) = node;
    }
}

Answer 3

Lo que necesitas es un libro llamado Algorithms in C de Robert Sedgewick.

http://www.amazon.com/Algorithms-C-paperback-Robert-Sedgewick/dp/0768682339/

Probablemente buscaría uno usado. Los nuevos son un tanto caros (pero, aún así, lo valen totalmente).

Answer 4

Prueba la Biblia:

http://dannyreviews.com/h/Art_Programming.html

Answer 5

Definitivamente deberías consultar la página Algoritmos de clasificación animados . Es un recurso increíble para los algoritmos de clasificación.

EDITAR ¡ Gracias a Peterino por el nuevo enlace!