Сортировка массива из единиц и двоек

от ·9 комментариев

Эта задачка применялась, как минимум, на собеседованиях в Sun Microsystems. Задачка миленькая, несложная, на сообразительность.

Задача

Отсортировать массив, состоящий только из единиц и двоек.

Решения

Решений, как у большинства задачек много. Приведем некоторые.

  1. Сложить все  элементы массива и вычесть из суммы длину массива. Результатом будет количество двоек в массиве. Далее массив заливается нужным количеством последовательных двоек и единиц.
  2. Посчитать количество единиц и двоек, пройдя по массиву. Далее опять заливаем массив нужным количеством двоек и единиц.
  3. Запускаем в цикле два счетчика, сближающихся с противоположных концов массива. Меняем местами соответствующие значения, по необходимости.

В третьем варианте что-то вроде:

public void sort12(int []array) {
    int i = 0;
    int j = array.length-1;
    for (; i<j; i++) {
        // Сортируем по возрастанию
        if (array[i] == 2) {
            for (; array[j] == 2; j--);
            array[i] = 1;
            array[j] = 2;
            j--;
        }
    }
}

Первый вариант представляется самым оптимальным, с точки зрения производительности: сравнений нет, все действия с массивом последовательные. В нём как раз проявляется сообразительность 🙂

Второй вариант похуже, но тоже ничего.

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

  • При этом предлагается считать, что кандидат, пишущий какую-нибудь классическую сравнивающую сортировку, получает EPIC FAIL.

    P.S. В коде есть опечатки: в сигнатуре метода должно быть int[]. Да и int i = 0; можно внести в for.

  • cap

    Да, epic fail однозначный.

    P.S. Сигнатуру метода поправил, спасибо. Про i думал, решил оставить в одном месте с j, т.к. на скорость не влияет.

  • omi891

    Первый да, но немного измененный — в процессе складывания заливаем массив 1. потом доливаем необходимое кол-во двоек.(или наоборот)

    😉

  • cap

    А как мы узнаем количество единиц, на котором надо остановиться? Или заливаем ими весь массив?

  • omi891

    да весь — потом доливаем двойки 😉

    однако можно заливать и двойками вначале а единицами потом — хотя это абсолютно идентично по количеству операций (у меня как раз кто-то из знакомых считал число элементарных операций и там и там — и что странно получилось одинаково ;-))

  • cap

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

  • Вы что, хотите сказать, что залить _весь_ массив единичками, а потом залить хвост двойками настолько же быстро, что и залить голову единичками, а хвост двойками?

    В первом варианте на каждую ячейку, содержащую в итоге «2», будут производиться две записи! Как бы Вы не старались. Расчёт «элементарных» операций разбивается таким вот простым рассуждением — как удалось уравнять их количество?

  • Ага, давайте скажем, что в массиве лежат int'ы =) Тогда memset'ом не обойдёшься.

  • cap

    +1