Сортировка массива с помощью сортировки слиянием

ProgramBox

Сортировка массива с помощью сортировки слиянием

Post author:admin
Запись опубликована:10 декабря, 2022
Post category:Вопросы по программированию

#c #sorting #merge #conditional-statements #output

#c #сортировка #слияние #условные операторы #вывод

Вопрос:

Я использую сортировку слиянием для убывания моего массива. В чем причина того, что мой первый элемент изменил свое значение? Моя половина кода работает. Но с моими первым и последним элементами что-то пошло не так.

 #include <iostream>

void Merge(int a[], int low, int high, int mid)
{
    int i = low, j = mid   1, k = 0;
    int temp[high - low   1];

    while (i <= mid amp;amp; j <= high) {
        if (a[i] > a[j])
            temp[k  ] = a[i  ];

        else
            temp[k  ] = a[j  ];
    }

    while (i <= mid) {
        temp[k  ] = a[i  ];
    }

    while (j <= high) {
        temp[k  ] = a[j  ];
    }
    for (i = low; i <= high; i  ) {
        a[i] = temp[i - low];
    }
    return;
}

void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low < high) {
        mid = (low   high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid   1, high);

        Merge(a, low, high, mid);
    }

    return;
}

void output(int* a, int n)
{
    for (int i = 0; i < n; i  ) {
        std::cout << a[i] << "t";
    }
}

int main()
{
    int n;
    std::cin >> n;
    int a[n];
    for (int i = 0; i < n; i  ) {
        std::cin >> a[i];
    }
    MergeSort(a, 0, n);
    output(a, n);
}

Результат должен быть таким.

ввод 10

 1 2 3 4 5 6 7 8 9 10

вывод

 10 9 8 7 6 5 4 3 2 1

Но я получаю этот
вывод

 4197055 10  9   8   7   6   5   4   3   2

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

1. этот код кажется работающим, но не может быть воспроизведен. godbolt.org/z/nPqhn3

2. @foragerDev нет, это не работает godbolt.org/z/G9GPnv классический пример неопределенного поведения. (godblot с gcc может отображать номера строк: godbolt.org/z/1M7vrj )

3. @MarekR на моей машине я этого не понимаю.

4. @foragerDev опять же, это неопределенное поведение, поэтому оно может привести к сбою, оно может ничего не делать, оно может печатать tash. Обратите внимание, единственное отличие заключается в том, что я включил средство очистки адресов.

5. Вы передаете n как high . Но n на единицу выше индекса самого высокого элемента, что вызывает неопределенное поведение. MergeSort(a,0,n-1); решит проблему.

Ответ №1:

Вы перепутали, как описываются диапазоны индексов. В тех же случаях вы закрыли эти диапазоны в конце, а в других открыли в конце. Результатом является переполнение буфера неопределенного поведения.

Здесь исправлена версия, в которой low указывает на первый элемент и high указывает на один шаг дальше последнего элемента.

Помните, что в C индексы массива arr[n] должны быть от 0 до n - 1 включительно.

 void Merge(int a[], int low, int high, int mid)
{
    int i = low, j = mid, k = 0;
    int temp[high - low];

    while (i < mid amp;amp; j < high) {
        temp[k  ] = a[i] < a[j] ? a[i  ] : a[j  ];
    }

    while (i < mid) {
        temp[k  ] = a[i  ];
    }

    while (j < high) {
        temp[k  ] = a[j  ];
    }

    for (i = low; i < high; i  ) {
        a[i] = temp[i - low];
    }
    return;
}

void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low   1 < high) {
        mid = (low   high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid, high);

        Merge(a, low, high, mid);
    }

    return;
}

https://godbolt.org/z/nET5YT

Ответ №2:

  #include <iostream>
    using namespace std;
    void merge(int arr[], int l, int m, int r)
    {
        int n1 = m - l   1;
        int n2 = r - m;
     
        int L[n1], R[n2];
    
        for (int i = 0; i < n1; i  )
            L[i] = arr[l   i];
        for (int j = 0; j < n2; j  )
            R[j] = arr[m   1   j];
    
        int i = 0;
     
        int j = 0;
    
        int k = l;
     
        while (i < n1 amp;amp; j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i  ;
            }
            else {
                arr[k] = R[j];
                j  ;
            }
            k  ;
        }
     
        while (i < n1) {
            arr[k] = L[i];
            i  ;
            k  ;
        }
    
        while (j < n2) {
            arr[k] = R[j];
            j  ;
            k  ;
        }
    }
     
    void mergeSort(int arr[],int l,int r){
        if(l>=r){
            return;
        }
        int m = (l r-1)/2;
        mergeSort(arr,l,m);
        mergeSort(arr,m 1,r);
        merge(arr,l,m,r);
    }
    
    void output(int A[], int size)
    {
        for (int i = size - 1; i >= 0; i--)
            cout << A[i] << " ";
    }
    
    int main()
    {
        int arr[] = { 1, 2, 3, 5, 6, 7 };
        int arr_size = sizeof(arr) / sizeof(arr[0]);
     
        mergeSort(arr, 0, arr_size - 1);
     
        output(arr, arr_size);
        return 0;
    }

Ответ №3:

Измените эту строку: Merge(a, low, high-1, mid); поскольку вы используете индексацию на основе нуля.

Обновление: предыдущее изменение работает не во всех случаях.

Попробуйте только это изменение: MergeSort(a, 0, n-1)

Попробуйте использовать индексацию на основе 1, чтобы избежать такого случая