Подтвердить что ты не робот

Хорошая справочная карта/чит-лист с основными алгоритмами сортировки в C?

Я искал (без везения) идеальную справочную карту со всеми основными сортировочными альго в C (или, возможно, в псевдокоде). Википедия - потрясающий источник информации, но на этот раз я ищу что-то определенно более портативное (карманный размер, если возможно) и, конечно же, для печати. Любое предложение было бы высоко оценено!

4b9b3361

ОТВЕТЫ

Ответ 1

Я сделал это для моего друга, изучающего C, возможно, вы найдете его полезным:

#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;
    }
}

Ответ 4

Вообще говоря, люди не слишком беспокоятся о разных алгоритмах, и многие люди используют стандартную библиотеку qsort() (которая может или не может использовать QuickSort) для их сортировки. Когда они не используют его, они обычно имеют более сложные требования. Это может быть связано с необходимостью внешней сортировки (проливания данных на диск) или по причинам, связанным с производительностью. Иногда воспринимаемые служебные данные функции-вызова-сравнения, связанные с использованием qsort() (или, действительно, bsearch()) слишком велики. Иногда люди не хотят рисковать потенциальным наихудшим поведением O (N ^ 2) Quicksort, но большинство алгоритмов производства qsort() избегают этого для вас.

В отличие от разных книг по алгоритмам - Sedgewick - один из таких, но есть много других - вы также можете взглянуть на книги Джона Бентли "Программирование жемчуга" или "Больше программирующих жемчужин". Это было бы хорошо, в любом случае - они превосходны, но "More Programming Pearls" также включает в себя библиотеку простых алгоритмов, написанных на awk, включая сортировку вставки, сортировку кучи и быструю сортировку. Он пропускает Bubble Sort, Shell Sort и BogoSort. Он также не включает сортировку Radix.