"Дан массив из n чисел.
Нужно разбить массив на макимальное количество непрерывных подмассивов так, чтобы
после сортировки элементов внутри каждого подмассива весь массив стал отсортированным."


Разве можно сортирнуть массив, например, разбив массив на два куска, отсортировать каждый кусок и получить весь массив отсортированным?
Или я не понимаю задачу?

(48)+ Хотя пофиг строка это в принципе число

(48) нет, без напильника не будет

А если значения одинаковые?

(51)+ Причем есть 2, 2 и еще и 4

(51) будет, из-за этого соединение тяжелое получилось
ПО (ВТ.Значение > ВТ1.Значение
                ИЛИ ВТ.Значение = ВТ1.Значение
                    И ВТ.Номер >= ВТ1.Номер)

для уникальных можно было бы проще
ПО ВТ.Значение >= ВТ1.Значение

(39) 2314 возвращает 2, что не верно

(54) Верно
(231) и (4)

Всем спасибо. Вроде бы прояснилось.

(54) верно

должно быть 0

Что вернет 2 4 1 2 ?

(58) меньше 1 не может быть)

(59) у меня уже курсы))

(57) а ну да..

(59) косяк какой-то. Пусто. Похоже что-то в (53) недоделал)

(47) По сути это аппроксимация, так что все правильно сказал про переломы

(64)+ Но работает только для возрастающих или убывающих функций (с локальными колебаниями) на всем промежутке анализа

*(63) Не, всё работает (когда с курсами игрался к первому значению "где ложь" поставил, блиииин)
(59) Возвращает 1

(66) Надо проверять на разных наборах тестовых, алгоритмы на основе различия/совпадений сумм значений не очень надежны.

(65) Нашлись как оказалось даты объявления санкций +/-
(67) Алгоритм примитивен, в (39) ошибок нет.

Вообще "алгоритмы ... не очень надежны" значит, что алгоритм неправильный.

Чем то напоминает задачку про "поменять значения двух числовых переменных не пользуясь дополнительными переменными".
a=2
b=5

сделать чтобы
a=5
b=2

b=b+a
a=b-a
b=b-a

(56) Источник озвучь, если не секрет конечно

(68) Не очень надежны, это значит есть строгие ограничения на условие задачи.
Ну и вытекает что очень сложно модифицировать алгоритм для обхода этих ограничений.

(71) условия из (0) решены в (39).
Точнее решены наполовину: нужна ещё обратная сортировка и выбор большего из двух вариантов прямой/обратный.
Без запроса решается в один синхронный проход трёх массивов: исходного, возрастающего и убывающего. Подготовка служебных массивов естественно за пределами оценки O(N).

(71) Идею-то так и не поднял?

Коммутативность сложения

(0) Кому нужны эти сортировки? Все алгоритмы сортировки уже давно придуманы. И в реальных задачах нужно будет другими вещами.

(75) Вы не правы очень сильно, потому что когда будет "Все алгоритмы ... уже давно придуманы" то будет технический регресс или как минимум стагнация.

Например сейчас очень быстро развиваются параллельные алгоритмы, распределенные вычисления и различные ML.
Там еще много-много придумывать...

(75)+ Я к тому что эта задача из разряда как раз параллельные алгоритмы и/или распределенные вычисления

Сначала быстро делим исходный массив на кусочки которые надо будет отсортировать.
А затем сортируем их по отдельности на разных ядрах или компах.

(74) похоже на правду), точно используется

Кста интересно можно ли поделить не имея/готовя отсортированный массив?

(79) к (72)

(79) Гм можно

(81) возможно, наверное. Только сложность может больше получиться

(82) Ага наверно

Суть создаем множество объектов (списков, множеств) каждый из которых характеризуется минимальным и максимальным значением, содержащихся внутри значений.
И постепенно заполняем их при одном проходе по исходному и этому списку объектов, помещая внутрь если новое значение >мин но <макс.

Если значение >макс то или <мин то создается новый объект

(82) Да сложность чуть меньше чем O(n^2)

2 3 1 4

2
23
23 12
23 12 4

Совмещаем по мин и макс эти объекты
123 4

Итого два подмассива

1 кусок

