Алгоритм сортировки, который сортирует каждые N элементов массива
Я ищу алгоритм, который сортирует каждый N элемент массива.
Например, предположим, что массив равен 7 8 6 4 5 1 4 3 5, а N равно 3.
Я хочу, чтобы отсортированный массив был 6 7 8 1 4 5 3 4 5
Обратите внимание, что размер массива кратен N.
Я написал приведенный ниже алгоритм для N == 3, но не знаю, как справиться с более высоким значением N.
for ( ll i=0;i<N;i+=3)
{
if (A1[i]> A1[i+1])
{
swap(A1[i+1],A1[i]);
}
if (A1[i+1] > A1[i+2])
{
swap(A1[i+2],A1[i+1]);
}
}
Что такое ll в вашем коде?
это долго долго
Примерно sort(begin(A)+i*N),begin(A)+(i+1)*N), где `i` варьируется от 0 до array.size()/N (остерегайтесь последнего сегмента, который может быть слишком коротким).
В Руби: arr.each_slice(n).flat_map(&:sort).
долго-долго - это long long. Не используйте бессмысленные определения типов, они не помогают, они кусаются.
Ответы 1
Обязательное решение с использованием диапазонов C++20:
#include <algorithm>
#include <iostream>
#include <ranges>
int main()
{
int arr[] = {7,8,6,4,5,1,4,3,5};
int n = 3;
for (auto &&segment : arr | std::views::chunk(n))
std::ranges::sort(segment);
for (int x : arr)
std::cout << x << ' ';
std::cout << '\n';
}
Но поскольку вас, вероятно, попросят реализовать это вручную: создайте функцию сортировки (используя любой желаемый алгоритм), которая просто сортирует весь массив. Вероятно, он примет указатель и длину в качестве параметров (или два указателя). Затем вы можете применить его к отдельным подмассивам в цикле.
Это шикарно! Мне нужно найти время, чтобы посмотреть на диапазоны и тому подобное.
Я бы сказал, что традиционные циклы должны уйти в отставку. <ranges> придает коду безопасность, читабельность и ленивость.
К сожалению, в ассортименте нет пиццы и пива. Но они дают вам больше времени, чтобы сбежать за пиццей и пивом.
Используйте
std::sortarray.size()/N раз в цикле (каждая итерация для следующих N значений).