Блог пользователя AlexSkidanov

Автор AlexSkidanov, 14 лет назад, По-русски

Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)

 

Для остальных -- отличная задача.

Дан массив длины 2N. Первые N элементов и последние N элементов отсортированы по возрастанию. Надо отсортировать весь массив за линейное время с константой памяти.

 

Я предполагаю, что это не классика, потому что существует (неверное) (распространенное) мнение, что лучшая реализация Merge Sort требует O(N) памяти. Сам факт, что описанная выше задача имеет решение, очевидно, опровергает это.

 

UPD: Ваши решения можно проверить на случаях

6 7 8 9 10 1 2 3 4 5

и

1 3 5 7 9 2 4 6 8 10.

Почти любое наивное решение не способно решить один из них.

 

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Более того. Сам факт, что в STL существует (возможно, не всем известная) функция inplace_merge() уж точно опровергает это... :)
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Верно, только в STL inplace_merge() не гарантирует O(N) (по времени). Цитата с cplusplus.com:

    Complexity

    Linear in comparisons (N-1) if an internal buffer was used, NlogN otherwise (where N is the number elements in the range [first,last)).

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    C++ не гарантирует, что не будет заведено O(n) памяти -- более того, STLPort заводит линейную память в inplace_merge.

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

    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Действительно O(NlogN). Сюрпризы STL, просто известный факт что есть несколько алгоритмов слияния за линию (c памятью O(logN), O(1)). Даже stable. Правда, сейчас я не очень помню, и придумывать времени нет (спать пора). Но где-то в Седжвике "Фундаментальные алгоритмы на C/C++/Java" если не была приведена реализация, то отсылка к соответствующим материалам имелась точно. И интуитивно представлялось, что если функция специально помечена как inplace... Настолько же интуитивно, насколько nth_element() должна работать за линию (в среднем, но слава Богу она так и работает).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Пока есть только такое решение. Если числа 32-битные, то массив можно объявить 64-битным. Тогда в старших 32-битах можно хранить собственно сам результат слияния, а в младших исходные данные.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Если бы массив состоял из чисел, задача бы решалась radix sort'ом.

    Разумеется, никаких допущених по поводу природы элементов, помимо того, что на них определен оператор <, делать нельзя.

     

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Алекс, прости меня - дуру грешную. Все-таки дерзнул я и прочитал головоломку :)
Первым пришло в голову вот такое решение... Не знаю, может быть и верное...
Возьмем первый элемент второй половины, его индекс P. Найдем место, куда его надо поставить (индекс T). Обменяем его с элементом, который находится на этой позиции. Теперь в P лежит другое значение, которое раньше стояло в первой половине (элемент с индексом T). Пока значение в этой позиции не превышает следующего элемента второй половины (то есть [P + 1]-го) будем обменивать значения очередного элемента первой половины (T + 1, T + 2 и так далее) и P-ого. В конце мы получим, что элемент с индексом P больше, чем [P + 1]-ый, тогда уже пора менять [P + 1]-ый элемент с последовательными элементами первой половины. Ну и так будет повторяться для каждого P из второй половины. Сложно на словах такое формулировать, мелом на доске и то проще показать :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    После этого массив не будет отсортирован:

    1 3 5 7 9 11

    2 4 6 8 10 12

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

     

    • 14 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится
      Действительно, глупость какую-то написал. В 5 утра первое пришедшее в голову решение даже писать не надо было :) Попытался дать какое-то развитие мышлению в этом направлении, но ничего не получилось. Специально подумаю завтра (точнее уже сегодня) на учебе, а только потом открою тему и посмотрю.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будем записывать результат слева. Понадобятся два указателя: p1 = 1, p2 = n + 1. Если a[p1] <= a[p2], двигаем p1 вправо. Иначе получаем: a[p2] < a[p1]. Пока это выполняется, меняем местами a[p1] и a[p2] и сдвигаем оба указателя вправо.При этом отрезок [1..p1] остается отсортированным (не считая промежуточные стадии второго случая), как и [p2..2n], [p1 + 1..n] и [n + 1..p2 - 1] (это легко доказать). Но так как указатели сдвигаются только вправо, то или p1 настигнет p2, или p2 уйдет за правую границу. В первом случае нас спасет отсортированность 1 и 2 отрезков. Во втором случае при каждом сдвиге p2 будет сдвигаться и p1, тогда p1 будет равен как минимум n + 1, и помогут 1 и 4 отрезки.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    ignore не так понял))
    сейчас буду вникать более подробно
    • 14 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      Как раз-таки в этом случае алгоритм работает
      .3 4 ,1 2
      1 .4 3 ,2
      1 2 3 4
      А вот в случае
      2 4 1 3
      Результат будет печальнее:
      .2 4 ,1 3
      1 .4 2 ,3
      1 3 2 4
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Пусть p1 достиг позиции N, когда p2 был где-то в середине своей половины. Тогда [0,N) отсортирован, [N,p2) отсортирован и [p2,2N) осортирован -- у нас есть три отсортированных массива, как мы их сливаем?

     

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А почему алгоритм остановился? Достижение N первым указателем не заканчивает его работу.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Алгоритм опирается на то, что [0,p1] отсортирован. Я не могу понять, что алгоритм делает пересекая N-ный элемент, чтобы [0,p1) остался отсортирован. Допустим, что p1 указывает на N-1-ый элемент (последний в первой половине), а p2 на некоторый элемент, который больше. Тогда мы сдвигаем p1, и он оказывается на N-ом элементе, который меньше, чем N-1-ый (так как он попал сюда в результате свопа какого-то элемента, который был левее N-1-ого). Значит отсортированность [0,p1] нарушилась.

         

  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    (даблпост)

