1

Суть алгоритма в том, что числа из интервала [0; 1) мы распределяем по спискам, каждый такой маленький список сортируем вставками, а затем все эти списки сливаем. Начнем с реализации списка и основных операций:

struct list{
    int data;
    struct list *next;
};

struct list * insert(struct list *node, int data){
    struct list *tmp = (struct list*)malloc(sizeof(struct list));

    if (tmp != NULL){
        tmp->data = data;
        if (node != NULL){
            tmp->next = node->next;
            node->next = tmp;
        }else{
            tmp->next = NULL;
        }
    }

    return tmp;
}

struct list * sort(struct list *root){
    struct list *new_root = NULL;

    while (root != NULL){
        struct list *node = root;
        root = root->next;

        if (new_root == NULL || node->data < new_root->data){
            node->next = new_root;
            new_root = node;
        }else{
            struct list *current = new_root;
            while (current->next != NULL && !(node->data < current->next->data)){                   
              current = current->next;
            }                

        node->next = current->next;
        current->next = node;
        }
    }

    return new_root;
}

И вот сама сортировка:

void Sort(double a[], int n){
    if(a == NULL) return;
    int i, j;
    list **buckets = (list **)malloc(n*sizeof(list *)); /*Массив списков, сейчас содержит мусор*/
    memset(buckets, 0, n*sizeof(list *));   /*Проинициализируем его*/

    /*Вставить элемент a[i] в список buckets[floor(n*a[i])]*/
    for(i = 0; i < n; i++)
        insert(buckets[(int)floor(n*a[i])], a[i]);
    /*Сортировка всех списков*/
    for(i = 0; i < n; i++)
        buckets[i] = sort(buckets[i]);
    /*Слияние всех списков в один*/
    j = 0;
    /*Цикл по всем спискам*/
    list *p;
    for(i = 0; i < n ; i++){
        printf("end loop\n");
        putchar('\n');
        if(buckets[i] != NULL){
            p = buckets[i];
            while(p != NULL){
                printf("bucket[%d]: data %d\n", i, p->data);
                a[j++] = p->data;
                p = p->next;
            }
        }else printf("bucket[%d] is empty\n", i);
    }
}

Я выводил отладочную информацию, и вот что получилось. В цикле, где сортируются все списки по отдельности, я добавил печать каждого списка. Программа упала, как будто в каждом buckets[i] содержится NULL. В конце, где происходит слияние списков, мы никогда не попадаем в цикл while(p != NULL). И я начал думать, что неправильно добавляю элементы в каждый список buckets[i]. Как это можно исправить?

Дополнение. При выводе каждого из buckets[i] увидел, что все эти списки содержат один или несколько нулей. Я подумал, что это из-за того, что изначально список должен был содержать целые числа, поэтому изменил его определение так:

struct list{
    double data;
    struct list *next;
};

Однако это не помогло. И после сортировки массив содержит одни нули.

3
  • Научитесь пользоваться отладчиком, выполнять программу из под него и проверять что-же в ней происходит.
    – Kromster
    5 сен 2015 в 14:19
  • Тогда придется изучать работу с отладчиком, а это невозможно, когда надо плотно заниматься математикой и алгоритмами.
    – typemoon
    5 сен 2015 в 14:21
  • 1
    @typemoon Если Вы занялись самостоятельным программированием, а не поручили это выделенному специалисту, то придётся и отладку изучить. Если не хочется сложностей консоли, используйте какую нибудь среду.
    – dsnk
    5 сен 2015 в 16:06

1 ответ 1

1

Метод insert вставляет новый элемент после элемента, заданного первым параметром метода, и возвращает указатель на этот новый элемент.

В этом цикле

for(i = 0; i < n; i++)
    insert(buckets[(int)floor(n*a[i])], a[i]);

вы не изменяете значения элементов buckets . Они как были равными NULL, так таковыми и остались.

Я думаю, что вам надо использовать другой метод для заполнения списков. Более подойдет метод, который вставляет элементы в начало списка. Например,

struct list * insert_front( struct list *root, int data )
{
    struct list *tmp = ( struct list * )malloc( sizeof( struct list ) );

    if ( tmp != NULL )
    {
        tmp->data = data;
        tmp->next = root;
        root = tmp;
    }

    return root;
}

Тогда предыдущий цикл может выглядеть следующим образом

for ( i = 0; i < n; i++ )
{
    int j = ( int )floor( n * a[i] )
    buckets[j] = insert_front( buckets[j], a[i] );
}

Другой способ объявления этого метода следующий

int insert_front( struct list **root, int data )
{
    struct list *tmp = ( struct list * )malloc( sizeof( struct list ) );

    if ( tmp != NULL )
    {
        tmp->data = data;
        tmp->next = *root;
        *root = tmp;
    }

    return tmp != NULL;
}

Тогда вызвать его в цикле можно как

for ( i = 0; i < n; i++ )
{
    insert_front( &buckets[( int )floor( n * a[i] )], a[i] );
}

Имейте в виду, что тип поля структуры data должен быть указан как double, если вы собираетесь хранить в списке значения типа double. Соответствующим образом также должен быть изменен тип второго параметра вышеуказанных функций.

4
  • Разве? Я так понял работу функции insert: создаем новый элемент temp, он указывает на элемент, на который раньше указывал node, после этого делаем так, чтобы node указывал на temp. То есть в том цикле мы вставляем элементы после головы. Ага, вижу, голова-то у всех этих списков NULL...
    – typemoon
    5 сен 2015 в 14:38
  • Странный результат работы. Почему-то везде получаются одни нули. ideone.com/0b97qB
    – typemoon
    5 сен 2015 в 15:02
  • @typemoon Я не смотрел вашу ссылку, но думаю проблема в том, что лист имеет тип данного int. Вам следует поменять его на тип double. 5 сен 2015 в 15:03
  • Я подумал об этом первым делом и сразу изменил тип данных. Но это не помогло. Я даже не могу предположить, в чем здесь дело. Кажется, понял. Везде в функциях стоит тип int, а я изменил только тип ноды. Сейчас отредактирую.
    – typemoon
    5 сен 2015 в 15:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.