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


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

(0) Отсортированным в любую сторону?

ничего не сказано, но это разве меняет суть дела?

все равно эти подмассивы нужно потом сливать, а не соединять!

(0) Если нельзя, тогда ответ - максимальное количество частей = 1.

https://ru.wikipedia.org/wiki/Быстрая_сортировка

https://ru.wikipedia.org/wiki/Сортировка_слиянием

Например, массив

2 1 4 3 можно "разбить" на две части

1 2 4 3 можно "разбить" на три части

1 2 3 4 можно "разбить" на четыре части

2 3 4 1 нельзя разбить

(5)(6) не понял, ссылки, они к чему, про точ есть разные виды сортировок еще Кнут писал.

(7) идет речь о сортировке ВНУТРИ подмассива

(7) >2 3 4 1 нельзя разбить
на одну часть разбивается


>1 2 3 4 можно "разбить" на четыре части
можно и не разбивать оно уже но да макс =4

(9) Сведи размер массива к 1 и сортируй. Потом слияй.

(0) Задача сводится к нахождению последовательностей на своих местах в пределах перестановок.

Попробуй для начала в лоб полным перебором решить.
Для массива из 4-х элементов есть варианты
4
1 3
2 2
3 1
1 2 1

(12) слова понятные, смысл не очень.
какой например массив из 4 элементов?
Конкретно вот этот 2 3 4 1
что тут нужно?

Т.е. по очереди проверяем соседние элементы по 1, 2, 3 и т.д. будут ли они на своих местах после сортировки.

Сначала делаем копию исходного массива и сортируем его как надо.

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

Если не совпадают то берем по 2 элемента и так же после сортировки проверяем на совпадение с правильным. Если совпали то это подмассивы из 2 элементов.

Ну и т.д. для 3, 4 и т.д. до длины массива.

По сути находится список всех возможных подмассивов, далее их надо сопоставить так чтобы собрался правильный целый массив.
Вариантов может быть несколько и надо среди правильных собранных выбрать с максимальным числом подмассивов.

(13) 2 3 4 1

По 1 элементу нет готовых подмассивов, проверям по 2 элемента
(2 3) являются таким подмассивом
Еще дойдя до 4 элементов получаем (2 3 4 1)

Итого из возможных подмассивов (2 3) и (2 3 4 1) пытаемся составить полный
Вариант только (2 3 4 1) - итого всего на 1 можно разделить

(15) Тьфу (2 3) не являются ошибся только вариант (2 3 4 1) будет сразу

Например для 2 1 4 3

из 1 нет, из 2 есть (2 1) и (4 3)
Из 3 нет, из 4 есть (2 1 4 3)

(2 1) собирается с (4 3) и еще есть готовый (2 1 4 5)
(2 1)+(4 3) больше подмассивов чем всего 1

1 4 2 3

Из 1 есть (1)
Из 2 нет
Из 3 есть (4 2 3)
Из 4 есть (1 4 2 3)

(1)+(4 2 3) лучше чем (1 4 2 3)

1 3 2 4
Из 1 есть (1) и (4)
Из 2 есть (3 2)
Из 3 есть (1 3 2) и (3 2 4)
Из 4 есть (1 3 2 4)

Собираем, варианты
(1)+(3 2)+(4)
(1)+(3 2 4)
(1 3 2)+(3 2 4) не складываются как и (3 2)+(1 3 2) или как (3 2)+(3 2 4)

так понятно?

(17) *и еще есть готовый (2 1 4 3)

(0) Кстати

Откуда такую задачку взял интересную? В яндекс устраиваешься на работу?

Тут главная загвоздка как кодировать подмассив чтобы сохранять варианты.

Можно двумя числами (ДлинаПодмассива, НачалоПодмассива).
Но можно это в одно число засунуть, зная что ДлинаПодмассива<=ДлиныМассива и НачалоПодмассива<ДлиныМассива

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

Или для хранения можно использовать списки (ТЗ в 1С), что проще

"Красивая дочка, умница." И зачем папаша ее мучает?

