सी में मूल प्रकार के एल्गोरिदम के साथ एक अच्छा संदर्भ कार्ड/धोखा शीट?

Question

मैं सी (या शायद छद्म कोड में) के सभी मूल सॉर्टिंग एल्गोस के साथ सही संदर्भ कार्ड के लिए (बिना भाग्य के) देख रहा हूं। विकिपीडिया जानकारी का एक भयानक स्रोत है, लेकिन इस बार मैं कुछ और पोर्टेबल (जेब आकार संभव होने पर) और निश्चित रूप से प्रिंट करने योग्य कुछ ढूंढ रहा हूं। किसी भी सुझाव की सराहना की जाएगी!

Answer 1

मैं मेरा एक दोस्त सी के अध्ययन के लिए बनाया है, हो सकता है आप यह उपयोगी मिल जाएगा:

#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

आपको रॉबर्ट सेडगेविक द्वारा सी में एल्गोरिदम नामक पुस्तक की आवश्यकता है।

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

मैं शायद एक प्रयोग एक के लिए विचार करेंगे। नए लोगों को कुछ हद तक महंगे हैं

Answer 3

बाइबिल का प्रयास करें (लेकिन, अभी भी पूरी तरह से इसके लायक।):

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

Answer 4

आप निश्चित रूप से बाहर की जाँच करनी चाहिए Animated Sorting Algorithms पेज। यह एल्गोरिदम को सॉर्ट करने के लिए एक अद्भुत संसाधन है।

संपादित करें नए लिंक के लिए पीटरिनो को धन्यवाद!

Answer 5

आम तौर पर, लोग अलग-अलग एल्गोरिदम के बारे में बहुत ज्यादा चिंता नहीं करते हैं, और कई लोग अपनी सॉर्टिंग करने के लिए मानक लाइब्रेरी qsort() फ़ंक्शन (जो वास्तव में क्विक्सॉर्ट का उपयोग नहीं कर सकते हैं) का उपयोग कर सकते हैं। जब वे इसका उपयोग नहीं करते हैं, तो आमतौर पर उन्हें अधिक जटिल आवश्यकताएं होती हैं। ऐसा इसलिए हो सकता है क्योंकि उन्हें बाहरी सॉर्टिंग (डिस्क पर डेटा फैलाना), या प्रदर्शन से संबंधित कारणों के लिए आवश्यकता होती है। कभी-कभी, qsort() (या, वास्तव में, bsearch()) का उपयोग करने से जुड़े फ़ंक्शन-कॉल-प्रति-तुलना का अनुमानित ओवरहेड बहुत अच्छा है। कभी-कभी, लोग क्विक्सोर्ट के संभावित ओ (एन^2) के सबसे खराब मामले व्यवहार को जोखिम नहीं लेना चाहते हैं, लेकिन अधिकांश उत्पादन qsort() एल्गोरिदम आपके लिए इससे बचेंगे।

एल्गोरिदम पर विभिन्न पुस्तकों के अलावा - सेडगेविक एक ऐसा है, लेकिन कई अन्य हैं - आप जॉन बेंटले के "प्रोग्रामिंग मोती" या "अधिक प्रोग्रामिंग मोती" किताबों पर भी नजर डाल सकते हैं। यह अच्छा होगा, वैसे भी - वे उत्कृष्ट हैं - लेकिन "अधिक प्रोग्रामिंग मोती" में भी लिखे गए सरल एल्गोरिदम की लाइब्रेरी शामिल है, जिसमें सम्मिलन क्रम, ढेर क्रम और त्वरित प्रकार शामिल हैं। यह बबल सॉर्ट, शैल सॉर्ट, और बोगोर्ट को याद करता है। इसमें रैडिक्स सॉर्ट भी शामिल नहीं है।