AC
// copy elements from both arrays until either array gets emptied
while (e1 < arr1.length && e2 < arr2.length) {
копировать элементы с обоих массивов, пока оба из них не опустеют или один из них?
я так понимаю это код
Size: a a a
AC
AC
class MergeSort extends SortingAlgorithm {
/
* Логика сортировки слиянием
* подразумевает разбиение массива поровну до тех пор пока из одного массива не получится несколько
* мелких — размером не более двух элементов.
* После разбиения следует обратное слияние, выбираются по одному первому элементу от каждого массива и сравниваются между собой.
* Наименьший элемент отправляется в результирующий массив,
* оставшийся при первом сравнении элемент остается актуальным для сравнения с элементом из другого массива на следующем шаге
* Время выполнения: O(nlogn);
*/
MergeSort() {
this.name = "Сортировка слиянием (MergeSort)";
}
@Override
void sortAsc(double[] values) {
int l = 0;
int u = values.length - 1;
int mid = l + (u - l) / 2;
if (u > l) {
// Создаем первый подмассив для левой части массива и рекурсивно применяем к нему sortAsc
double[] array1 = new double[mid + 1 - l];
for (int i = 0; i < array1.length; i++)
array1[i] = values[l + i];
sortAsc(array1);
// Создаем второй подмассив для правой части массива и рекурсивно применяем к нему sortAsc
double[] array2 = new double[u - mid];
for (int i = 0; i < array2.length; i++)
array2[i] = values[mid + i + 1];
sortAsc(array2);
// слияние двух отсортированных выше массивов
double[] mArr = mergeSortedArrays(array1, array2);
// заполнение массива values отсортированными значениями из массива mArr
for (int i = 0; i < mArr.length; i++)
values[i] = mArr[i];
}
}
@Override
void sortDesc(double[] values) {
sortAsc(values);
ReverseArray.reverse(values);
}
/
* Слияние двух массивов и возвращение результата
*/
double[] mergeSortedArrays(double[] arr1, double[] arr2) {
int len = arr1.length + arr2.length;
double[] values = new double[len];
int e1 = 0;
int e2 = 0;
int i = 0;
// копировать элементы с обоих массивов, пока оба из них не опустеют
while (e1 < arr1.length && e2 < arr2.length) {
// копируем подходящий элемент из двух для сортировки
if (arr1[e1] < arr2[e2])
values[i++] = arr1[e1++];
else
values[i++] = arr2[e2++];
}
// копируем оставшиеся элементы из первого массива если остались
while (e1 < arr1.length)
values[i++] = arr1[e1++];
// копируем оставшиеся элементы из второго массива если остались
while (e2 < arr2.length)
values[i++] = arr2[e2++];
return values;
}
}
A5
DS
class MergeSort extends SortingAlgorithm {
/
* Логика сортировки слиянием
* подразумевает разбиение массива поровну до тех пор пока из одного массива не получится несколько
* мелких — размером не более двух элементов.
* После разбиения следует обратное слияние, выбираются по одному первому элементу от каждого массива и сравниваются между собой.
* Наименьший элемент отправляется в результирующий массив,
* оставшийся при первом сравнении элемент остается актуальным для сравнения с элементом из другого массива на следующем шаге
* Время выполнения: O(nlogn);
*/
MergeSort() {
this.name = "Сортировка слиянием (MergeSort)";
}
@Override
void sortAsc(double[] values) {
int l = 0;
int u = values.length - 1;
int mid = l + (u - l) / 2;
if (u > l) {
// Создаем первый подмассив для левой части массива и рекурсивно применяем к нему sortAsc
double[] array1 = new double[mid + 1 - l];
for (int i = 0; i < array1.length; i++)
array1[i] = values[l + i];
sortAsc(array1);
// Создаем второй подмассив для правой части массива и рекурсивно применяем к нему sortAsc
double[] array2 = new double[u - mid];
for (int i = 0; i < array2.length; i++)
array2[i] = values[mid + i + 1];
sortAsc(array2);
// слияние двух отсортированных выше массивов
double[] mArr = mergeSortedArrays(array1, array2);
// заполнение массива values отсортированными значениями из массива mArr
for (int i = 0; i < mArr.length; i++)
values[i] = mArr[i];
}
}
@Override
void sortDesc(double[] values) {
sortAsc(values);
ReverseArray.reverse(values);
}
/
* Слияние двух массивов и возвращение результата
*/
double[] mergeSortedArrays(double[] arr1, double[] arr2) {
int len = arr1.length + arr2.length;
double[] values = new double[len];
int e1 = 0;
int e2 = 0;
int i = 0;
// копировать элементы с обоих массивов, пока оба из них не опустеют
while (e1 < arr1.length && e2 < arr2.length) {
// копируем подходящий элемент из двух для сортировки
if (arr1[e1] < arr2[e2])
values[i++] = arr1[e1++];
else
values[i++] = arr2[e2++];
}
// копируем оставшиеся элементы из первого массива если остались
while (e1 < arr1.length)
values[i++] = arr1[e1++];
// копируем оставшиеся элементы из второго массива если остались
while (e2 < arr2.length)
values[i++] = arr2[e2++];
return values;
}
}
A
A
AN
t
AN
t
HR
MN
GV
MN
MN
GV
GV
QH
AL
MN