массив слияния int с использованием указателей

Question

Для школы мне нужно запрограммировать сортировку слиянием, используя только указатели. Я перепробовал почти все, но не могу заставить его работать.

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

#define num_elementi(array) (sizeof(array)/sizeof(array[0]))

void selsort(int arr[],int n);
void swap(int * a, int * b);
void print(int arr[],int n);
void insort(int arr[],int n);
void mergesort(int arr[],int *p,int *u);
void merge(int arr[],int * p, int * q,int * u);

int main(int argc, char *argv[]){
    int arr[]={99,12,14,65,2,7,54,78,5,1,43,59,88,28,61};
    int n=num_elementi(arr);
    printf("numero elementi array: %d\n",n);
    print(arr,n);
    printf("numero elementi array: %d\n",n);    
    mergesort(arr,&arr[0],&arr[n-1]);
    print(arr,n);
    system("pause");
}

void selsort(int arr[],int n){
    int *i,*j;
    for(i=arr;i<&arr[n-1];i++){
        for(j=i+1;j<&arr[n];j++){
            if(*j<*i)swap(i,j);;
        }

    }
}

void swap(int * a, int * b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void print(int arr[],int n){
    int * p=arr;
    for(p;p<&arr[n];p++)printf("%d ",*p);
    printf("\n");
}

void insort(int arr[],int n){
    int *i,*k;
    for(i=&arr[1];i<&arr[n];i++){
        k=i-1;
        while(k>=&arr[0]&& *k>*(k+1)){
            swap(k,k+1);
            k=k-1;
        }
    }
}


void mergesort(int arr[],int *p,int *u){
    if (p<u){
        int *q=((u-p)/2)+p;
        mergesort(arr,p,q);
        mergesort(arr,q,u-1);
        merge(arr,p,q,u);
    }

}

void merge(int arr[],int * p, int * q,int * u){
    int arr1[u-p]; //inizializzazione array di dimensioni utili
    int * i=p; //puntatore al primo elemento di arr
    int *j=q+1; //puntatore al elemento di mezzo +1 di arr
    int *k= arr1; //puntatore al primo elemento di arr1
    if (u-p==1){ 
        if (*u<*p){
            swap(u,p);
        }
        return;
    }
    while(i<q && j<u){
        if(*i<*j){ 
            *k=*i;
            i=i+1;
        }
        else{
            *k=*j;
            j=j+1;
        }
        k=k+1;
    }
    while(i<q){*k=*i;i++;k++;}
    while(j<u){*k=*j;j++;k++;}

    i=p;
    k=arr1;
    for(i,k;i<&arr[u-p];i++,k++){
        *i=*k;
    }
}

Может кто-нибудь объяснить, что я сделал не так? Большое спасибо !!

PS: Пожалуйста, прости мой действительно плохой английский.

РЕДАКТИРОВАТЬ новый код для предложения Maciej Hehl

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

#define num_elementi(array) (sizeof(array)/sizeof(array[0]))

void swap(int * a, int * b);
void print(int arr[],int n);
void mergesort(int arr[],int * arr_begin,int * arr_end);
void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end);

int main(int argc, char *argv[]){
    int arr[]={99,12,14,65,2,7,54,78,5,1,43,59,88,28,61};
    int n=num_elementi(arr);
    print(arr,n);  
    mergesort(arr,&arr[0],&arr[n-1]);
    print(arr,n);
    system("pause");
}

void swap(int * a, int * b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void print(int arr[],int n){
    int * p=arr;
    for(p;p<&arr[n];p++)printf("%d ",*p);
    printf("\n");
}

void mergesort(int arr[],int * arr_begin,int * arr_end){
    int * med,*arr1,*p,*p1;
    printf("i'm doing something\n");
    if(arr_begin<arr_end){
        med=arr[arr_end-arr_begin]/2+arr_begin;
        mergesort(arr,arr_begin,med);
        mergesort(arr,med+1,arr_end);
        arr1=malloc((arr_end-arr_begin)*sizeof(int));
        printf("msort calls ended begin merge\n");
        merge(arr1,arr_begin,med,med+1,arr_end);
        for(p=arr,p1=arr1;p<arr_end&&p1<&arr1[arr_end-arr_begin];p++,p1++){
            *p=*p1;
        }
    }

}

void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end){
    int *pdest=destination;
    if (r1_end-r1_begin==1){ 
        if (*r1_end<*r1_begin){
            swap(r1_end,r1_begin);
        }
        return;
    }
    if (r2_end-r2_begin==1){ 
        if (*r2_end<*r2_begin){
            swap(r2_end,r2_begin);
        }
        return;
    }
    while(r1_begin<=r1_end&&r2_begin<=r2_end){
        if(*r1_begin<*r2_begin){
            *pdest=*r1_begin;
            r1_begin++;
        }
        else{
            *pdest=*r2_begin;
            r2_begin++;
        }
        pdest++;
    }
    while(r1_begin<r1_end){
        *pdest=*r1_begin;
        r1_begin++;pdest++;        
    }
    while(r2_begin<r2_end){
        *pdest=*r2_begin;
        r2_begin++;pdest++;
    }

}

