Une bonne carte de référence/feuille de triche avec les algorithmes de tri de base en C?

Question

J'ai regardé (sans grande chance) la carte de référence parfaite avec tous les algos de tri de base en C (ou peut-être en pseudo code). Wikipédia est une formidable source d'information mais cette fois je cherche quelque chose de nettement plus portable (format de poche si possible) et bien sûr imprimable. Toute suggestion serait très appréciée!

Answer 1

Je l'ai fait pour un de mes amis l'étude C, peut-être vous sera utile:

#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

Ce dont vous avez besoin est un livre intitulé Algorithms in C de Robert Sedgewick.

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

Je chercherais probablement une occasion. Nouvelles sont un peu cher

Answer 3

Essayez la Bible (mais, encore tout à fait la peine.):

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

Answer 4

Vous devez absolument vérifier la page Animated Sorting Algorithms. C'est une ressource incroyable pour les algorithmes de tri.

EDIT Merci à Peterino pour le nouveau lien!

Answer 5

De manière générale, les gens ne se soucient pas trop des différents algorithmes, et beaucoup de gens utilisent la fonction de bibliothèque standard qsort() (qui pourrait ou non utiliser un Quicksort) pour faire leur tri. Quand ils ne l'utilisent pas, ils ont généralement des exigences plus complexes. Cela peut être dû au fait qu'ils ont besoin d'un tri externe (déversement de données sur le disque) ou pour des raisons liées aux performances. Parfois, la surcharge perçue de la fonction-appel-par-comparaison associée à l'utilisation qsort() (ou, en effet, bsearch()) est trop grande. Parfois, les gens ne veulent pas risquer le pire comportement possible de Quicksort, mais la plupart des algorithmes de production éviteront cela pour vous. Outre les divers livres sur les algorithmes - Sedgewick en est un exemple, mais il y en a beaucoup d'autres - vous pouvez aussi jeter un coup d'œil sur les livres de «Programming Pearls» ou «More Programming Pearls» de Jon Bentley. Ce serait bon, de toute façon - ils sont excellents - mais "More Programming Pearls" inclut également une bibliothèque d'algorithmes simples écrits en awk, incluant le tri par insertion, le tri par tas et le tri rapide. Il manque Bubble Sort, Shell Sort et BogoSort. Il n'inclut pas non plus Radix Sort.