VPF::[c++] сортировки во внешней памяти

dav1d

Дата 19.4.2008, 15:07 (ссылка)

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

Загрузка ...

Новичок

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

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

здравствуйте. вот такая задача стоит передо мной:

требуется программно реализовать следующие методы сортировки данных во внешней памяти: сортировка прямым слиянием; сортировка сбалансированным многопутевым слиянием.

сортировка прямым слиянием

Цитата

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и записи a1, a3, ..., a(n-1) пишутся в файл B, а записи a2, a4, ..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4), ..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей.

сортировка сбалансированным многопутевым слиянием

Цитата

В основе метода внешней сортировки сбалансированным многопутевым слиянием является распределение серий исходного файла по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия.

может у кого-то уже есть алгоритмы, написанные на си++? в интернете найти не удалось..

dav1d

Дата 20.4.2008, 16:00 (ссылка)

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

Загрузка ...

Новичок

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

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

может кто-нибудь за деньги возьмётся? по цене договримся.

piritus

Дата 20.4.2008, 17:23 (ссылка)

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

Загрузка ...

Бывалый

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

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

могу попробовать помоч...
до какого числа актуально?

--------------------

piritus

Дата 20.4.2008, 21:17 (ссылка)

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

Загрузка ...

Бывалый

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

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

я так понимаю, что в "сортировке прямым слиянием" для того что бы выполнянось условие:

Цитата(dav1d @ 19.4.2008, 15:07

)

Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности

т.е. что бы в конце осталось только 2 строчки, нужно что бы изначально файл А содержал количество строк: 2,4,16,32,64 и т.д.

если я правильно понял условие, то вот:

Код


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>

#define max 1000


char A[]="A";
char B[]="B";
char C[]="C";
int Sort(char *A,char *B,char *C);

int main(void){
    Sort(A,B,C);

    return 0;
}

int Sort(char *fnA,char *fnB,char *fnC){
FILE *fpA;
FILE *fpB;
FILE *fpC;
int i,n=0,c,nstr,nstr2;
char t[1000];

// Num string
    fpA=fopen(fnA,"r");
    nstr=0;
    while((c=getc(fpA))!=EOF)
        if(c=='\n')
            ++nstr;
    fclose(fpA);
    nstr=sqrt(nstr);
    nstr2=nstr;
    nstr=2;
    while(nstr2!=1){
        nstr2/=2;
        nstr++;
    }
    
    for(i=0;i<=nstr;i++){
// First step
    fpA=fopen(fnA,"r");
    fpB=fopen(fnB,"w");
    fpC=fopen(fnC,"w");
    
    do{
        t[0]=0;
        fgets(t,max,fpA);
        fputs(t,fpB);
        if(t[0]!=0){
            fgets(t,max,fpA);
         fputs(t,fpC);
        }
    }while(t[0]!=0);
    
    fclose(fpA);
    fclose(fpB);
    fclose(fpC);

// Second step
    fpA=fopen(fnA,"w");
    fpB=fopen(fnB,"r");
    fpC=fopen(fnC,"r");
    
    do{
        t[0]=0;
        fgets(t,max,fpB);
        t[(strlen(t))-1]=0;
        fputs(t,fpA);
        fgets(t,max,fpC);
        fputs(t,fpA);
    }while(t[0]!=0);

    fclose(fpA);
    fclose(fpB);
    fclose(fpC);
    }

    return 0;    
}

тема: "характеристики процессора, cpuid" еще интересует?

Это сообщение отредактировал(а) piritus - 20.4.2008, 21:48

--------------------

dav1d

Дата 21.4.2008, 05:26 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата

если я правильно понял условие

наверное, не правильно.
сортируется просто массив целых чисел. и, чтобы

Цитата

Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая.

для простоты заполняем файл А чётным количеством чиел.

обратись в личку - подробное задание кину.

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