Форум программистов, компьютерный форум CyberForum.ru

Не работает алгоритм многофазной сортировкой - C++

Восстановить пароль Регистрация
 
Newprogramer
Сообщений: n/a
18.04.2013, 07:45     Не работает алгоритм многофазной сортировкой #1
Алгоритм работает при количестве случайных элементов i до 10000 и выдает в конечном файле бред при например 20000... Не могу разобраться в чем проблема, помогите пожалуйста... Нужно чтобы работал при разном количестве, например до 200000... Помогите исправить или подскажите другой алгоритм каскадной или многофазной сортировки файлов на C++...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void sl (FILE *fn1, FILE *fn2, FILE *fn3, char *max) {           // функция слияния
    long int ch1=0,ch2=0,tmp=0,tml=0,m=0,n=0;                                     // используемые переменные
    FILE *temp;
 
#define read_a if (!feof(fn1)) fscanf(fn1,"%d",&ch1); else ch1=-1;
#define read_b if (!feof(fn2)) fscanf(fn2,"%d",&ch2); else ch2=-1;
 
    while (!feof(fn1)) {                                             // пока не достигнем конца файла
        read_a; if(!feof(fn1)) read_b;                                // считываем первые элементы серий
        while (ch1>=0 && ch2>=0) {                                    // пока серия не кончилась
            if (ch1<ch2) { fprintf(fn3,"%5d",ch1); read_a;}            // записываем текущий элемент изфайлф fn1 и считываем следующий
            else         { fprintf(fn3,"%5d",ch2); read_b;}            // записываем текущий элемент изфайлф fn2 и считываем следующий
        }
        if (ch1<0 && !feof(fn1))
            while (ch2>=0) { fprintf(fn3,"%5d",ch2); read_b; }   // если серия файла fn2 еще не кончилась, дописываем оставшиеся элементы
            if (ch2<0) {
                while (ch1>=0) { fprintf(fn3,"%5d",ch1); read_a; }   // если серия файла fn1 еще не кончилась, дописываем оставшиеся элементы
                if (!feof(fn1)) fprintf(fn3,"%5d\n",-1); }
    }
    fclose(fn1); fclose(fn3);
 
    temp=fopen("temp.txt","w");
    while (fscanf(fn2,"%d",&tml)!=EOF)
        fprintf(temp,"%5d",tml);
    fclose(fn2);fclose(temp);
 
    fn2=fopen(max,"w"); temp=fopen("temp.txt","r");
    while (fscanf(temp,"%d",&tmp)!=EOF) {
        fprintf(fn2,"%5d",tmp);
        if(tmp==-1) fprintf(fn2,"\n"); }
    fclose(fn2);fclose(temp);
    remove("temp.txt");
}
 
