Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

[C/C++ или алгоритм] Сортировка двухфазным слиянием

271
30 апреля 2007 года
MrXaK
721 / / 31.12.2002
Необходимо реализовать сортировку двухфазным слиянием...
Вот здесь есть алгоритм сортировки слиянием, но он по идее однофазный... поискал в гугле, нашёл небольшое описание двухфазного слияния, но встал вопрос как искать наиболее упорядоченную последовательность...
киньте в меня нормальным линком с теорией, или кодом (желательно с описанием времени, занимаемой памяти и сложности)
7.8K
30 апреля 2007 года
Hrew
185 / / 23.04.2007
А Вы всегда Гуглом ищете? Он иногда играет в партизанов... Следующее было найдено на Nigma.ru:

http://cavernxxx.by.ru/i-4-4/struct/sort.htm - код на Си (сортировка файла естественным слиянием - двухфазная сортировка;
сортировка файла прямым слиянием - двухфазная сортировка)

http://lothar.nm.ru/infa/doc/%cb%e5%ea%f6%e8%ff%20%ee%f2%20291004.doc - описание двухфазной сортировки внутренней и внешней, код

http://www.dore.ru/perl/nntp.pl?f=1&gid=17&mid=62765 - пункты 'Сортировка простым слиянием' и 'Сортировка естественным слиянием' - описание принципа.

Или Вам не это нужно?
271
30 апреля 2007 года
MrXaK
721 / / 31.12.2002
ага, спасибо) репу кинул
271
01 мая 2007 года
MrXaK
721 / / 31.12.2002
я вот думаю... почему однофазная сортировка реализована через рекурсивный алгоритм, а двух/многофазная через бесконечный цикл? суть я понял, но вот вопрос... если сложность однофазного слияния nlogn, то двухфазного получается колеблется до n(logn+1) в худшем случае... памяти используется столько же, где тут получается выигрыш в быстродействии? или я неправильно понял алгоритм?
7.8K
01 мая 2007 года
Hrew
185 / / 23.04.2007
Цитата: Mr.Hacker
где тут получается выигрыш в быстродействии?


Вообще-то, насколько я понимаю, все наоборот - однофазная сортировка является улучшением двухфазной (по быстродействию) за счет объединения фаз слияния и разделения, а вот памяти однофазная сортировка занимает больше, так как требует больше дополнительных файлов.

271
03 мая 2007 года
MrXaK
721 / / 31.12.2002
в-общем, я написал, использовав частично код с http://cavernxxx.by.ru/i-4-4/struct/sort.htm
убрал в коде все goto
вот, может кому пригодится:
Код:
/* двухфазная сортировка, параметр - имя файла*/
int vnsort1(char *ff); // фаза разделения серий
int vnsort2(char *a); // фаза слияния

int vnsort1( char *ff )
{
    FILE *A,*B,*C; /* файловые переменные */
    /* файлы "B", "C" в функциях - временные */
    int a1,a2; /* для чтения из исходного файла */
    int pb,pc; /* признаки записи в файлы разделения */
    int p; /* p=1 - признак достижения конца исходного файла */
    while(1)  /* цикл 1, цикл повторения фаз разделения и слияния */
    /* Подготовительные операции */
    {
        if ((A=fopen(ff,"r")) == NULL)
    {
        printf("\n Файл %s не открывается",ff);
        getch();
        return -1;
    }
        if ((B=fopen("B","w")) == NULL)
    {
        printf("\n Файл B не открывается");
        getch();
        return -1;
    }
        if ((C=fopen("C","w")) == NULL)
    {
        printf("\n Файл C не открывается");
        getch();
        return -1;
    }
    p = 0;
    pb = 0;
    pc = 0;
        if(fscanf(A, "%d", &a1) == EOF)
    {
        printf("\n Сортируемый файл - пустой");
        getch();
        return -1;
    }
        else
    {
        fprintf(B, " %d", a1);  
        pb=1;
    }
       while(1) /* цикл 2, цикл формирования серий в файлах В и С */
       {
           while (1) /* цикл 3, цикл формирования серии в файле В */
       {
           if(fscanf(A, "%d", &a2) == EOF)
           {
               p=1; break; /* выход из цикла 3 */
           }
           else
           {
               if (a2>=a1)  /* запишем в серию в файле В */
           {
               fprintf(B, " %d", a2);
               a1=a2;
               pb=1;
               continue;
           }
           else /* запишем первую запись новой серии в файле С */
           {
               fprintf(C, " %d", a2);
               a1=a2;
               pc=1;
               break; /* выход из цикла 3 */
           }
           }
        }
        if (p)
            break;  /* выход из цикла 2 */
            while (1) /* цикл 4, формирование серии в файле С */
        {
            if(fscanf(A, "%d", &a2) == EOF)
        {
            p=1;
            break; /* выход из цикла 4 */
        }
            else
        {
            if (a2 >= a1)  /* запишем в серию в файле С */
            {
                fprintf(C, " %d", a2);
                a1=a2;
                pc=1;
            continue;
            }
            else
            {
                fprintf(B, " %d", a2);
                a1=a2;
                pb=1;
            break; /* выход из цикла 4 */
            }
        }
        }
        if (p)
           break; /* выход из цикла 2 */
        }
    fclose(A);
    fclose(B);
    fclose(C);
    if (pb && pc)  /* исходный файл записан в оба файла разделения */
        vnsort2(ff);  /* вызов функции слияния */
    else
    { /* Удаление вспомогательных файлов */
        remove("B"); remove("C");
        return 0;  /* конец сортировки */
    }
    }
}

