четверг, 3 марта 2011 г.

Сортировка огромного массива

Опять задали вопрос на собеседовании, на который я не сразу дал ответ, а уже вдогонку отправил письмом. Что вы думаете по поводу этого?

Задача: Дан огромный массив чисел, состоящий только из 0, 1 и 2. Описать алгоритм как его отсортировать и оценить сложность алгоритма.

ЗЫ: в каментах ответ, предупреждаю :)

5 комментариев:

  1. Что я смог придумать:
    Первым проходом подсчитываем количество 0, 1 и 2.
    Вторым, сетим массив.
    В нужном порядке, например, с начала 0, потом 1, потом 2. Можно в любом другом порядке.

    ОтветитьУдалить
  2. Уж извините за занудство, но может от вас хотели что-то оттуда http://ru.wikipedia.org/wiki/Алгоритм_сортировки (например, http://ru.wikipedia.org/wiki/Сортировка_подсчетом), и сказать "я отсортирую этот массив за O(n)".

    ОтветитьУдалить
  3. хотя это он и есть (сортировка подсчетом) =)

    ОтветитьУдалить
  4. Это можно сделать одним проходом без дополнительных memory allocations. Не спроста дано только три числа:

    Идея в том, чтобы разделить массив на три блока для чисел 0, 1 и 2. Хранить указатель на конец блока 0 и начало 2. Сделать один проход, где для каждого i-го числа, совать его в соответсвтующий блок, и менять границы блоков по необходимости.

    https://gist.github.com/nodirt/5579453

    ОтветитьУдалить