Викиучебник

Реализации алгоритмов/Сортировка/Слиянием: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Строка 1:
{{wikipedia|Сортировка слиянием}}
== [[w:C++|C++]] ==
<source lang="cpp">
 
/**
* @brief Сортировка элементов от left до right массива buf
* @param[in/out] buf - сортируемый массив
* @param[in] left - левая граница. При первой итерации left = 0
* @param[in] right - правая граница. При первой итерации right = buf.size() - 1
*
* В результате сортируются все элементы массива buf от left до right включительно.
*/
template<typename Type>
void MergeSort(vector<Type>& buf, size_t left, size_t right)
{
//! Условие выхода из рекурсии
if(left >= right) return;
 
size_t middle = left + (right - left) / 2;
 
//! Рекурсивная сортировка полученных массивов
MergeSort(buf, left, middle);
MergeSort(buf, middle + 1, right);
merge(buf, left, right, middle);
}
 
/**
* @brief Слияние элементов.
* @param[in/out] buf - массив
* @param[in] left - левая граница. При певой итерации left = 0
* @param[in] right - правая граница. При первой итерации right = buf.size() - 1
* @param[in] middle - граница подмассивов.
*
* Массив buf содержит два отсортированных подмассива:
* - [left; middle] - первый отсортированный подмассив.
* - [middle+1; right] - второй отсортированный подмассив.
* В результате получаем отсортированный массив, полученный из двух подмассивов,
* который сохраняется в buf[left; right].
*/
template<typename Type>
static void merge(vector<Type>& buf, size_t left, size_t right, size_t middle)
{
if (left >= right || middle < left || middle > right) return;
if (right == left + 1 && buf[left] > buf[right]) {
swap(buf[left], buf[right]);
return;
}
 
vector<Type> tmp(&buf[left], &buf[left] + (right + 1));
 
for (size_t i = left, j = 0, k = middle - left + 1; i <= right; ++i) {
if (j > middle - left) {
buf[i] = tmp[k++];
} else if(k > right - left) {
buf[i] = tmp[j++];
} else {
buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
}
}
}
 
</source>
 
Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
 
<source lang="cpp">
 
/*
* Слияние двух упорядоченных массивов
* m1 - Первый массив
* m2 - Второй массив
* len_1 - Длина первого массива
* len_2 - Длина второго массива
* Возвращает объединённый массив
*/
template <class T>
T* merge(T *m1, T* m2, int len_1, int len_2)
{
T* ret = new T[len_1+len_2];
int n = 0;
// Сливаем массивы, пока один не закончится
while (len_1 && len_2) {
if (*m1 < *m2) {
ret[n] = *m1;
m1++;
--len_1;
} else {
ret[n] = *m2;
++m2;
--len_2;
}
++n;
}
// Если закончился первый массив
if (len_1 == 0) {
for (int i = 0; i < len_2; ++i) {
ret[n++] = *m2++;
}
} else { // Если закончился второй массив
for (int i = 0; i < len_1; ++i) {
ret[n++] = *m1++;
}
}
return ret;
}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
int n = 1, k, ost;
T * mas1;
while (n < len) {
k = 0;
while (k < len) {
if (k + n >= len) break;
ost = (k + n * 2 > len) ? (len - (k + n)) : n;
mas1 = merge(mas + k, mas + k + n, n, ost);
for (int i = 0; i < n + ost; ++i)
mas[k+i] = mas1[i];//тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза
delete [] mas1;
k += n * 2;
}
n *= 2;
}
}
</source>
 
Пример:
char a[] = "ASORTINGEXAMPLE";
mergeSort(a, 16);
Альтернативная версия алгоритма Сортировки Слиянием.
<source lang="cpp">
template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
int j = left;
int k = medium + 1;
int count = right - left + 1;
 
if (count <= 1) return;
 
Item *TmpMas = new Item[count];
 
for (int i = 0; i < count; ++i) {
if (j <= medium && k <= right) {
if (Mas[j] < Mas[k])
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
} else {
if (j <= medium)
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
}
}
 
j = 0;
for (int i = left; i <= right; ++i) {
Mas[i] = TmpMas[j++];
}
delete[] TmpMas;
}
 
template <typename Item>
void MergeSort(Item a[], int left, int right)
{
int middle;
 
// Условие выхода из рекурсии
if(left >= right) return;
 
middle = left + (right - left) / 2;
 
// Рекурсивная сортировка полученных массивов
MergeSort(a, left, middle);
MergeSort(a, middle + 1, right);
Merge(a, left, right, middle);
}
 
</source>
 
==[[w:C Sharp|C#]]==
<source lang="csharp">
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Слиянием