(85)+ Но потеряли исходную информацию где были изначально значения

(86) Если ты про (85) то 4 стоит на своем месте и образует отдельный подмассив

(84) можно вроде в O(n) без сортировки, прохода 3 должно хватить (если только возрастание рассматриваем)

(85)+ распишу
2 3 1 5 4

1.Берем первые два элемента =2 и =3
(мин 2, макс 3)

2.Берем 3-й элемент =1
1<2 и 1<3 внутрь не попадет, значит образует новую группу, причем второй парой берем ближайший из мин или макс других объектов-групп это 2
Было 2-3 и добавили 1-2

3.Берем 4-й =5
5>3 и 5>2 ближайшее 3 значит новая группа
Было 2-3 и 1-2 добавили 3-5

4.Берем 5-й =4
он попадает в 3-5, добавляем туда
Было 2-3 и 1-2 и стало 3-4-5

5.Совмещаем по совпадающим мин=макс (только один раз уже совмещенные группы не совмещаем далее)
1-2 с 2-3 = 1-2-3
2-3 с 3-4-5 = 2-3-4-5

6.Получили две группы 1-2-3 и 2-3-4-5 значит два подмассива, причем группы кривые
И правильные подмассивы (2 3 1) и (5 4) не отражают, инфа потеряна

Короче вроде бы работает но я хз.
Кто может найти ошибку у меня?

Слишком сложно (90) , завтра с компа (89) напишу, если тема жива будет

(89) (91) Может количество проходов будет 1+КолвоЭлементов-КолвоПодмассивов ?

(92) нет, проходов 2-4. Подмассивов не надо. 2(или 4 если в обе стороны) служебных массива

(93) Проблемы с проходами по служебным массивам в цикле по основному, я не понимаю как этого избежать

А совпадающие значения могут быть?

(95) в общем случае могут. Но вроде вопрос не принципиальный, если только не пытаться решить запросом)

ТС, ответь на (70), пожалуйста

Оцените, что получилось.

Пусть p - счетчик подмассивов,
изначально р=1.

Скопируем данный массив $a[n]$ в новый - $b[n]$,
отсортируем его - $O(nlogn)$,
создадим вспомогательный массив $count[n]$,
заполним его значением "0".

будем идти по исходному массиву и если
1. a[j]=i, => count[i] = 1,
после переходим к $b[j]$, если
2. b[j]=k, => a[k] = -1,
далее рассматриваем a[j+1] и т.д. - сложность O(n)

Если в какой-то момент времени, после действия 2. сумма всех значений массива count=0, то данный отрезок можно отнести в подмассив, тогда увеличим счетчик подмассивов - p++

(98) ничего не понятно. p, i, j, k?
Откуда задача?

Есть простое решение. Без сортировок. Два линейных цикла не вложенных. И никаких массивов подмассивов.

(100) Давай уже решение, не обязательно код хотя бы алгоритм

(98) Сортировка массива какая сложность?

(101) Код будет, но всё-таки хочется узнать источник)

В общем алгоритм:
Находим такое значение, что в первом подмассиве все значения будут меньше его, а во втором - больше. Если такое значение больше максимального в массиве или меньше минимального - значит данный подмассив разбить нельзя.
В каждом полученном подмассиве пытаемся сделать то же самое.
В итоге получится, что на определенном этапе итерации закончатся и мы получим общее количество таких подмассивов.

как я понял ключевое слово НЕПРЕРЫВНЫХ,
те для 2 3 4 1 - это 1 подмассив
ля 8 2 6 3 7 - это 2 3 и 6 7 8

(104)+ Все упирается именно в процесс поиска нужного числа. Как вариант - в качестве первой попытки выбираем среднее по подмассиву. Потом сравниваем значения с ним. Если до определенного элемента в массиве все числа меньше его, а в другой - больше - тогда можно делить. Если то меньше, то больше - то идем в сторону сопротивления. Например 6 чисел из 10 меньше, а потом идет то больше, то меньше. Значит увеличиваем число и снова проверяем. И так далее, пока не упремся до конца массива или не получится найти состояние "дзен", когда условие выполняется. Если условие достигнуто - начинаем попытку деления в каждом полученном подмассиве. Если не получается - итерация закончена.

