Сортировка слиянием не дает мне выходной - PullRequest
Новая
       14

Сортировка слиянием не дает мне выходной

0 голосов
/ 17 сентября 2018

Я написал этот код сортировки слиянием, вдохновленный книгой deitel (она использует классы). Когда я компилирую код (без ошибок), я получаю вывод несортированного массива, но второй вывод не появляется, как будто он игнорирует эту часть кода. Программа завершается нормально.

Вот код: 

#include <iostream>

using namespace std;

void mergeSort(int*, int);


int main()
{

   const int DIM = 20;
   int vettore[DIM] = { 5, 10, 45, 214, 2, 14, 65, 87, 30, 21, 1, 24, 97, 
                        35, 64, 82, 14, 32, 98, 2};


   for(int i = 0; i < DIM; i++)
       cout << vettore[i] << ' ';

   cout << endl;

   mergeSort(vettore, DIM);

   for(int i = 0; i < DIM; i++)
       cout << vettore[i] << ' ';

   return 0;

}

void sortSubVector(int*, int, int, int); //prototipo
void mergeSort(int* vec, int dim)
{
    sortSubVector(vec, dim, 0, dim-1);
}

void merge(int*, int, int, int, int, int); //prototipo
void sortSubVector(int* vec, int dim,  int low, int high)
{
    if((high - low) >= 1 )
    {
        int middle1 = (high - low) / 2;
        int middle2 = middle1 + 1;

        sortSubVector(vec, dim, low, middle1);
        sortSubVector(vec, dim, middle2, high);

        merge(vec, dim, low, middle1, middle2, high);
    }
}


void merge(int* vec, int dim, int left, int middle1, int middle2, int right)
{
     int leftIndex = left;
     int rightIndex = middle2;
     int tempIndex = left; //indice vettore temporaneo

     int tempVector[ dim ]; //qui verranno posizionati gli elementi ordinati

   while(leftIndex <= middle1 && rightIndex <= right)
   {
       if(vec[leftIndex] <= vec[rightIndex])
           tempVector[tempIndex++] = vec[leftIndex++];
       else
           tempVector[tempIndex++] = vec[rightIndex++];
   }

  /* gli elementi di una metà sono stati tutti posizionati in ordine, ma 
     mancano gli elementi dell'altra metà */ 

     if(leftIndex == middle2) //la prima metà è stata completata
         while(rightIndex <= right)
             tempVector[tempIndex++] = vec[rightIndex++];
     else                    //la seconda metà è stata completata
         while(leftIndex <= middle1)
             tempVector[tempIndex++] = vec[leftIndex++];

   /*il vettore temporaneo è pieno e ordinato. Copiamolo nel vettore 
     originale*/

    for(int i = 0; i < dim; i++)
       vec[i] = tempVector[i];
 }

Где проблема? Пожалуйста, помогите мне. Спасибо.

Ответы [ 3 ]

0 голосов
/ 18 сентября 2018

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

Вот более похожая на c ++ реализация 

#include <iostream>
#include <array>
#include <algorithm>

template <typename T>
void print(const T& array) {
    for (const auto& item : array) {
        std::cout << item << ' ';
    }

    std::cout << std::endl;
}

int main() {
    const int DIM = 20;
    std::array<int, DIM> vec = {5, 10, 45, 214, 2, 14, 65, 87, 30, 21, 1, 24, 97, 35, 64, 82, 14, 32, 98, 2};

    print(vec);

    std::sort(vec.begin(), vec.end());

    print(vec);
    return 0;
}

Пожалуйста, обратите внимание на следующие пункты

  • Используйте контейнеры, предоставляемые стандартной библиотекой, такие как std::vector и std::array.
  • Используйте алгоритм, предоставляемый стандартной библиотекой, такой как std::sort.
  • Не использовать using namespace std
  • Боб Мартин (в своей книге Clean Code) предлагает использовать только английские имена для переменных. Таким образом, используйте vec вместо итальянского vettore.
0 голосов
/ 18 сентября 2018

Я сделал это, чтобы узнать, как работает сортировка слиянием, потому что это необходимо для сдачи экзамена. Я знаю, что существуют алгоритмы из библиотеки std, я узнал об этом по своей книге. Я использовал итальянское имя, потому что я итальянский (да, местный и глупый), но я должен научиться использовать английское слово только так, как вы говорите

0 голосов
/ 18 сентября 2018

спасибо за комментарии, ребята.Я нашел ошибку.в функции sortSubVector, в переменной middle1 я вычисляю (high - low) / 2, но в случае high = 3 и low = 2 я получаю неправильный индекс и получаю ошибку ошибки сегментации.я исправил это вычисление middle1 = (low + high) / 2 и теперь оно работает!

благодаря вам я учусь использовать отладчик для поиска ошибок, большое спасибо!

...