void sort (char *fname) {                  // функция сортировки
    long int i=0,j=0,k=0,a1=0,a2=0,a=0,b=0,l=0,h=0,h1=0,h2=0,h3=0;                 // используемые переменные
    FILE *file,*f1,*f2,*f3;                // испоьзуемые файлы
    file=fopen(fname,"r");                 // открывафем исходный файл
    f1=fopen("tmp1.txt","w");              // создаем временный файл
    j=0; k=0;                              // минимальный элемент и кол-во серий
    while (fscanf(file,"%d",&i)!=EOF) {    // перебираем все элементы файла
        if (i<j) {fprintf(f1,"%5d\n",-1);  // если серия закончилась
        k++; }                  // число серий
        fprintf(f1,"%5d",j=i); }           // записываем число во временный файл
    fcloseall();                           // закрываем все файлы
 
    a1=0; a2=1;                            // первые числа Фибоначи
    a=a1+a2;                               // след. число
    while (a<k) {                          // превышает число серий
        a1=a2; a2=a; a=a1+a2; }            // вычисление послед. чисел
 
    b=a-k;                                 // кол-во пустых серий
    f1=fopen("tmp1.txt","a+");             //
    for (l=1; l<=b; l++)                    //
        fprintf(f1,"%5d\n",-1);            // добавляем фиктивные серии
    fclose(f1); l=0;                       // закрываем все файлы
 
    f1=fopen("tmp1.txt","r");              //
    f2=fopen("tmp2.txt","w");              // открываем файлы
    f3=fopen("tmp3.txt","w");              //
    while (l<a1) {                         // записываем во 2-ой файл
        fscanf(f1,"%d",&i);                // кол-во серий
        if (i==-1) {                       // удовлетв. первому
            l++;                       // из чисел Фибоначи
            fprintf (f2,"%5d\n",i); }  // (меньшему)
        else fprintf (f2,"%5d",i); }       //
 
    while (l<a) {                          // записываем в 3-ий файл
        fscanf(f1,"%d",&i);                // кол-во серий
        if (i==-1) {                       // удовлетв. второму из
            l++;                       // чисел Фибоначи
            fprintf (f3,"%5d\n",i); }  // (большему)
        else fprintf (f3,"%5d",i); }       //
    fcloseall();                           // закрываем все файлы
 
    while ((!feof(f1) && !feof(f2)) || (!feof(f1) && !feof(f3)) || (!feof(f2) && !feof(f3))) {
        fseek(f1,-5,1);fseek(f2,-5,1);fseek(f3,-5,1);
        fcloseall();
        f1=fopen("tmp1.txt","w");         // для 1-го, 4-го, 7-го и т.д. прохода
        f2=fopen("tmp2.txt","r");
        f3=fopen("tmp3.txt","r"); sl(f2,f3,f1,"tmp3.txt"); fcloseall();
 
        f1=fopen("tmp1.txt","r");         // для 2-го, 5-го, 8-го и т.д. прохода
        f2=fopen("tmp2.txt","w");
        f3=fopen("tmp3.txt","r"); sl(f3,f1,f2,"tmp1.txt"); fcloseall();
 
        f1=fopen("tmp1.txt","r");
        fscanf(f1,"%5d",&h);
        if (feof(f1)) { f3=fopen("tmp3.txt","w"); fclose(f3);
        fclose(f1); }
        else  {   fseek(f1,-5,1);
        // для 3-го, 6-го, 9-го и т.д. прохода
        f2=fopen("tmp2.txt","r");
        f3=fopen("tmp3.txt","w"); sl(f1,f2,f3,"tmp2.txt"); fcloseall(); }
        fcloseall();
 
        f1=fopen("tmp1.txt","r");
        f2=fopen("tmp2.txt","r");
        f3=fopen("tmp3.txt","r");
        fscanf(f1,"%5d",&h1);
        fscanf(f2,"%5d",&h2);
        fscanf(f3,"%5d",&h3); }
 
    if (!feof(f1)){                         // если последняя серия в первом файле
        f1=fopen("tmp1.txt","r");          //
        file=fopen(fname,"w");             //
        while(fscanf(f1,"%d",&i)!=EOF)     //
            fprintf(file,"%5d\n",i); }           // записываем серию в исходный файл
    if (!feof(f2)){                         // если последняя серия во втором файле
        f2=fopen("tmp2.txt","r");          //
        file=fopen(fname,"w");             //
        while(fscanf(f2,"%d",&i)!=EOF)     //
            fprintf(file,"%5d\n",i); }           // записываем серию в исходный файл
    if (!feof(f3)){                         // если последняя серия в третьем файле
        f1=fopen("tmp3.txt","r");          //
        file=fopen(fname,"w");             //
        while(fscanf(f3,"%d",&i)!=EOF)     //
            fprintf(file,"%5d\n",i); }           // записываем серию в исходный файл
    fcloseall();                            // закрываем все файлы
    remove("tmp1.txt");remove("tmp2.txt");remove("tmp3.txt");  // удаляем временные файлы
}
void main () {            // основная программа
    long int i=0;                // используемые переменные
    FILE *f;              // используемые файлы
    srand (unsigned (time(0)));          // инициализируем генератор случайных чисел
    // ***** Заполняем файл случайными перестановками *****
    f=fopen("file.txt","w");                                // создаем новый файл
    for (i=0; i<15000; i++) fprintf(f,"%5d",rand()%10000+1);  // заполняем его случайными числами
    fclose(f);                                              // закрываем созданный файл
    sort("file.txt");                                       // сортируем файл
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2013, 07:45     Не работает алгоритм многофазной сортировкой
Посмотрите здесь:

Почему такой простой алгоритм работает неправильно? C++
Как работает алгоритм удаления дерева C++
Как работает алгоритм возведения числа a в степень n ? C++
Не работает алгоритм сортировки динамического массива C++
C++ Алгоритм шифрования RC4 не совсем корректно работает
C++ Как работает алгоритм Khazad
C++ Неправильно работает алгоритм поиска занятых клеток
C++ Не работает алгоритм нахождения слов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 06:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru