¿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 gran 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

Hice esto para un amigo mío que estudia C, tal vez le resultará ú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 2

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

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

que probablemente busque uno usado. Otros nuevos son un poco caros

Answer 3

Trata la Biblia (pero, aún totalmente la pena.):

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

Answer 4

Usted debería salir la página Animated Sorting Algorithms. Es un recurso increíble para los algoritmos de clasificación.

EDIT ¡Gracias a Peterino por el nuevo enlace!

Answer 5

En términos generales, las personas no se preocupan demasiado por los diferentes algoritmos, y muchas personas usan la función de biblioteca estándar qsort() (que podría o no usar un 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 de producción qsort() lo evitarán.

Además de los diversos libros sobre algoritmos, Sedgewick es uno de ellos, pero hay muchos más, también puede consultar 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.