Классная задачка. Кажется, знаю решение. Если вечером доберусь до компа, напишу

(26) Да решение в лоб не сложное и выше привел.
Но вот придумать оптимальное решение когда в массиве тысячи элементов (или более) это уже сложнее, надо заранее неправильные варианты отсекать.

Кста чтобы правильно решить (как задумал автор задачки) надо знать какую тему(ы) проходили перед этим.
Может там теория графов была с методом ветвей и границ.
Или банальная рекурсия.

(27) твоё не смотрел). Мое работает на любых объемах, в один проход (O(N)) при наличии отсортированной копии массива

(28) Лучше скажи как это запросом сделать...

(29) можно и запросом

(30) Угу рекурсивным

(31) я таких не знаю))

Ну что, идею(простую) или запрос (возможно будет непонятно :))?

Запросом как, кодом то все понятно

Любой запрос можно перевести в код (это доказывает то что движки написаны кодом).

Вот обратное не всегда. Ибо язык запросов не полный по Тьюрингу.

(35) "Любой запрос можно перевести в код" - для этого надо будет понять))
(34) ОК 15 минут

(36) Уже 10 минут прошло, осталось 5 минут ))

(37) Ок причесывать не буду

Количество записей в результате - ответ (сортировка только в одну сторону)
ВЫБРАТЬ
    1 КАК Номер,
    44 КАК Значение
ПОМЕСТИТЬ ВТ

ОБЪЕДИНИТЬ

ВЫБРАТЬ
    2,
    202
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    ВТ.Номер КАК Номер,
    СУММА(ВТ1.Значение) КАК НИ
ПОМЕСТИТЬ ВТ_НИ
ИЗ
    ВТ КАК ВТ
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК ВТ1
        ПО ВТ.Номер >= ВТ1.Номер

СГРУППИРОВАТЬ ПО
    ВТ.Номер
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    ВТ.Номер КАК НомерИсх,
    СУММА(ВТ1.Значение) КАК НИ,
    КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ВТ1.Номер) КАК Номер
ПОМЕСТИТЬ ВТ_Сорт_НИ
ИЗ
    ВТ КАК ВТ
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК ВТ1
        ПО (ВТ.Значение > ВТ1.Значение
                ИЛИ ВТ.Значение = ВТ1.Значение
                    И ВТ.Номер >= ВТ1.Номер)

СГРУППИРОВАТЬ ПО
    ВТ.Номер
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    *
ИЗ
    ВТ_НИ КАК ВТ_НИ
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ_Сорт_НИ КАК ВТ_Сорт_НИ
        ПО ВТ_НИ.Номер = ВТ_Сорт_НИ.Номер
            И ВТ_НИ.НИ = ВТ_Сорт_НИ.НИ

(37) Сколько времени тебе понадобится чтобы угадать идею))?

Нутром чую что кол-во подмассивов зависит от дельности смещения всех элементов не на своем месте.

Но вот доказать не могу.

*дальности

Засунул в исходную ВТ курс ЦБ бакса с начала 2018
ВЫБРАТЬ
    РАЗНОСТЬДАТ(&Дата, КурсыВалют.Период, ДЕНЬ) Номер,
    КурсыВалют.Курс Значение
ПОМЕСТИТЬ ВТ
ИЗ
    РегистрСведений.КурсыВалют КАК КурсыВалют
ГДЕ
    КурсыВалют.Валюта = &Валюта
    И КурсыВалют.Период > &Дата

Получил 4 отрезка. 433 значения - работает мгновенно

(41) Запрос(39) в код то переведёшь? Идею там углядеть можно

(44) Оно от "в один проход (O(N))" сильно далеко

(45) Это не про запрос было

*(43) может мы новый вид техананиза изобрели)))
01.01.2018-09.04.2018    55,6717-58,1718
10.04.2018               58,5714
11.04.2018-09.08.2018    60,8583-64,0683
10.08.2018-09.03.2019    65,2221-69,9744

Реально переломы какие-то нашлись

(44) На не числовых данных работать не будет же?

(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).