Re[5]: Зацените bubble_sort (только сильно не ругайтесь) - C/C++

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

_>Нет, не у меня. Тем не менее, это быдлокод. Во-первых, писать пузырёк это быдлокодерство. Во-вторых, даже пузырёк можно записать более элегантно, например как-то так:

_>template< typename Iterator >
_>void bubble_sort( Iterator First, Iterator Last )
_>{
_>    while( First < --Last )
_>        for( Iterator i = First; i < Last; ++i )
_>            if ( *(i + 1) < *i )
_>                std::iter_swap( i, i + 1 );
_>}

Ваш "элегантный" код упадет на пустой последовательности. Кстати, в отличие от кода OP. Это к вопросу о быдлокодерстве.

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

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

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

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

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

Ytz>Судя по минусу от некоего skeptik_, были именно у него

Нет, не у меня. Тем не менее, это быдлокод. Во-первых, писать пузырёк это быдлокодерство. Во-вторых, даже пузырёк можно записать более элегантно, например как-то так:

template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

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

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

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

Здравствуйте, 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, Вы писали:

То ли я не силен в шаблонах, то ли у нас взаимная нелюбовь, но ваш код за 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;
    }

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

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

_>Нет, не у меня. Тем не менее, это быдлокод. Во-первых, писать пузырёк это быдлокодерство. Во-вторых, даже пузырёк можно записать более элегантно, например как-то так:

Речь идет о культуре общения. Я правильно понял, что хамить малознакомым людям для тебя нормальное явление?

Здравствуйте, 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, Вы писали:

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

):

Можно было ещё 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);
  }
}

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

LVV>Здравствуйте, slava_phirsov, Вы писали:
LVV>Надо было так:
_>>

_>>template < class FwdIter >
_>>void bubble_sort(FwdIter start, FwdIter end)
_>>{ std::sort(start, end);
_>>}
_>>

LVV>И вопросы бы отпали...

Не, вопрос остается. WTF?

Пузырек на форвард итераторах, реализованный через вызов стандартной сортировки на random access итераторах.

Здравствуйте, 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;
_>  }
_>}
_>

Ваш код сложно читать и понимать

for (bool was_swaped = (start != end); was_swaped; )

зачем здесь for в while-стиле? у читающего в голове есть семантика for, ему придется затратить больше мыслей при чтении

for (i = j = start, ++j; j != end; ++j, ++i)

Зачем двойной for если можно два for'а

Вы можете сказать, что это исключительно дело вкуса, но сложность чтения должна что-то принципиально привносить в программу, а не просто сокращать число строчек кода.
Если в такую простую вещь, как сортировка пузырьком, реализовали так сложно, то что будет в более замороченных случаях?

Если по самому алгоритму, то зачем начинать всегда со start?

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

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

_>> end = last_swap;

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

Типа да...

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

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

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

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

Код не читабелен,

.
ИМХО тот кто энто будет после тебя разруливать повешается.
Думаю интервьювер правельно поступил

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

Л>Слово "какой-нибудь" нельзя понимать буквально. Например, если клиент приходит в парикмахерскую и говорит: "Подстрегите как-нибудь на ваш вкус", то это не значит, что можно взять машинку и под ноль его обрить.

- Скажите, а куда мне идти?
— Это зависит от того, куда ты хочешь попасть.
— Но мне все равно, куда попасть!
— Тогда тебе все равно, куда идти.

Л>А что касается приведённого кода, то он весьма избыточен и запутан. Из особых перлов "for (i = j = start, ++j; j != end; ++j, ++i)". Тут достаточно одного итератора. j всегда равно i + 1.

~~Типа~~ оптимизация, в духе кода из незабвенной статьи "банды трех"(TM) "Fast patttern matching on strings". i+1 должно вычисляться четырежды, потому использована новая переменная. Ну и чтобы было что обсуждать при разборе кода.

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

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

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

Здравствуйте, 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).

ну как по мне так практически все нормально с этим кодом (ну да вот как уже отметили компаратор тоже былоп недурно передать шаблонным параметром)...

ну не все интервьюеры шарят в шаблонах (и вообще догоняют идею generic'ового программинга) ... бывает... и чтобы не выглядеть дураком (сначала на интервью, а потом и в процессе работы, то луче послать сразу кандидата))

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

-- все блин руки не доходят сделать LGPLную библеотечку из него...

могу догадаться что от вас может быть хотели не простого кода а очень простого (или даже тупого)

-- типа

void bubble_sort(int* array, int size)

-- но писать какашки это веть не правильный выбор!!?

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

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

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

M_>Ну, начало обоих циклов от 0 уже означает что-то не то.
с чего бы это?
так тоже не то?

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

_> end = last_swap;

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

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

К>Здравствуйте, 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).

Здравствуйте, 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).

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

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

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

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

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

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

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

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

А то все черпак, да черпак.

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

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

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

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

A>Поэтому всегда перед решением задачи следует уточнить ограничения по времени, памяти, типу данных.

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

Классно. Только вот зачем нужен новый массив?
Временная структура на выходе черпака более информативна?

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

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

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

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

Судя по минусу от некоего skeptik_, были именно у него

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

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

A>>Поэтому всегда перед решением задачи следует уточнить ограничения по времени, памяти, типу данных.

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

HA>Классно. Только вот зачем нужен новый массив?
HA>Временная структура на выходе черпака более информативна?

Все зависит от алгоритмов, которые потом будут применяться. Если их можно адаптировать к такой структуре, то не проблема. Но они могут быть уже написаны. Хотя... если для этой структуры реализовать итератор... В общем все как всегда: время, качество, стоимость.

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

Z>ну как по мне так практически все нормально с этим кодом (ну да вот как уже отметили компаратор тоже былоп недурно передать шаблонным параметром)...

Z>ну не все интервьюеры шарят в шаблонах (и вообще догоняют идею generic'ового программинга) ... бывает... и чтобы не выглядеть дураком (сначала на интервью, а потом и в процессе работы, то луче послать сразу кандидата))

Z>на сам деле я был бы рад встретить такого кандидата (все еще ищешь работу?)... ибо сам сначала всегда пытаюсь решить задачу обобщенным кодом (так чтоб это можно было использовать более чем в одном месте или даже проекте). у меня в голове крутится пример моего знакомого, любителя вырезать из дерева, который в своем увлечении дошел до того, что делает инструменты себе сам, и потом их использует... мое такое ИМХО что у опытного программиста кроме знаний в голове должен быть багаж в виде кода (высокой степени реюзабельности) наработанного за время участия в разных проектах... ну не переизобретать веть велосипеды каждый раз? у меня лично скопилось куча такого кода, который был многократно перезаюзан в куче проектов (внедрен в уже идущий проект либо ставший первым что появилось в системе контроля версий нового проекта)... так вот и кочюет он из проекта в проект

-- все блин руки не доходят сделать LGPLную библеотечку из него...

Z>могу догадаться что от вас может быть хотели не простого кода а очень простого (или даже тупого)

-- типа

void bubble_sort(int* array, int size)

-- но писать какашки это веть не правильный выбор!!?

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

Z>мое такое мнение что вам повезло не работать в этой конторе (ибо скорее всего там авгиевы конюшни копаться в которых врядли комуто будет интересным) и кроме того высока вероятность что вы там были бы не поняты... такая работа кроме нервяков (и денег?) ничего не принесет... оч трудно работать в коллективе где тебя не понимают (и даже противостоят тебе)

Да проблема не в шаблонах. Проблема в том, что dilmah спросил. "А это отсортирует вообще?" Да у меня самого, точно такой же вопрос в голове. Понятно, чем опытнее программист, тем быстрее он убедиться в его работоспособности. Но это не будет мгновенно. И вот вы тратите 3 минуты, на простую сортировку пузырьком. А ведь проект состоит не из одной сортировки.

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

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

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

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

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

):

skipped

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

может там и в самом деле чего-то такое страшно нехорошее. Подскажите, плиз, кому какая критика в голову приходит, только сильно не пинайте.

Ну, реакция интервьюера слишком странная вообще, какой бы там код ни был. Не понравилось ему, возможно, то, что по этому коду слишком тяжело понять, правильно он работает или нет. Я бы уточнил требования к сортировке, если бы мне предложили ее написать. Ну и даже если писать какой-то обобщенный код, да еще и с forward iterators, то можно было бы написать что-нибудь такое:

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

Я знаю, что это не эквивалентно коду выше, и сравнений будет больше, но оптимизировать пузырек тоже дело не сильно благородное.

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

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

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

_>>Нет, не у меня. Тем не менее, это быдлокод. Во-первых, писать пузырёк это быдлокодерство. Во-вторых, даже пузырёк можно записать более элегантно, например как-то так:

Ytz>Речь идет о культуре общения. Я правильно понял, что хамить малознакомым людям для тебя нормальное явление?

skeptik_, минус поставил — молодец. Теперь на вопрос ответь, если сможешь то с аргументацией своей позиции.

Здравствуйте, slava_phirsov, Вы писали:
Надо было так:
_>

_>template < class FwdIter >
_>void bubble_sort(FwdIter start, FwdIter end)
_>{ std::sort(start, end);
_>}
_>

И вопросы бы отпали...

Здравствуйте, skeptik_, Вы писали:
_>Во-вторых, даже пузырёк можно записать более элегантно, например как-то так:
_>

_>template< typename Iterator >
_>void bubble_sort( Iterator First, Iterator Last )
_>{
_>    while( First < --Last )
_>        for( Iterator i = First; i < Last; ++i )
_>            if ( *(i + 1) < *i )
_>                std::iter_swap( i, i + 1 );
_>}
_>

Твой быдлокод:
— Падает (уже отметили).
— Если массив где-то на полпути окажется отсортирован — все равно по нему елозит.
В отличии от.

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

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

LVV>>Здравствуйте, slava_phirsov, Вы писали:
LVV>>Надо было так:
_>>>

_>>>template < class FwdIter >
_>>>void bubble_sort(FwdIter start, FwdIter end)
_>>>{ std::sort(start, end);
_>>>}
_>>>

LVV>>И вопросы бы отпали...

_DA>Не, вопрос остается. WTF?

Пузырек на форвард итераторах, реализованный через вызов стандартной сортировки на random access итераторах.
Ну, можно было имя параметра шаблона и переименовать, чтобы вопросов не возникало...

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

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

A>Да проблема не в шаблонах. Проблема в том, что dilmah спросил. "А это отсортирует вообще?" Да у меня самого, точно такой же вопрос в голове. Понятно, чем опытнее программист, тем быстрее он убедиться в его работоспособности. Но это не будет мгновенно. И вот вы тратите 3 минуты, на простую сортировку пузырьком. А ведь проект состоит не из одной сортировки.

Отсортирует. То что показалось странным dilmah сделано для того, чтобы не сортировать конец массива, если в конце скопилась отсортированная последовательность.

Вопрос "А работает ли это вообще" сам по себе может являться вполне законным. Но только применительно быдлокоду ужасающего качества, чего в сообщение автора топика я совсем не вижу. Там нет, ни грязных хаков, ни каких либо нетривиальных вещей, которые нужно специально доказывать. И вообще, если у людей возникают вопросы по поводу работоспособности и сложности восприятия этого кода, то чтобы они сказали по поводу быстрой, например, сортировки?
Если что, то так реализовывать сортировку пузырьком учат в школе/институте.

Кстати, если посмотреть код известных программистов и компьютер саентистов (кнута, линуса торвальдса ну или кого вы там уважаете) он окажется тем ещё говном.

Так что я не думаю, что субъективная оценка качества кода может служить оценкой соискателя в целом. Может быть проводившему собеседование ещё что нибудь не понравилось. Иначе он полный неадекват. Впрочем, _skeptik ведет себя тоже довольно странно, расставляя всем минусы в этом топике. Ну напиши хоть что нибудь по делу!
Интересно было бы услышать от автора подробности собеседования и название организации.

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

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

Странный подход. Видимо менеджеры совершенно не в курсе (судят по себе) такой свойстве человека — способности обучаться. Я с трудом представляю такую ситуацию, чтобы устроившийся на работу программист сразу мог разобраться в проекте так, как будто он его всю жизнь писал.

A>Отсортирует. То что показалось странным dilmah сделано для того, чтобы не сортировать конец массива, если в конце скопилась отсортированная последовательность.

просто у меня после первого прочтения сложилось ощущение, что отсортированная последовательность скапливается в начале.

A>ни каких либо нетривиальных вещей

то, что forward итераторы можно использовать в многопроходных алгоритмах это все С++ программисты знают? что-то не верится.

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

H>

H>for (i = j = start, ++j; j != end; ++j, ++i)
H>

H>Зачем двойной for если можно два for'а

В этом случае рост индексов при каждой итерации происходит на одну и ту же величину. Это скорее аналогично:

    for (j = start + 1; j != end; ++j)
    ...
        if( *(j-1) < *j)
            ...

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

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

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

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

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

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

Только вот этот код ничего не сортирует ) Да и пока что с виду он похож скорее на неправильный selection sort, чем на неправильный bubble sort.

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

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

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

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

A>>Да проблема не в шаблонах. Проблема в том, что dilmah спросил. "А это отсортирует вообще?" Да у меня самого, точно такой же вопрос в голове. Понятно, чем опытнее программист, тем быстрее он убедиться в его работоспособности. Но это не будет мгновенно. И вот вы тратите 3 минуты, на простую сортировку пузырьком. А ведь проект состоит не из одной сортировки.

A>Отсортирует. То что показалось странным dilmah сделано для того, чтобы не сортировать конец массива, если в конце скопилась отсортированная последовательность.

A>Вопрос "А работает ли это вообще" сам по себе может являться вполне законным. Но только применительно быдлокоду ужасающего качества, чего в сообщение автора топика я совсем не вижу. Там нет, ни грязных хаков, ни каких либо нетривиальных вещей, которые нужно специально доказывать. И вообще, если у людей возникают вопросы по поводу работоспособности и сложности восприятия этого кода, то чтобы они сказали по поводу быстрой, например, сортировки?
A>Если что, то так реализовывать сортировку пузырьком учат в школе/институте.

Попробую объяснить свою мысль на примере STL. Мы используем STL как библиотеку. Она хорошо спроектирована, и реализована без ошибок (допустим). Я использую из нее сортировку, и могу даже не заглядывать внутрь. А теперь представим, что ее написал наш коллега. В проекте где-то ошибка, и нужно ее найти. Будем отлаживать STL (т.к. ее уже писал наш коллега, то и там могут быть ошибки). И придется тратить много времени, на ее понимание (ну взяли студента практиканта, который с трудом в шаблоны въезжает, зато он дешевый). Что хорошо для библиотеки, может быть плохо для проекта. И это никак не касается качества кода (до тех пока там нет хаков, обходов архитектуры и прочего). Просто одни подходы хороши здесь, другие там.

A>Кстати, если посмотреть код известных программистов и компьютер саентистов (кнута, линуса торвальдса ну или кого вы там уважаете) он окажется тем ещё говном.

A>Так что я не думаю, что субъективная оценка качества кода может служить оценкой соискателя в целом. Может быть проводившему собеседование ещё что нибудь не понравилось. Иначе он полный неадекват. Впрочем, _skeptik ведет себя тоже довольно странно, расставляя всем минусы в этом топике. Ну напиши хоть что нибудь по делу!
A>Интересно было бы услышать от автора подробности собеседования и название организации.

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

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

A>Странный подход. Видимо менеджеры совершенно не в курсе (судят по себе) такой свойстве человека — способности обучаться. Я с трудом представляю такую ситуацию, чтобы устроившийся на работу программист сразу мог разобраться в проекте так, как будто он его всю жизнь писал.

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

Сталкивался с конторами, в которых проекты пишутся студентами на испытательных сроках. Потом они увольняются, и набираются новые. Очень дешево выходит. Может это была одна из таких контор.

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

K_O>>Простейший пузырек для собеседования вполне может быть примерно таким:
K_O>>

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

_DA>Только вот этот код ничего не сортирует )

Откуда такой вывод?

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

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

K_O>>>Простейший пузырек для собеседования вполне может быть примерно таким:
K_O>>>

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

_DA>>Только вот этот код ничего не сортирует )

K_O>Откуда такой вывод?

Хм, ну если на код посмотреть, то это вроде бы очевидно. Но если нужны доказательства, то вот http://codepad.org/mB3a5ULK.

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

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

K_O>>>Простейший пузырек для собеседования вполне может быть примерно таким:
K_O>>>

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

_DA>>Только вот этот код ничего не сортирует )

K_O>Откуда такой вывод?
Ну, начало обоих циклов от 0 уже означает что-то не то.
Далее, возьмем первые шаги: i=0, j=1. И если array[i] < array[j] (что нормально для отсортированного массива), то эти элементы меняются местами.

На первый взгляд могу предположить, что:
1) диапазон i должен был быть 0...count-1
2) диапазон j должен был быть i+1...count-1
3) знак в сравнении должен быть "больше", а не "меньше"

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

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

):

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

А что касается приведённого кода, то он весьма избыточен и запутан. Из особых перлов "for (i = j = start, ++j; j != end; ++j, ++i)". Тут достаточно одного итератора. j всегда равно i + 1.

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

Л>>А что касается приведённого кода, то он весьма избыточен и запутан. Из особых перлов "for (i = j = start, ++j; j != end; ++j, ++i)". Тут достаточно одного итератора. j всегда равно i + 1.

_>~~Типа~~ оптимизация, в духе кода из незабвенной статьи "банды трех"(TM) "Fast patttern matching on strings". i+1 должно вычисляться четырежды, потому использована новая переменная. Ну и чтобы было что обсуждать при разборе кода.

Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно. И почему ты решил, что интервьюеру хотелось увидеть оптимизацию именно производительности, а не понятности кода. Но вообще, чтобы оптимизировать на подобном уровне, надо и ассемблер знать и оптимизационные возможности компилятора. Между C кодом и командами процессора нет однозначного обратимого соответствия. *(i + 1) и *i в большинстве случаев выливаются в равнозначные по времени машинные инструкции. А вот наличие ненужных переменных нежелательно, т.к. количество регистров процессора, в которых их можно хранить, ограничено.
Интервьюеры, конечно, не испытывают энтузиазма каждому претенденту всё это рассказывать.

Л>*(i + 1) и *i

в коде топикстартера используются forward iterators. Для них нельзя писать (i+1), только ++i или i++

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

D>в коде топикстартера используются forward iterators. Для них нельзя писать (i+1), только ++i или i++

В таких случаях пишут std::advance(i, 1), а не ++.

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

Л>Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно.

Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук.... Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.

Л>*(i + 1) и *i в большинстве случаев выливаются в равнозначные по времени машинные инструкции.

Хм, для указателей — да, для итераторов — не уверен. Ибо *(i+1) выливается в создание нового объекта-итератора. Хотя

Конечно, хорошо бы на эту тему послушать умных людей, залезавших под капот к STL.

Л>Интервьюеры, конечно, не испытывают энтузиазма каждому претенденту всё это рассказывать.

- Что-то вы мне, милочка, не нравитесь...
— Да и вы, доктор, не Аполлон.

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

_>Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук.... Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.
Тестовые задания в обычных фирмах придумывать некогда и некому. Большинство из них рождается в недрах монстров вроде MS. И соответствует позиции продвинутого разработчика, который сортировку слиянием может просто придумать находу. Но постепенно задание становится достоянием всё более широкой общественности. Его берут на вооружение самые занюханные конторы. И тут уже проверяется, знает ли кандидат о таком задании. Если знает, значит не последний человек в программировании. Всё-таки профильные форумы читает.

Л>>*(i + 1) и *i в большинстве случаев выливаются в равнозначные по времени машинные инструкции.

_>Хм, для указателей — да, для итераторов — не уверен. Ибо *(i+1) выливается в создание нового объекта-итератора. Хотя

Конечно, хорошо бы на эту тему послушать умных людей, залезавших под капот к STL.

Компиляторы сейчас inline код сносят практически подчистую. Но даже если какие-то прециденты и остались, то они на месте не стоят, совершенствуются. Тягаться с компилятором без какой-то весомой причины бессмысленно.

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

Л>Компиляторы сейчас inline код сносят практически подчистую. Но даже если какие-то прециденты и остались, то они на месте не стоят, совершенствуются. Тягаться с компилятором без какой-то весомой причины бессмысленно.

Еще раз: насколько я понимаю, грубо говоря, i + 1 порождает временный объект-итератор (если конечно i — объект, а не указатель), после чего он инкрементируется. На это требуется затратить определенное время, и inline подстановка тут не спасет: она может дать экономию за счет вызова конструктора, но код конструктора все равно должен будет выполниться. Кстати, где-то слышал, что вроде бы конструкторы (или деструкторы?) вообще не встраиваются (могу ошибаться, поправьте, если что). Да, а потом еще надо будет вызвать еще и деструктор временного объекта. Эээх, ~~навыков и желания~~ времени нету поковыряться в дизасме и проверить приведенное ИМХО для разных компиляторов, с разными ключами оптимизации...

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

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

M_>>Ну, начало обоих циклов от 0 уже означает что-то не то.
_>с чего бы это?
_>так тоже не то?
_>

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

тут совсем другое дело. Может быть, алгоритм и рабочий

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

Л>>Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно.

_>Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук....
я писал

сортировка списка строк из 5-10 строк максимум 1 раз в день. Даже не захотелось заморачиваться с поиском способа сортировки имеющего списка. 5 минут и готово.

_>Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.
смотрят на код. Чтобы оценить код лучше всего смотреть на известную задачу. Сортировка неплохо подходит ИМХО.

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

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

Л>>>Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно.

_>>Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук....
M_>я писал

M_>сортировка списка строк из 5-10 строк максимум 1 раз в день. Даже не захотелось заморачиваться с поиском способа сортировки имеющего списка. 5 минут и готово.

_>>Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.
M_>смотрят на код. Чтобы оценить код лучше всего смотреть на известную задачу. Сортировка неплохо подходит ИМХО.

Смотрят на код, это да. Но еще, очень часто ожидают вопросов. А зачем эта сортировка? А что она будет сортировать? А какие есть ограничения? Память, скорость, место на жестком диске. И если ты их задаешь, то сама сортировка уже и не так важна.

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

A>Смотрят на код, это да. Но еще, очень часто ожидают вопросов. А зачем эта сортировка? А что она будет сортировать? А какие есть ограничения? Память, скорость, место на жестком диске. И если ты их задаешь, то сама сортировка уже и не так важна.

Закидать, закидать их вопросами, чтобы они сразу почувствовали мощь настоящегопрофи(TM)

Видимо, интервьюер именно этого и ждал. А соискатель, дурак, кинулся сразу чего-то там писать, какой-то код — да кому этот код нужен? Если оставить шутки за скобками, то пожалуй согласен.

	От:	elcste
	Дата:	19.05.10 11:07
	Оценка:	7 (4) +6

	От:	skeptik_
	Дата:	19.05.10 10:05
	Оценка:	-6

От:	Ytz	https://github.com/mtrempoltsev
Дата:	17.05.10 10:13
Оценка:	2 (2) +3 -1

	От:	Sni4ok
	Дата:	17.05.10 11:47
	Оценка:

	От:	slava_phirsov
	Дата:	17.05.10 09:54
	Оценка:	1 (1) +2 -1

	От:	Kh_Oleg
	Дата:	17.05.10 10:20
	Оценка:	1 (1) +2

От:	dabeat_bf	http://alexmogurenko.com
Дата:	21.05.10 06:47
Оценка:	+1