Сортировка слиянием с указателем на массив

Question

Сортировка слиянием с указателем на массив

Я пытаюсь создать алгоритм сортировки слиянием с библиотекой stl, но у меня возникли некоторые проблемы. Ниже приведен код, который я использую

template <typename Item, typename SizeType>
void merge_sort(Item array[], SizeType size){
size_t n1; //Size of the first subarray
size_t n2; //Size of the second subarray

if(size > 1){
//Compute the size of the subarrays
n1 = size/2;
n2 = size - n1;

//create the temp array.
int* n1Temp = new int[n1];
int* n2Temp = new int[n2];
int i;
for(i = 0; i < n1; i++)
n1Temp[i] = array[i];
for(i = 0; i < n2; i++)
n2Temp[i] = array[i + n1];

//recursive calls
merge_sort(n1Temp, n1);//sort from array[0] through array[n1 - 1]
merge_sort(n2Temp, n2);//sort from array[n1] to the end

//Merge the two sorted halves.
vector<int> v(array, array + size);
merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, v.begin());
copy(v.begin(), v.end(), array);//copy the vector back to the array

delete[] n1Temp;
delete[] n2Temp;
}
}

Код сортируется нормально, но проблема в том, что он действует как алгоритм O (n ^ 2) вместо O (n \ log n), что связано с созданием вектора в каждом вызове сортировки слиянием (я думаю). Я попытался удалить вектор и просто использовать массив в функции слияния, который можно увидеть ниже

    //Merge the two sorted halves.
int* finalArray = new int[n1 + n2];
merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, begin(finalArray));
array = finalArray;

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

2

algorithm c++mergesort

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Как указали и Vaughn, и user93353, вы должны иметь возможность объединяться непосредственно в целевой массив в каждой точке слияния. Но вы все равно можете использовать std :: vector<> Чтобы сделать это значительно проще для себя.

Кроме того, ваши временные массивы имеют прямой тип ‘int’, и я уверен, что это был тип параметра шаблона Item, Я не уверен, что SizeType Параметр для, но я оставил его на случай, если у вас есть особые идеи для этого. Что бы это ни было, лучше быть совместимым с size_t :

template <typename Item, typename SizeType>
void merge_sort(Item array[], SizeType size)
{
if(size > 1)
{
//Compute the size of the subarrays
size_t n1 = size/2;

//create the temp array
std::vector<Item> n1Temp(array, array+n1);
std::vector<Item> n2Temp(array+n1, array+size);

//recursive calls
merge_sort(&n1Temp[0], n1);       //sort array[0] through array[n1-1]
merge_sort(&n2Temp[0], size-n1);  //sort array[n1] through array[size-1]

// merge the sorted halves
std::merge(n1Temp.begin(), n1Temp.end(),
n2Temp.begin(), n2Temp.end(), array);
}
}

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

template <typename Item>
void merge_sort(Item ar[], size_t n)
{
if (n > 1)
{
// Compute the size of the subarrays
size_t n1 = n/2;

// invoke recursion on the submerges
merge_sort(ar, n1);      //sort array[0] through array[n1-1]
merge_sort(ar+n1, n-n1); //sort array[n1] through array[size-1]

// create merge-buffer
std::vector<Item> mrg;
std::merge(ar, ar+n1, ar+n1, ar+n, back_inserter(mrg));
std::copy(mrg.begin(), mrg.end(), ar);
}
}

Общее итераторное решение

Для общего решения, которое обеспечивает еще большую гибкость, вы можете определить сортировку слиянием на основе итераторов, а не указателей элементов. Это становится немного более волосатым, но выгода очень стандартная.

template <typename Iterator>
void merge_sort(Iterator first, Iterator last)
{
typedef typename std::iterator_traits<Iterator>::value_type value_type;
typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

difference_type n = std::distance(first, last)/2;
if (n == 0)
return;

// invoke recursion on the submerges
merge_sort(first, first + n);
merge_sort(first + n, last);

// create merge-buffer
std::vector<value_type> mrg(std::distance(first, last));
std::merge(first, first+n, first+n, last, mrg.begin());
std::copy(mrg.begin(), mrg.end(), first);
}

Наконец, если вы обнаружите, что сортируете тонну C-массивов фиксированной длины, вам может пригодиться следующее (в нем используется решение общего итератора, описанное выше):

// front-loader for C arrays
template<typename Item, size_t N>
void merge_sort(Item (&ar)[N])
{
merge_sort(std::begin(ar), std::end(ar));
}

Это делает следующий код довольно удобным:

int arr[1024];
... fill arr ...
merge_sort(arr);

4