14 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Утверждение:
Решение этой задачи очень сложное и не практичное (скрытая константа большая).

Доказательство:
Если бы это было не так, то задача была бы классикой и расписана везде где можно (от Кнута до Кормена).

Следствие:
Все решения в этой ветке неправильные, т.к. для описания правильного решения (с доказательством) не хватит лимита символов для комментария :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Решение действительно не практичное.

    Но описать его займет не намного больше, чем любое описанное здесь неправильное решение :о)

     

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    К тому же можно записать решение в pastebin и дать ссылку :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    > Если бы это было не так, то задача была бы классикой и расписана везде где можно (от Кнута до Кормена).

    Ошибочка... Ваше доказательство неверное. См. Кнут, 3-й том, раздел 5.2.4, упражнение №18.


14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Ух... Я придумал какую то жесть:D

Эта жесть работает в предположении, что мы можем сделать циклический сдвиг массива длины n на k единиц за время O(n) и память O(1). Вроде бы мы так можем делать))

Щас еще поразмыслю и запостчу картинки. Без них вообще ничо не будет понятно:D

UPD. Уже не важно. Обломал.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    В C++ в алогритмах операция rotate работает за константу памяти. Во всяком случае на cplusplus.com реализация приведена именно такая.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      О, спасибо)) Не знал, что этот алгоритм есть в stl.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Прочитать первые N в массив. Теперь осталось слиять прочитанный массив с непрочитанным буфером, сразу выводя наименьшее значение
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну... Рациональное зерно в этом решении есть, но задание - отсортировать массив, а не вывести числа в порядке неубывания. При этом, массив уже создан где-то в памяти компьютера, а не вводится из файла.
    При чтении действительно можно было бы считать первую половину. Перевернуть ее. Держать указатель на последний элемент считанной последовательности (самый правый после переворота). Потом читать поочередно оставшиеся числа и выполнять следующее. Будем добавлять в конец элемент, на который указывает наш указатель до тех пор, пока он не больше последнего считанного числа (все время сдвигаем указатель влево, следим, чтобы он не вылез за границы массива), ставим следом считанное число. Читаем новое так далее... В конце получаем массив, отсортированный в обратном порядке, перевернем его и получим отсортированный.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Ну видимо так:
1. В любой момент вначале будет уже отсортированная часть, потом возможно циклически сдвинутый суффикс первого массива, потом суффикс второго массива.
2. Очевидно изначально это выполняется.
3. Научимся за O(a) уменьшать суммарный размер массивов на какое-то a, зависящее от ситуации.
4a) Если первый элемент второго массива меньше, то за 1 обмен задача сводится к на 1 меньшей.
4b) Если первый массив не циклически сдвинутый, то за 0 обменов задача сводится к на 1 меньшей.
4c) Рассмотрим множество элементов первого второго массива, меньших, чем последний элемент в циклическом сдвиге первого. Рекурсивно сольем ту часть первого которая в конце, с тем что мы нашли. Пусть слитый массив имеет размер a. Тогда уже выполненные операции - O(a). Поменять нашу часть в начало можно тоже за O(a). Сделаем цикл. сдвиг если она больше остатка первого массива и a обменов если меньше. Итого свелись к задаче на a меньшей.

Казалось бы это O(n) и доказываться это должно не сложно по индукции.