(104) >Находим такое значение, что в первом подмассиве все значения будут меньше его, а во втором - больше

Решение:
1) Нормализауем массив сортировкой. Получаем массив-перестановку, в котором заданы числа от 1 до n
2) В перестановке находим все циклы. Например на 1 месте стоит 3, на 3 месте стоит 7, на 7 месте стоит 1.
Цикл 1->3->7->1 замкнулся.
3) Выделяем границы цикла. Для цикла 1->3->7->1 - границы 1 и 7
4) Объединяем циклы, границы которых пересекаются. Это и есть искомые подмассивы

(107)+ Ай молодца только ты алгоритм то нахождения скажи без двойного цикла?

(108) С предварительной сортировкой уже давно решили, без нее как?

(110) Что значит, без предварительной сортировки? Быстрее чем 0(N * log N) ? Боюсь, невозможно

(111) см мои посты (83)(85)(90)

(112)+ Я только доказать не могу что алгоритм рабочий и не выдаст ошибки

(111) O(N) возможно.
Прикольная задачка, школьники после прохождения циклов с большИм чем мисятяне успехом её бы решали.

(109) Смотри (106)
Там вроде вполне понятный поиск

(115) Что такое "среднее по подмассиву"? Как его нашли? Сколько на нахождение затратили?

Что если среднее не совпало не с одним из имеющихся в массиве значений?

2 1 5 4, ну нету 3 нету

(116) И что? Проверяем на нем. Если не подходит - то увеличиваем его в случае если справа идет "то больше то меньше", или уменьшаем, если слева. Конечно, данное решение имеет определенные недостатки и ограничения, но в простых случаях должно сработать

(117)+ Среднее находим как среднее арифметическое. Надеюсь, как его найти в числовом массиве - понятно

(117) сколько раз увеличиваем?

(119) Пока не окажется, что все числа в подмассиве больше или все числа в подмассиве меньше этого числа.

То есть цикл типа Do While

(114) первый цикл для затравки

//А - входящий массив

    Колво = А.Количество();
    МинНач = Новый Массив(Колво);
    МинКон = Новый Массив(Колво);
    МаксНач = Новый Массив(Колво);
    МаксКон = Новый Массив(Колво);
    
    МинНач[0] = А[0];
    МаксНач[0] = А[0];
    МинКон[Колво - 1] = А[Колво - 1];
    МаксКон[Колво - 1] = А[Колво - 1];
    
    Для инд = 1 По Колво - 1 Цикл
        МинНач[инд] = Мин(А[инд], МинНач[инд-1]);
        МаксНач[инд] = Макс(А[инд], МаксНач[инд-1]);
        МинКон[Колво - 1 - инд] = Мин(А[Колво - 1 - инд], МинКон[Колво - инд]);
        МаксКон[Колво - 1 - инд] = Макс(А[Колво - 1 - инд], МаксКон[Колво - инд]);
    КонецЦикла;

второй цикл

    КолПодмассивовУбыв = 1;
    КолПодмассивовВозр = 1;
    Для инд = 0 По Колво - 2 Цикл
        КолПодмассивовВозр = КолПодмассивовВозр + ?(МаксНач[инд] <= МинКон[инд+1], 1, 0);
        Если МаксНач[инд] <= МинКон[инд+1] Тогда
            Сообщить(""+инд +"    "+  МаксНач[инд] +"    "+ МинКон[инд+1]);
        КонецЕсли;
        
        КолПодмассивовУбыв = КолПодмассивовУбыв + ?(МинНач[инд] >= МаксКон[инд+1], 1, 0);
    КонецЦикла;
    
    Результат = Макс(КолПодмассивовВозр, КолПодмассивовУбыв);

(123)
Помоему, липа.
Что получается на последовательности 3,2,7,1,6,5,4
Разбить такую последовательность на подмассивы нельзя из-за 3->7->4->1->3, а второй цикл из (123) на первом проходе уже больше дает

(124) У меня вернул 1.
Что значит "на первом проходе"?

при инд=1.
КолПодмассивовВозр = КолПодмассивовВозр + ?(МаксНач[1] <= МинКон[1+1], 1, 0);

