Вместо 283 - 0, да и сортировка в начале неправильная... Я подозреваю, что где-то проблемы с индексами массива, но поскольку принцип работы алгоритма я не осилил и максимум, что у меня получилось - это переписать его, заменив goto на циклы, найти эту ошибку не могу. Поэтому прошу помочь
S1: s=0; p=1;
S2: if (s==0) { i=1; j=N; k=N; l=2*N+1; }
if (s==1) { i=N+1; j=2*N; k=0; l=N+1; }
d=1; q=p; r=p;
S3: if (R[i]->K>R[j]->K) goto S8;
Проверь i и j, они у тебя начинаются i с 1(надо наверное с нуля сделать чтобы цифра 4 в сотритровке участвовала), а j непонятно с чего N это что(длина первой части?).
Нулевой элемент у меня возникал когда сортировка вылазила за правую границу массива(но это было в пузырьковой)
Весь массив имеет длину 2*N, где N - число элементов, подлежащих сортировке, они изначально лежат в первой половине массива и в ходе алгоритма по определенным праилам пересылаются во вторую половину, потом обратно и т.д.
i и j я пробовал менять, но тогда вообще никак не сортирует.
Что-то подсказывает, что придется писать с нуля, предварительно долго и упорно вникая в суть алгоритма. У нас в методичке дана блок-схема, но она, во-первых, составлена по Кнуту, а во-вторых, программа, написанная по ней, вообще не дает никаких результатов.
на сайте который ты мне дал описание очень плохое ИМХО. Вот ссылка где есть исходники. Сегодня начну писать и завтра покажу свой код. Единственное что мне не нравится в нем это использование рекурсивных вызовов...
Выяснил неприятную вещь Он работает только на массивах с длиной, равной степени двойки. Надо где-то поправлять...
может быть кратное двум, а не степень двойки? блин, ни как руки не доходят заняться... чтобы написать алгоритм простых слияний, нужно знать алгоритм естественного слияния? какая между ними связь?
Именно степеням двойки. Я написал оба, чтобы лучше разобраться, ну и в описаниях обычно рассказывают о простом, основываясь на естественном.
Цитата из Кнута по поводу алгоритма:
Довольно удивительно, что этот метод работает и тогда, когда N не является степенью 2.
хоть как то разобрался с алгоритмом... сам столкнулся с проблемой связанной скорее с языком.
вот код:
Код:
#include <fstream>
using namespace std;
void merge (int *, int , int *, int , int *, int);
int *mergesort (int *, int);
int main () {
ifstream fin ("a.in");
ofstream fout ("a.out");
int n;
fin>>n;
int i;
int *arr=new int [n];
for (i=0;i<n;i++){
fin>>arr [i];
}
int *res = mergesort (arr,n);
for (i=0;i<m+n;i++){
fout<<res[i]<<" ";
}
fout.close ();
fin.close ();
return 0;
}
void merge (int *arr, int lena, int *brr, int lenb, int *res, int len) {
int i, j, k;
i=j=k=0;
int temp;
while (k<len){
if (i==lena) temp=brr[j];
else
if (j==lenb) temp=arr[i];
else
temp=(arr[i]>brr[j])?brr[j]:arr[i];
res[k]=temp;
if (temp==arr[i]) ++i;
else ++j;
++k;
}
}
int *mergesort (int *arr, int len) {
if (len==1) return arr;
else {
int middle=len/2;
int buff [1000];
merge(mergesort (&arr[middle],middle), middle, mergesort (arr,middle), middle, buff, len);
return buff;
}
}
как видно в последней функии возразается адрес локальной памяти, это грубая ошибка-понимаю. но как мне еще реализовать обмен адресами (массивами)? глобальные переменные не предлогать, мне не интересно такое решение. как возвращать значения или где хранить? мне бы интересно было узнать кто как бы написал этот алгоритм (не в плане алгоритма, а в плане выделений памяти и т.д.). как вообще принято выделять память и работать с ней (как бы стандарт), может кто знает ссыку на такой материал?
как видно в последней функии возразается адрес локальной памяти, это грубая ошибка-понимаю. но как мне еще реализовать обмен адресами (массивами)? глобальные переменные не предлогать, мне не интересно такое решение. как возвращать значения или где хранить? мне бы интересно было узнать кто как бы написал этот алгоритм (не в плане алгоритма, а в плане выделений памяти и т.д.). как вообще принято выделять память и работать с ней (как бы стандарт), может кто знает ссыку на такой материал?
Насчет стандарта не знаю, но одномерные массивы заменяются на такие конструкции без переписки кода (внимание - стиль C!):
Код:
/*int a[N]*/
int *a;
if(
!(a= /* malloc возвращает 0,
* если память выделить не
* удалось, а 0 - это ЛОЖЬ
*/
(int *) /* malloc всегда возвращает
* void *, на что компилятор
* иногда выдает предупреждение
*/
malloc(N*sizeof(int)) /* malloc принимает
* размер в байтах
* в качестве аргумента,
* а размер типа почти
* всегда больше 1 байта
*/
)
{
puts ("Не удалось выделить память под a");
/* обработать ошибку, не обязательно через exit.
* Главное - исключить обращения к этой переменной
*/
exit (1);
}
/* Версия без комментариев: */
int *a;
if(!(a=(int *) malloc(N*sizeof(int)))
{
puts ("Не удалось выделить память под a");
exit (1);
}
Надеюсь, комментарии не слишком развернутые.
malloc находится в stdlib.h, exit - там же.
Решение вроде работает и в C++, хотя и имеет старый стиль, как пользоваться new пускай другие говорят.
как видно в последней функии возразается адрес локальной памяти, это грубая ошибка-понимаю. но как мне еще реализовать обмен адресами (массивами)? глобальные переменные не предлогать, мне не интересно такое решение. как возвращать значения или где хранить? мне бы интересно было узнать кто как бы написал этот алгоритм (не в плане алгоритма, а в плане выделений памяти и т.д.). как вообще принято выделять память и работать с ней (как бы стандарт), может кто знает ссыку на такой материал?
Насчет стандарта не знаю, но одномерные массивы заменяются на такие конструкции без переписки кода (внимание - стиль C!):
Код:
/*int a[N]*/
int *a;
if(
!(a= /* malloc возвращает 0,
* если память выделить не
* удалось, а 0 - это ЛОЖЬ
*/
(int *) /* malloc всегда возвращает
* void *, на что компилятор
* иногда выдает предупреждение
*/
malloc(N*sizeof(int)) /* malloc принимает
* размер в байтах
* в качестве аргумента,
* а размер типа почти
* всегда больше 1 байта
*/
)
{
puts ("Не удалось выделить память под a");
/* обработать ошибку, не обязательно через exit.
* Главное - исключить обращения к этой переменной
*/
exit (1);
}
/* Версия без комментариев: */
int *a;
if(!(a=(int *) malloc(N*sizeof(int)))
{
puts ("Не удалось выделить память под a");
exit (1);
}
Надеюсь, комментарии не слишком развернутые.
malloc находится в stdlib.h, exit - там же.
Решение вроде работает и в C++, хотя и имеет старый стиль, как пользоваться new пускай другие говорят.
спасибо, постепенно избавляюсь от потоков, а щас избавлюсь от new. а какие системные вызовы отвечают за выделение памяти в никсаx?
Он работает только на массивах с длиной, равной степени двойки. Надо где-то поправлять...