UPD: На втором примере
(1 3 5 7 9) (2 4 6 8 10)
(1) (3 5 7 9) (2 4 6 8 10)
(1 2) (5 7 9 | 3) (4 6 8 10)
Рекурсивно: (3) -> (3)
(1 2) (5 7 9) (3) (4 6 8 10)
(1 2 3) (7 9 | 5) (4 6 8 10)
(1 2 3 4) (9 | 5 7) (6 8 10)
Рекурсивно: (5 7) (6) -> (5 6 7)
(1 2 3 4) (9) (5 6 7) (8 10)
(1 2 3 4 5 6 7) (9) (8 10)
(1 2 3 4 5 6 7 8) (9) (10)
(1 2 3 4 5 6 7 8 9) (10)
(1 2 3 4 5 6 7 8 9 10)

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    памяти O(1), а тут будет пропорционально глубине рекурсии. или может это глубина не превосходит какой-нибудь константы?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Хм... Про память в стеке не подумал. Ну оценивать глубину рекурсии я не умею, хотя и верю что она маленькая.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    4a) Если первый элемент второго массива меньше, то за 1 обмен задача сводится к на 1 меньшей.

    У тебя может испортится вторая последовательность, например

    (4 5 6) (1 2 3 7 8 9)
    получится
    1 (5 6) (4 2 3 7 8 9)

    Второй массив стал совсем испорченным.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      на сколько я понимаю, в алгоритме первая последовательность хранится с каким-то циклическим сдвигом. т.е. в этом примере на самом деле получится
      1(5 6 | 4)(2 3 7 8 9)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        С цикличискими сдвигами все ломается на чуть большем примере:
        1 3 5 7 9 10 2 4 6 8 11 12
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Может ломается где-то в другом месте, но там где сказал Сережа сломаться ничего не может, так как второй суффикс без сдвига, то просто сдвиг станет большим. Он может стать даже больше чем длина суффикса, но в этом нет ничего плохого. Решение правильное, но оно не O(1) памяти. 
          • 14 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
            Что-то вообще возникла безумная идея инвертировать первую половину массива. Хранить три указателя-индекса:
            1) позиция очередного отсортированного элемента.
            2) позиция на очередной элемент второй половины, он будет сдвигаться всегда вправо.
            3) позиция на очередной элемент первой половинки (которая инвертирована) и этот указатель будет двигаться влево. А когда будет пытаться выйти левее указателя (1). его будем автоматически передвигать на поицию перед указателем (2)
            Ну и процесс обмена будет таков: Очередной минимальный элемент будем обменивать с элементом в позиции (1) (хвост первой половинки). Ну и двигать соответствующий указатель...вроде нигде не ошибся. Возможно для первой половинки еще пригодится хранить количество оставшихся элементов, чтоб было проще с указателями, но все равно памяти O(1)

            Примеры работы алгоритма для последовательности Автора:
            [] (9 7 5 3 1!) (2! 4 6 8 10)
            [1] (7 5 3! 9) (2! 4 6 8 10)
            [1 2] (5 3! 9 7) (4! 6 8 10)
            [1 2 3] (5! 9 7) (4! 6 8 10)
            [1 2 3 4] (9 7 5!) (6! 8 10)
            [1 2 3 4 5] (7! 9) (6! 8 10)
            [1 2 3 4 5 6] (9 7!) (8! 10)
            [1 2 3 4 5 6 7] (9!) (8! 10)
            [1 2 3 4 5 6 7 8] (9!) (10!)
            [1 2 3 4 5 6 7 8 9] (первая последовательность закончилась длина 0) (!10)
            [1 2 3 4 5 6 7 8 9 10]

            для входа: 6 7 8 9 10 1 2 3 4 5 все тоже самое, только вторая последовательность закончится быстрее, а первая тупо будет циклически сдвигаться по массиву.

            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Видимо это не сработает на
              1 2 5 7 9 3 4 6 8 10

              [] (9 7 5 2 1!) (3! 4 6 8 10)
              [1] (7 5 2! 9) (3! 4 6 8 10)
              [1 2] (5! 7 9) (3! 6 8 10)
              ...

              По-моему первая часть стала некорректной.
              • 14 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
                ну да...:(

                ЗЫ: Я правильно понимаю автора, что задача узкозаточненная, правильный алгоритм будет работать тогда и только тогда, когда длина левой половины равна длине правой половины?
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Нет, правильное решение работает в случае, когда половины не равны.

14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Чуть более общая задача (где длины отсортированных кусков неравны) есть в Кнуте: упр. 5.2.4.18.
В ответах есть решение со ссылочками.
Отмечу, что Кнут считает эту задачу довольно трудной (40 из 50).
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    У нас его парнишке задали на интервью в одну компанию. Видимо, они очень не хотели, чтобы он прошел :о)

    А потом уже решение мы с ним нашли как раз в Кнуте.

     

14 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится
В виде кода -- ideone.com/HjOit
Там же можно попробовать подобрать контр-примеры

Кстати обобщается и на случай когда участки разной длинны
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится
    Ваш алгоритм работает за квадрат на тестах такого вида:
    2 4 6 8 ... 2n  1 3 5 7 ... 2n-1