VPF::Сортировка слиянием дека. - Форум программистов

marsh123

Дата 22.5.2011, 04:18 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 69
Регистрация: 22.6.2008

Репутация: нет
Всего: нет

Здравствуйте. Очень надеюсь на Вашу помощь, так как не успеваю закрыться до сессии.

Нужно написать сортировку дека, дек реализован на кольцевом буфере (но это не важно, преподаватель сказал, что в сортировке слиянием я имею право использовать только функции push, pop, len).
Язык СИ.

Вот, собственно, функция (закомментировал, чтобы Вам была ясна моя логика):

Код


void deck_merge_sort(deck *d) {
    if (deck_len(d) < 2) return; //если длина дека 1 или 0, то сортировать его не нужно
    if (deck_len(d) == 2) { //если длина дека 2, то сортировка сводится к замене элементов местами
        Data dataa, datab; //выделяем буфер типа дата (такие элементы хранит дек)
        dataa = deck_pop_left(d); //выталкиваем туда первый элемент из дека
        datab = deck_pop_left(d); //выталкиваем туда второй элемент из дека
        if (dataa.key > datab.key) { //сравниваем их ключи (сортировка по ключу элемента).
            deck_push_left(d, dataa); //заносим в дек в нужном порядке
            deck_push_left(d, datab);
        }
        else {
            deck_push_left(d, datab); //заносим в дек в нужном порядке
            deck_push_left(d, dataa);
        }
        return; //выходим
    }
    int len = deck_len(d); //получаем длину переданного дека
    deck A = deck_init((len / 2)); //инициализирум дек длинной /2 от переданного
    deck B = deck_init(len - (len / 2)); //инициализируем дек оставшейся длины от переданного
    deck C = deck_init(len); // и еще 1 дек, который равен по длине
    while (deck_len(d) > (len / 2)) { //пока длина переданного дека больше середины
        printf("1.\n"); //принтф для дебага, после кода напишу, что он даёт
        deck_push_right(&B, deck_pop_left(d)); //добавляем в дек B элементы, только что вытолкнутые из переданного дека слева
    } 
    while (deck_len(d) > 0) { //выталкиваем оставшиеся элементы из переданного дека
        printf("2.\n"); //тоже для дебага
        deck_push_right(&A, deck_pop_left(d)); //выталкиваем оставшиеся элементы в дек A
    }
    
    deck_merge_sort(&A); //запускаем рекурсивно тоже самое для дека A
    deck_merge_sort(&B); //и для дека B
    deck_merge(&A, &B, &C); //сливаем А и B в дек C

    while (deck_len(&C) > 0) { //выталкиваем элементы из дека C в переданный дек
        printf("3.\n");
        deck_push_right(d, deck_pop_left(&C));
    }
    
    deck_destroy(&A); //уничтожаем вспомогательные деки
    deck_destroy(&B);    
    deck_destroy(&C);
}

А вот, собственно, функция слияния деков: deck_merge(deck *, deck *, deck *) - слияние первых двух деков в третий.

Код


void deck_merge(deck *a, deck *b, deck *c) {
    Data dataa, datab; //вспомогательный буфер
    while ((deck_len(a) > 0) || (deck_len(b) > 0)) { //пока еще в деках что-то есть
        dataa = deck_pop_left(a); //выталкиваем по элементу из каждого дека в буфер
        datab = deck_pop_left(b);
        if ((deck_len(b) == 0) || ((deck_len(a) > 0) && (dataa.key <= datab.key))) { //если длина дека 2 = 0,
              //либо же, если длина дека 1 больше нуля, при этом ключ дека 1 больше дека 2
            deck_push_right(c, dataa); //вталкиваем справа в дек 3 элемент из первого
            deck_push_left(b, datab); //возвращаем элемент слева в дек 2
        }
        else {
            deck_push_right(c, datab); //тоже самое, но наоборот
            deck_push_left(a, dataa);
        }
    }
}

Вот, собственно вывод программы:

Цитата

./a.out
5
l 2 3
l 4 1
l 5 7
l 3 1
l 8 2
p
8 2
3 1
5 7
4 1
2 3
s
1.
1.
1.
2.
2.
1.
1.
2.
Error: You are trying to pop an element from an empty deck.
Аварийный останов

там сначала создается дек из 5 элементов, потом они заталкиваются слева (ключ и значение), потом печать, а при вызове сортировки она проходит по принтфам для дебага и выдает, что не может вытолкнуть элемент из пустого дека, хотя по идее он там не должен пытаться что-то толкать из пустого дека, я в замешательстве smile

Помогите пожалуйста разобраться, заранее спасибо.
Модератор: улучшил читаемость сообщения

Это сообщение отредактировал(а) bsa - 22.5.2011, 22:10

marsh123

Дата 22.5.2011, 05:03 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 69
Регистрация: 22.6.2008

Репутация: нет
Всего: нет

Разобрался, криво работала не сама сортировка, а функция слияния deck_merge, вот исправленная версия, может кому-то пригодится:

Код


void deck_merge(deck *a, deck *b, deck *c) {
    Data dataa, datab;
    int fa = 0, fb = 0;
    while ((deck_len(a) > 0) || (deck_len(b) > 0)) {
        if (deck_len(a) > 0) {
            dataa = deck_pop_left(a);
            fa = 1;
        }
        if (deck_len(b) > 0) {
            datab = deck_pop_left(b);
            fb = 1;
        }
    
        if ((deck_len(b) == 0) && (fb == 0)) {
            deck_push_right(c, dataa);
        }
        else if ((deck_len(a) == 0) && (fa == 0)) {
            deck_push_right(c, datab);
        }
        else if (((fa == 1) && (deck_len(a) >= 0)) || ((fb == 1) && (deck_len(b) >= 0))) {
            if (dataa.key < datab.key) {
                deck_push_right(c, dataa);
                deck_push_left(b, datab);
            }
            else if (dataa.key == datab.key) {
                deck_push_right(c, dataa);
                deck_push_right(c, datab);
            }
            else {
                deck_push_right(c, datab);
                deck_push_left(a, dataa);
            }
        }
        fa = 0; fb = 0;
    }
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »