Доброго времени суток всем читающим!

На одном собеседовании, проходившем в популярном ныне формате опускания соискателя энергичного интервью предложили написать "какую-нибудь сортировку", ну и я, чтобы меньше думать, накарябал простейший "пузырек" (все равно ничего другого я толком и не помню ):

template < class FwdIter >
void bubble_sort(FwdIter start, FwdIter end)
{
  for (bool was_swaped = (start != end); was_swaped; )
  {
    FwdIter i, j, last_swap;
    was_swaped = false;
    for (i = j = start, ++j; j != end; ++j, ++i)
    {
      if (*i > *j)
      {
        was_swaped = true;
        last_swap = j;
        iter_swap(i, j);
      }
    }
    end = last_swap;
  }
}

Интервьюер на этот овнокод страшно возбудился, заявил "сразу видно, что вам еще многому нужно учиться" (с чем я и не собираюсь спорить, ибо согласен на 100.1%), "вы нам явно не подходите" ну ит.д. На вопрос, что, собственно не так, был дан ответ типа "извините, но я не могу тратить свое время на дискуссии с вами". С одной стороны, у каждого свои тараканы в голове, с другой стороны — может там и в самом деле чего-то такое страшно нехорошее. Подскажите, плиз, кому какая критика в голову приходит, только сильно не пинайте.

Заранее спасибо.

Здравствуйте, slava_phirsov, Вы писали:

_>"извините, но я не могу тратить свое время на дискуссии с вами".

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

_> end = last_swap;

а это отсортирует вообще?

Здравствуйте, slava_phirsov, Вы писали:

То ли я не силен в шаблонах, то ли у нас взаимная нелюбовь, но ваш код за 5 минут усиленного вникания я понять не смог. Особенно циклы. Думаю, излишняя сложность — это и есть "страшно нехорошее". Никто ж ведь не ожидает на собеседовании работающего кода — ожидают понятный код.
Простейший пузырек для собеседования вполне может быть примерно таким:

for (int i = 0; i < count; i++)
  for (int j = 0; j < count - i; j++)
    if (array[i] < array[j])
    {
      T t = array[i];
      array[i] = array[j];
      array[j] = t;
    }

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

Здравствуйте, dilmah, Вы писали:

_>> end = last_swap;

D>а это отсортирует вообще?

Типа да...

Здравствуйте, slava_phirsov, Вы писали:

_>Доброго времени суток всем читающим!

_>На одном собеседовании, проходившем в популярном ныне формате опускания соискателя энергичного интервью предложили написать "какую-нибудь сортировку", ну и я, чтобы меньше думать, накарябал простейший "пузырек" (все равно ничего другого я толком и не помню ):

_>

_>template < class FwdIter >
_>void bubble_sort(FwdIter start, FwdIter end)
_>{
_>  for (bool was_swaped = (start != end); was_swaped; )
_>  {
_>    FwdIter i, j, last_swap;
_>    was_swaped = false;
_>    for (i = j = start, ++j; j != end; ++j, ++i)
_>    {
_>      if (*i > *j)
_>      {
_>        was_swaped = true;
_>        last_swap = j;
_>        iter_swap(i, j);
_>      }
_>    }
_>    end = last_swap;
_>  }
_>}
_>

_>Интервьюер на этот овнокод страшно возбудился, заявил "сразу видно, что вам еще многому нужно учиться" (с чем я и не собираюсь спорить, ибо согласен на 100.1%), "вы нам явно не подходите" ну ит.д. На вопрос, что, собственно не так, был дан ответ типа "извините, но я не могу тратить свое время на дискуссии с вами". С одной стороны, у каждого свои тараканы в голове, с другой стороны — может там и в самом деле чего-то такое страшно нехорошее. Подскажите, плиз, кому какая критика в голову приходит, только сильно не пинайте.

_>Заранее спасибо.

Проблема в чрезмерном усложнении простых вещей. Вспоминается мудрость одного старого программиста. "Только действительно опытные программисты позволяют себе писать просто." Они уже все давно все доказали, и не стремятся поразить кого нибудь замудренным кодом, который только они и способны читать. Это не камень в Ваш огород. Т.к. я сам еще люблю "поражать" коллег высотой полета своей мысли. Ну а интервьюер лох. Ведь теперь им пойдет антиреклама.

они не доросли до твоих стихов(с)

Здравствуйте, slava_phirsov, Вы писали:


_>На одном собеседовании, проходившем в популярном ныне формате опускания соискателя энергичного интервью предложили написать "какую-нибудь сортировку", ну и я, чтобы меньше думать, накарябал простейший "пузырек" (все равно ничего другого я толком и не помню ):

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

Здравствуйте, slava_phirsov, Вы писали:

_>На одном собеседовании, проходившем в популярном ныне формате опускания соискателя энергичного интервью предложили написать "какую-нибудь сортировку", ну и я, чтобы меньше думать, накарябал простейший "пузырек" (все равно ничего другого я толком и не помню ):

Можно было ещё shuffle_sort

template<class RandIt, class Pred>
void shuffle_sort(RandIt begin, RandIt end, Pred pred)
{
  while(true)
  {
    if(adjacent_find(begin,end,bind(not_,bind(pred,_1,_2))==end) // без бинда это цикл проверки
      return;
    random_shuffle(begin,end);
  }
}

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, slava_phirsov, Вы писали:

_>>На одном собеседовании, проходившем в популярном ныне формате опускания соискателя энергичного интервью предложили написать "какую-нибудь сортировку", ну и я, чтобы меньше думать, накарябал простейший "пузырек" (все равно ничего другого я толком и не помню ):

К>Можно было ещё shuffle_sort
К>

К>template<class RandIt, class Pred>
К>void shuffle_sort(RandIt begin, RandIt end, Pred pred)
К>{
К>  while(true)
К>  {
К>    if(adjacent_find(begin,end,bind(not_,bind(pred,_1,_2))==end) // без бинда это цикл проверки
К>      return;
К>    random_shuffle(begin,end);
К>  }
К>}
К>

Про shuffle сортировку я слышал. Но с реализациями как-то не сталкивался. Интересная задача — оценить ее сложность. Я тут прикинул в уме... O(n! * n).

A>оценить ее сложность. Я тут прикинул в уме... O(n! * n).

обычно считают worst case complexity, а не "в среднем". С "worst case" тут плохо, особенно если случайные числа не настоящие, а псевдо, то легко может оказаться что правильная перестановка просто никогда не будет сгенерирована.

Здравствуйте, Acteon, Вы писали:


A>Про shuffle сортировку я слышал. Но с реализациями как-то не сталкивался. Интересная задача — оценить ее сложность. Я тут прикинул в уме... O(n! * n).

ошибаетесь, просто O(n^2), такаяже как и для пузырьковой(random_shuffle в общем случае ~n, вероятность того что даная итерация попадёт ~ 1/n => колл. необходимых итераций в среднем ~n).

Здравствуйте, dilmah, Вы писали:


A>>оценить ее сложность. Я тут прикинул в уме... O(n! * n).

D>обычно считают worst case complexity, а не "в среднем". С "worst case" тут плохо, особенно если случайные числа не настоящие, а псевдо, то легко может оказаться что правильная перестановка просто никогда не будет сгенерирована.

Да, тут уж как повезет.

Поэтому всегда перед решением задачи следует уточнить ограничения по времени, памяти, типу данных. Ведь есть еще замечательная сортировка которая работает за O(n), но с очень сильными ограничениями (мы ее называли черпаком). Например, если в массиве могут быть только 1, 2 или 3. То считаем сколько всего единиц, двоек и троек. И потом столько и пишем в новый массив.

S>ошибаетесь, просто O(n^2), такаяже как и для пузырьковой(random_shuffle в общем случае ~n, вероятность того что даная итерация попадёт ~ 1/n => колл. необходимых итераций в среднем ~n).

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

Здравствуйте, dilmah, Вы писали:


A>>оценить ее сложность. Я тут прикинул в уме... O(n! * n).

D>обычно считают worst case complexity, а не "в среднем".

тогда бы для быстрой сортировки считали бы n^2, а не n * ln(n).

Здравствуйте, Acteon, Вы писали:

A>Ведь есть еще замечательная сортировка которая работает за O(n), но с очень сильными ограничениями (мы ее называли черпаком). Например, если в массиве могут быть только 1, 2 или 3. То считаем сколько всего единиц, двоек и троек. И потом столько и пишем в новый массив.

Насколько я помню, наукообразное название — "сортировка счётом"

Здравствуйте, dilmah, Вы писали:

D>в таком случае, вышеприведенный код имеет мало общего с тем, что ты подразумеваешь под shuffle sort.

я не знаю что такое shuffle sort, поэтому просвятите- что я под ним подразумеваю.

Здравствуйте, Sni4ok, Вы писали:

S>Здравствуйте, Acteon, Вы писали:


A>>Про shuffle сортировку я слышал. Но с реализациями как-то не сталкивался. Интересная задача — оценить ее сложность. Я тут прикинул в уме... O(n! * n).

S>ошибаетесь, просто O(n^2), такаяже как и для пузырьковой(random_shuffle в общем случае ~n, вероятность того что даная итерация попадёт ~ 1/n => колл. необходимых итераций в среднем ~n).

Не совсем понял Ваших рассуждений. Но вот чем я руководствовался. Массив из n различных элементов. Количество перестановок n!. Только одна перестановка правильна (т.к. все элементы различны). => Нужно совершить n!/2 итераций, что бы ее "угадать". Одна итерация требует 2 * n операций (вот тут не уверен, нужно смотреть сложность алгоритмов поиска и рандомизации коллекции). Если все перемножить, то и получится заветное O(n! * n).

Здравствуйте, slava_phirsov, Вы писали:

_>Здравствуйте, Acteon, Вы писали:

A>>Ведь есть еще замечательная сортировка которая работает за O(n), но с очень сильными ограничениями (мы ее называли черпаком). Например, если в массиве могут быть только 1, 2 или 3. То считаем сколько всего единиц, двоек и троек. И потом столько и пишем в новый массив.

_>Насколько я помню, наукообразное название — "сортировка счётом"

Спасибо за название. Теперь хоть буду знать. А то все черпак, да черпак.

Здравствуйте, Acteon, Вы писали:

A>Массив из n различных элементов. Количество перестановок n!.

вы правы, тут я ошибся.