Answer 1

EDIT

Ваши изменения сделали мой оригинальный ответ (ниже) бессмысленным для других читателей :) О, хорошо ...

Прежде всего необходимо решить, будут ли ваши указатели begin и end определять диапазон [начало, конец) или [начало, конец]. Я предлагаю первый выбор, потому что он используется в библиотеке C ++. Если Вы согласны с этим, звоните

mergesort(arr,&arr[0],&arr[n]);

правильно. Вы должны изменить &arr[n] на &arr[n-1], только если решите, что вы хотите, чтобы указатели begin и end определяли диапазон [начало, конец], который я предлагаю не делать.

На самом деле указателей begin и end достаточно для сортировки диапазона, и вашей функции mergesort не нужен первый параметр.

Неверный расчет med

med=arr[arr_end-arr_begin]/2+arr_begin;

В предыдущей версии это было правильно (переменная называлась q)

Звонки ниже также неверны

mergesort(arr,arr_begin,med);
mergesort(arr,med+1,arr_end);

Первый вызов должен сортировать диапазон [arr_begin, med), а не [arr_begin, med] (*med не принадлежит этому диапазону), поэтому второй вызов должен сортировать диапазон, начиная с med.

Распределение arr1 правильное, благодаря тому, что разница end - begin равна количеству элементов. В этом преимущество выбора диапазона [начало, конец) вместо [начало, конец]. Однако было бы неплохо, если бы Вы освободили выделенную память после использования.

Неверный вызов слияния, как и звонки на mergesort выше. Второй диапазон начинается с med, потому что med указывает за первый диапазон, а не на его последний элемент.

Реализация merge слишком сложна. Вам не нужно ничего менять. Вы просто берете элементы из обоих диапазонов и копируете их в место назначения. Те три цикла, которые начали мой оригинальный пост (ниже), достаточно, но обратите внимание на условия.

Я повторяю еще раз med точек мимо первого диапазона и arr_end точек мимо второго диапазона. Принимая это во внимание, следует ли вам использовать <= или < операторов?

---

Мне не нравится несоответствие в условиях i<=q, j<=u, i<q, j<u в следующем коде:

while(i<=q && j<=u){
    if(*i<*j){ 
        *k=*i;
        i=i+1;
    }
    else{
        *k=*j;
        j=j+1;
    }
    k=k+1;
}
while(i<q){*k=*i;i++;k++;}
while(j<u){*k=*j;j++;k++;}

Вы называете свой слияние следующим образом:

mergesort(arr,&arr[0],&arr[n]);

, что означает, что u является указателем, который указывает на точку после последнего элемента Вашего массива . Другими словами, вы, кажется, думаете о своих указателях, как об итераторах begin и end, которые определяют диапазон [начало, конец) - *begin принадлежит диапазону, но *end нет,

В определении mergesort Вы пишете

int *q=((u-p)/2)+p;
mergesort(arr,p,q);
mergesort(arr,q+1,u);

, что не согласуется с предположениями выше. q может быть равно p, если u == p+1.

mergesort(arr,p,q); означает сортировку диапазона [p, q) (q выходит за пределы диапазона) mergesort(arr,q+1,u); означает сортировку диапазона [q + 1, u) (u выходит за пределы диапазона)

Если бы вы были последовательны в представлении диапазона с указателями, вы бы никогда не коснулись элемента *q таким образом.

Представление о диапазоне как [начало, конец) вместо [начало, конец] (во втором случае *end является частью диапазона) согласуется с тем, как итераторы используются в C ++, но это не обязательно. Вы можете использовать указатели для определения диапазона также вторым способом, но в этом случае вам нужно изменить вызов mergesort(arr,&arr[0],&arr[n]); на mergesort(arr,&arr[0],&arr[n-1]);. В обоих случаях Вы должны переосмыслить условия в коде, приведенном в начале .

Это домашнее задание, поэтому я не буду решать его для Вас, но здесь есть небольшой намек, который может помочь подумать об этом. Переопределите Ваш merge, так что для слияния требуется 2 диапазона:

void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end);

и подумайте, как его использовать. Позже вы можете упростить вещи. Вам не нужен параметр назначения, и вам не нужно копировать все объединенные элементы. Сначала вы можете скопировать только один диапазон, а затем слить его непосредственно в место назначения, извлекая элементы из копии первого диапазона и из второго диапазона.

Answer 2

В основном, если вы добавите printf("*** n=%d\n", n) перед каждым вызовом к print, вы заметите, что перед вторым вызовом вывод будет n=61.То есть, вы хорошо сортируете массив, но когда вы печатаете его второй раз, вы печатаете 61 число.
Вы также можете заметить, что 61 - самое большое число в массиве, а n - этоопределяется сразу после arr, поэтому n и arr будут находиться в последовательных адресах памяти в стеке.Я думаю, что n перезаписывается во время вызова функции mergesoft.
Фактически перезапись происходит, когда вы вызываете mergesoft с помощью &arr[n].Последний элемент массива имеет индекс n-1.Индекс n фактически соответствует переменной n.Измените вызов на: mergesort(arr,&arr[0],&arr[n-1]);