МинКон[2]= 4
МаксНач[1] =3
Те КолПодмассивовВозр = КолПодмассивовВозр+1

т.е. инд =0

(126) МинКон[2] = 1;//минимальное значение от А[2] до конца массива

МаксНач
Индекс    Значение элемента
0    3
1    3
2    7
3    7
4    7
5    7
6    7

МинКон
Индекс    Значение элемента
0    1
1    1
2    1
3    1
4    4
5    4
6    4

(129) Точно, не заметил, что массив перевернут

(130) Это из-за экономии на циклах)), хотелось в два уложиться

(131) Наконец то я понял, что делает алгорим из (123), переведу на русский.
Первым проходом подготовливаются максимумы-минимумы, суть которых будет ясна ниже.
Вторым проходом пытаемся разрезать последовательность на две.
Для того, чтобы последовательность разрезалась удачно, все числа из первой части, должны быть меньше, чем все числа из второй части. Вместо сравнения всех чисел, сравниваются заранее подготовленные максимумы-минимумы из первого прохода.

(132) Спасибо за перевод.
Мне казалось, что даже первого цикла должно хватать для понимания идеи. Надо было комменты к служебным массивам сделать.

(133) Можешь это оформить в виде готовой функции?
Желательно чтобы оно и границы подмассивов выдавало сразу.

Ну и следующий шаг а можно ли и этот алгоритм распараллелить так чтобы получилось готовое для очень быстрой параллельной сортировки на множестве ядер.

Т.е. вот эта подготовка пары служебных массивов ее можно на кусочки поделить, делать больше массивов а потом их состыковать?

(134) Склей два поста, получишь готовую функцию. A - входящий параметр, Результат на выходе. Можно оптимизировать в два раза, проверять только на убывание или возрастание.

Для каких целей ты его параллелить собрался - не понял. 1С тебе миллионный массив обработает за секунду (если сообщить убрать), что-то си-подобное - миллиарды в секунду.

Задачка абсолютно учебная и базовая, оптимизировать здесь нечего.

(135) Когда числа простые да, но бывает надо сортировать нечто чуть посложнее чем просто числа.

А насчет сортировки миллиардов в секунду это ты загнул конечно ))

Уже миллионы весьма сильно тормозит на одном ядре. Хотя у нас тут сотни и тысячи простых ядер в GPU простаивают.

(136)+ Например сортировка строк уже весьма сложная штука

(137) весь вопрос не в сортировке, а в сравнении строк

алгоритм то не меняется

(136) про сортировку никто не говорил, речь про конкретный алгоритм. И тут будет несколько миллиардов простых операций на миллиард элементов, для современных гигагерцовых процов - секунды.

Если ты этой хренью собираешься сортировку оптимизировать, забудь. Там всё уже придумано до нас.

(138) В первом цикле 4 операции сравнения, во втором 3 операции.
Итого 7 операций сравнения O(n) алгоритма

Далее делим и сортируем параллельно по кол-ву подмассивов причем алгоритм сортировки O(n^2), и на каждом шаге идет операция сравнения.
В худшем случае практически тоже самое, в лучшем выигрыш от кол-ва подмассивов.

Просто сравнить 7*N+(n-X)*(n-X) и 1*n*n

(140) Параллельную сортировку

(141) у сортировки слиянием сложность O(n log2 n) и это лучше чем O(n^2)

(143) Пофиг, в любом случае если массив сортировать не целиком а по раздельным подмассивам то это лучше.
Параллельно сортируются подмассивы и затем собираются в один.

(144) тут главное вовремя остановиться плодить потоки

(145) https://ru.wikipedia.org/wiki/OpenCL
https://ru.wikipedia.org/wiki/GPGPU

И стандартные характеристики нынешней самой дешевой видяхи:
"Количество универсальных процессоров - 192"

(146)+ Видеокарта чуть получше типа GT 1050 ti
Количество универсальных процессоров
768

И до нескольких тысяч у топовых видях за бешенные бабки.

(142) (144)
Во-первых это всё уже есть (если это кому-то нужно),
во-вторых это применимо очень для немногих массивов, в любом случайном массиве будет в среднем один подмассив из (0).