Реализации алгоритмов/Сортировка/Слиянием: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 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;
} 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++;
} else {
ret[n] = *m2;
}
}
// Если закончился первый массив
if (l1 == 0) {
▲ for (int i=0; i<l2; i++)
ret[n++] = *m2++;
}
} 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) {
mas1 = merge(mas + l, mas + l + n, n, ost);
for (int i = 0; i < n + ost;
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;
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 {
if (j <= medium)
TmpMas[i] = Mas[j++];
Строка 169 ⟶ 156 :
j = 0;
for (int i = left; i <= right;
Mas[i] = TmpMas[j++];
}
|