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

Содержимое удалено Содержимое добавлено
Строка 41:
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
if (l >= r || m < l || m > r) return;
if (r == l + 1 && buf[l] > buf[r]) {
{
swap(buf[l], buf[r]);
return;
Строка 50 ⟶ 49 :
vector<Type> tmp(&buf[l], &buf[l] + (r + 1));
 
for (size_t i = l, j = 0, k = m - l + 1; i <= r; i++i) {
if (*m1j <> *m2m - l) {
{
if(j > m - l) buf[i] = tmp[k++];
} else if(k > r - l) {
buf[i] = tmp[j++];
} else {
buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
{ }
}
}
Строка 76 ⟶ 78 :
int n = 0;
// Сливаем массивы, пока один не закончится
while (l1 && l2) {
if (*m1 < *m2) {
if (*m1 < *m2)
{
ret[n] = *m1;
m1++;
l1--l1;
} else {
else
{
ret[n] = *m2;
m2++m2;
l2--l2;
}
n++n;
}
// Если закончился первый массив
if (l1 == 0) {
for (int i = 0; i < l2; i++i) {
{
for (int i=0; i<l2; i++)
{
ret[n++] = *m2++;
}
} else { // Если закончился второй массив
}
for (int i = 0; i < l1; i++i) {
// Если закончился второй массив
else
{
for (int i=0; i<l1; i++)
{
ret[n++] = *m1++;
}
Строка 117 ⟶ 109 :
int n = 1, l, ost;
T * mas1;
while (n < len) {
{
l = 0;
while (l < len) {
{ if (l + n >= len) break;
ifost = (l + n * 2 >= len) break? (len - (l + n)) : n;
ost = (l+n*2>len) ? (len-(l+n)) : n;
mas1 = merge(mas + l, mas + l + n, n, ost);
for (int i = 0; i < n + ost; i++i)
mas[l+i] = mas1[i]; //тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза
delete [] mas1;
l += n * 2;
}
n *= 2;
Строка 150 ⟶ 141 :
Item *TmpMas = new Item[count];
 
for (int i = 0; i < count; i++i) {
if (j <= medium && k <= right) {
{
if (j <= medium && k <= right)
{
if (Mas[j] < Mas[k])
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
} else {
else
{
if (j <= medium)
TmpMas[i] = Mas[j++];
Строка 169 ⟶ 156 :
 
j = 0;
for (int i = left; i <= right; i++i) {
{
Mas[i] = TmpMas[j++];
}