int vnsort2(char *a)
{
    bool flag;
    FILE *A,*B,*C; /* файловые переменные */
    int b1,b2,c1,c2; /* для считывания данных из файлов В и С */
    int rb,rc; /* коды завершения операции считывания из файлов В и С*/
    /* Подготовительные операции */
    if ((A=fopen(a,"w")) == NULL)
    {
        printf("\n Файл %s не открывается",a);
    getch();
    return -1;
    }
    if ((B=fopen("B","r")) == NULL)
    {
        printf("\n Файл B не открывается");
    getch();
    return -1;
    }
    if ((C=fopen("C","r")) == NULL)
    {
        printf("\n Файл C не открывается");
    getch();
    return -1;
    }
    rb = fscanf(B,"%d", &b2);
    rc=fscanf(C,"%d",&c2);
    b1=b2;  
    c1=c2;
    while (1)
    {
        if ( (rb > 0) && (rc <= 0) )    // файл С закончился
        {
        fprintf(A," %d",b2);
            while (fscanf(B,"%d",&b2) >0)
            fprintf(A," %d",b2);
        fclose(A);
        fclose(B);
        fclose(C);
        return 0;
        }
        else if ( (rb <= 0) && (rc > 0) ) // файл B закончился
        {
        fprintf(A," %d",c2);
            while (fscanf(C,"%d",&c2) >0)
            fprintf(A," %d",c2);
        fclose(A);
        fclose(B);
        fclose(C);
        return 0;
        }
        else if ( (rb <= 0) && (rc <= 0) ) // оба файла закончились
        {
        fclose(A);
        fclose(B);
        fclose(C);
        return 0;
        }

        if ( (b2 >= b1) && (c2 >= c1) ) /* обе сливаемые серии не исчерпаны */
        {
        if (b2 <= c2)
        {
            fprintf(A," %d",b2); b1=b2;
        rb=fscanf(B,"%d",&b2);
        continue;
        }
        else
        {
            fprintf(A," %d",c2);
            c1=c2;
        rc=fscanf(C,"%d",&c2);
        continue;
        }            
        }

        if ( (b2 >= b1) && (c2 < c1) ) // серия файла C кончилась
        {
        c1 = c2;
        flag = false;
        do
        {
            fprintf(A," %d",b2);
        b1 = b2;
            rb = fscanf(B,"%d",&b2);
            if( rb <= 0 )
            {
                flag = true;               
                break;
            }
            if( b2 < b1 )
            {
                    b1 = b2;
                    flag = true;
                    break;
            }
            if ( flag == true )
                break;
        } while(1);
        if( flag == true )
            continue;
        }
        if ( (b2 < b1) && (c2 >= c1) ) // серия файла B кончилась
        {
        b1 = b2;
        flag = false;
        do
        {
            fprintf(A," %d",c2);
                c1 = c2;
            rc = fscanf(C,"%d",&c2);
            if( rc <= 0 )
            {
                flag = true;               
                break;
            }
            if( c2 < c1 )
            {
                    c1 = c2;
                    flag = true;
                    break;
            }
            if ( flag == true )
                break;
        } while (1);
        if( flag == true )
            continue;
        }

    }
}
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог