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

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

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

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

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

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

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

void bubble_sort(int* array, int size)

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

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

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

_>

_>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?

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

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

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

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

Здравствуйте, 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. Это к вопросу о быдлокодерстве.

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

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

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

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

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

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

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

Здравствуйте, _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-ам, собственно два вложенных цикла здесь и не нужны, или я вас не правильно понял.

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

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

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