Две лекции создателя STL Александра Степанова в Яндексе

Преобразования и их орбиты

Наибольшая общая мера последние 2500 лет

Посты по теме:

• Александр Степанов, "Elements of programming"

Programming with GUTs

Вчера был на тренинге Kevlin’a Henny под названием «Programming with GUTs». (Кевлин автор нескольких книг, например «Things Every Programming Should Know»)

«GUT» – это сокращение от Good Unit Tests.

Также я узнал выражения «Programming with BUTs» (Brittle Unit Tests) и «Programming with NUTs» (No Unit Tests).

Итак, «...with GUTS» - это хорошо, «...with BUTs» - хуже, «...with NUTs» - безумие.

Вся эта терминология построена на игре слов guts, butt и nuts в английском языке, которые своим двойным смыслом примерно отражают ситуацию в проекте, когда тестирование находится на указанном уровне (Good, Brittle, No).

Дядька очень интересно ведет беседу, нескучно. Вовремя переходит от приколов к важным выводам, что, например, что ошибки – это не зло, а данность (процесс создания программа сложен, и ошибки – это часть процесса), поэтому очень важно уметь использоваться их для своих целей. Глупо исправлять баг, не написав для него unit- или regression- тест, так как без теста информация, которую несет в себе баг-репорт, будет потеряна по исправления ошибки.

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

Например, дежурный вопрос менеджера (не очень умного менеджера) проекта: «А если мы будем практиковать TDD в разработке, это замедлит процесс?». И ваш правильный и политический верный ответ будет решительное «ДА!». «А правда, что написание тестов вместе с кодом призвано затормозить работу разработчика?». «ДА!!!».

В короткой перспективе – да, но в долгосрочной – нет, а совсем наоборот.

Есть хорошая аналогия. Можно ли доехать из места А в место Б на машине, у которой нет традиционных тормозов (а например, только ручник)? Теоретически да. Очень очень медленно, правильно используя торможение двигателем и ручником. Задача будет решена, но очень не быстро, и вероятность облажаться очень высока. А вот если машину оборудовать нормальными тормозами (~unit-тестами), цель которых останавливать машину (и увеличивать время достижения цели), то они также позволят активно разгоняться между торможениями, и как результат – приехать быстрее.

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

Все эти посылы просто TDD очевидны и однозначно разумны, но я был поражен до глубины души, когда кто-то таки спросил из зала, а если я, мол, просто буду писать много комментариев, чтобы всем было понятно, что код делает. И это был не вопрос-прикол. Кто-то спросил это на полном серьезе.

По поводу комментариев была приведена также интересная аналогия. Комментарии в коде – это золото. Но золото обесценивается, когда его становится слишком много. Комментариев много бывает (особенно бесполезных).

На лабах было интересное задание. Программисту дается задание написать класс и unit-тесты для него. Затем эти тесты уже без кода класса даются другому программисту, и его просят воспроизвести функционал класса, основываясь только на тестах к нему. Результаты порой «радуют» даже продвинутых бойцов TDD.

Вывод как всегда простой: тестируйте как можно раньше, тестируйте чаще, тестируйте автоматизировано. Тестирование – это часть работы программиста в первую очередь, а тестера – во вторую.

P.S. Небольшое задание для интересующихся. Допустим, вы написали собственный алгоритм сортировки. Как его тестировать? Каковы будут критерии проверки, что результат такой, какой вы ожидаете?

Смесь двоичной и десятичной арифметики

Многие знают, что происходит при выполнении присваивания "n &= (n - 1);" просто потому, что это весьма распространенный шаблон, и для чего может понадобиться выполнение его в цикле, пока n не станет нулем.

Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.


Update:

Чтобы разобраться в вопросе надо понять, что является корнем недопонимания.

Для людей, не часто имеющих дело с двоичной системой, обычно не совсем очевидна суть трансформации внутреннего двоичного представления числа при выполнении арифметической операции в десятичной нотации. Кажется, что если вычесть единицу, то расположение битов после операции будет иметь мало общего с тем, что было до вычитания. И дальнейшее выполнение "and" вообще не имеет смысла.

С точки зрения битового представления любого числа, есть только два случая:

1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.

2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.

Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.

Использование этого трюка в цикле, пока n не равно нулю, позволяет подсчитать количество ненулевых бит. На каждой итерации мы "выбиваем" ровно один бит, поэтому Число итераций будет равно количеству единиц в n.

Презентация про HTML5

HTML5 презентует сам себя: http://apirocks.com/html5/html5.html

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

У меня под Chrome все работает. Не уверен про IE, но, говорят, что под FireFox тоже все работает.

Можно ли memset'ить float и double?

В финансовой области постоянно приходится иметь дело с ценами, а цены удобно держать как float или double. Также финансовой сфере много старого когда, написанного на С или Фортране.

А в мире языке С практика инициализации структур нулем через memset является весьма распространенной и в целом не самой плохой практикой.

Вопрос: а что, если в структуре есть поля типа double или float. Что будет, если поля этих типов будут тупо забиты нулями, каково будет значение этих полей?

Для начала я проверил у себя на Солярисе и в Visual Studio 9 - все вроде нормально. После memset'а нулем и float и double тоже равны нулю.

Хотя в целом правильный ответ такой: если ваш компилятор гарантирует хранение вещественных чисел в форматe IEEE 754, то вы в безопасности. Если нет (стандарт языка не гарантирует, что должен использоваться именно IEEE 754), то могут быть неожиданности.

Вышла новая версия Google Test 1.5.0

Сегодня вышла новая версия правильной библиотеки для unit-тестирования Google C++ Testing Framework 1.5.0.

Пока обзор будет краткий (фактически, это просто перевод официального анонса):

• assert'ы теперь можно безопасно запускать из разных потоков (работает на платформах, где есть pthreads)
• при использовании предикатов в EXPECT_TRUE() теперь можно самому задавать сообщения их ошибках
• библиотеку теперь можно собрать как DLL (эту возможность многие ждали)
• "упакованная" версия теперь входит состав дистрибутива, и ее не надо создавать самому через скрипт ("упакованная" версия - это просто два файла "gtest.h" и "gtest-all.cc", которые можно добавить в проект и не возиться с двоичной библиотекой)
• система сборки теперь работает через CMake (это фантастически удобно)
• добавлены две новые платформы: Solaris и AIX
• убрана поддержка VC++ 7.1 с отключенными исключениями (если исключения включены, то все еще можно компилировать в VC++ 7.1)

Для тех, кто слышит про Google Test впервые, ниже предыдущие посты о Google Test и о тестировании в целом (многие на русском языке):

• Руководство для начинающих по Google Test и Google Mock (перевод официальной документации для новичков)
• Обзор Goolge Test 1.4.0
• Обзор Google Test 1.3.0
• Введение в Google Mock (видео на английском)
• Презентация от авторов Google Test (на английском)
• Анализатор покрытия кода тестами Bullseye
• Статический анализ кода (Coverity Prevent и Klocwork)
• Unit-тестирования в языке C
• The first little step into Test Driven Development (на английском)
• Автоматизация сборки
• Системы автоматизированной интергации Hudson

Задача про поиск середины связного списка

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

Найти середину связного списка за один проход. Длина заранее не известна, а есть только указатель на голову.

Кто не догадается, смотрите комментарии. Уверен, там задачу быстро "возьмут".

Задача очень жизненная, и реально полезно знать решение.

Как научиться решать задачи подобного рода? алгоритмические программистские задачи? В чем суть обучения?

Есть определенная категория программистов, которым я профессионально завидую. Это бойцы спортивного программирования типа TopCoder'а, Google Code Jam'а и прочих контестов. Для которых что-то вроде поиска цепочек в частично упорядоченном множестве как для меня сложить две переменные. Там, где мне надо открыть книгу или хотя бы Википедию, они это пишут сходу из головы.

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

Но как научиться догадываться? Есть ли какая-то методика обучения? Именно методика, а не "решай все подряд, и все тебе будет". Второй подход, конечно, работает, но методика могла бы ускорить процесс, сделать его более эффективным.

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

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

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

Кстати, сравним среднего выпускника MIT и МАИ (я там учился). Наверное, выпускник MIT потенциально "сильнее" выпускника МАИ (при всей моей любви и уважении к Альма-матер). Почему? Там книги другие? Там профессора хуже? Я не могу пожаловаться, что мой курс программирования, где изучались алгоритмы был недостаточен.

Пока у меня только одно объяснение - скажем так, в объективно престижных ВУЗах просто больше прессуют и фактически заставляют учиться (иначе - это пустая трата денег и большой шанс вылететь).

Выходит, что количество так или иначе переходит в качество. И никакой магии.

Задачи на интервью

Лично я считаю, что задавать на интервью программиста около математические задачки или задачи типа «на сообразительность» – это бесполезно (а значит не нужно). Почему? Моя логика крайне проста. Какова цель интервью? Как можно точнее понять, подходит ли вам человек по нужным критериям. А что именно скажет вам о человеке факт того, что он решил или не решил математическо-логическую задачу? Поможет ли это оценить уровень знаний кандидата в матанализе или теории вероятности, алгебре и даже арифметике? Нет. Ибо подобные задачи нельзя классифицировать по сложности, а значит и по ожидаемому уровню знаний, необходимому для их решения.

Например, задача, часто применяемая (не мной) на интервью.

Из двух городов навстречу друг другу едет велосипедист и летит муха. Скорость мухи в четыре раза быстрее велосипедиста. Когда велосипедист и муха встречаются где-то по середине, муха разворачивается и летит назад, а велосипедист также едет себе дальше. Когда муха возвращается в исходную точку, она разворачивается и снова летит на встречу велосипедисту. Когда они встречаются, все повторяется снова. Муха курсирует подобным образом от своего города до велосипедиста и назад то тех пор, пока велосипедист не приедет в ее город. Вопрос: каково соотношение расстояний, пройденных мухой и велосипедистом?

Задача для средней школы. Хотя лично мне будет без разницы, решит ее человек или нет. Ибо есть гораздо более конкретные вопросы и задачи, чтобы понять, что человек знает, умеет и любит делать. Обычно использование подобных задач призвано потешить самолюбие самого интервьюера типа «ну я то это решил в свое время!», но вот только не уточняется, за какое время.

В плане именно вопросов-задач, куда полезнее попросить написать небольшой код для обхода дерева (например, для поиска медианы в BST), или поиска кратчайшего пути в графе, или придумать на месте хеш-функцию для каких-то данных, или, например, спросить: до N какого порядка реально решать задачи с O(N^2), а O(N^3), а на кластере? и т.д. Подобные вопросы дают реальный выхлоп, который применим в жизни.

А уж если есть желание «проверить сообразительность», то куда полезнее вопросы на общее представления о мире вокруг и взаимосвязях в нем. Я как-то был реально озадачен, когда меня спросили «А сколько весит Боинг-747?». Я хоть и учился в МАИ, но точной цифры ни разу не знал. Но исходя и элементарных понятий и количестве людей в самолете, грузе, соотношении топлива и массы и т.д. – можно дать оценку, или что более важно, показать умение логически и реально мыслить.

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

Update: В комментариях подсказали полезную ссылку по теме.

Jason Fried, David Heinemeier Hansson, "Rework"

Книга от создателей компании 37 signals и Ruby on Rails о том, как можно вести малый бизнес в IT, не разрывая зад по 10-12 часов в день, а только с 9 до 5, и при этом достойно и даже очень зарабатывать.

Jason Fried, David Heinemeier Hansson, "Rework"



Довольно пафосная книга, состоящая из мини глав, похожих на посты в блоге (эта книга и родилась из блога), но многие ее посылы стоит усвоить. С ними легче и приятнее жить, и во многом ранее скучном и нудном может появиться вдруг смысл. Также книга может подтолкнуть в мир самостоятельной работы на самого себя, например, написание shareware.

Но одна глава мне очень понравилась. Про резюме и сопроводительные письма.

Приведу ее целиком как есть и собственный вольный перевод, если кому надо.

Resumes are ridiculous

We all know resumes are a joke. They're exaggerations. They're filled with "action verbs" that don't mean anything. They list job titles and responsibilities that are vaguely accurate at best. And there's no way to verify most of what's on there. The whole thing is a face.

Worst of all, they're too easy. Anyone can create a decent-enough resume. That's why half-assed applicants love them so much. They can shotgun out hundreds at a time to potential employers. It's another form of spam. They don't care about landing your job; they just care about landing any job.

If someone sends out a resume to three hundred companies, that's a huge red flag right there. There's no way that applicant has researched you. There's no way he knows what's different about your company.

If you hire based on this garbage, you're missing the point of what hiring is about. You want a specific candidate who cares specifically about your company, your products, your customers, and your job.

So how do you find these candidates? First step: Check the cover letter. In a cover letter, you get actual communication instead of a list of skills, verbs, and years of irrelevance. There's no way an applicant can churn out hundreds of personalized letters. That's why the cover letter is a much better test than a resume. You hear someone's actual voice and are able to recognize if it's in tune with you and your company.

Trust you gut reaction. If the first paragraph sucks, the second has to work that much harder. If there's no hook in the first three, it's unlikely there's a match there. On the other hand, if your gut is telling you there's a chance at a real match, then move on to the interview stage.

Перевод:

Резюме – это недоразумение.

Всем известно, что резюме – это ерунда. Одни преувеличения. В них полно «правильных» глаголов, которые ничего не значат. В них перечисляются должности и обязанности, которые в лучшем случае сомнительны. И нет никакой возможности проверить, что за всем этим стоит. Сплошной фарс.

И хуже все то, что их очень просто сделать. Любой может написать приличное резюме. Вот почему недоразвитые кандидаты так их любят. Они могут наплодить их сотни для потенциальных работодателей. Это еще один тип спама. Им не важно получить работу у вас. Им нужна какая-то работа.

Если кто-то посылает резюме в три сотни компаний, это плохой знак. Такой кандидат не пытался ничего о вас узнать, и чем ваша компания отличается от других.

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

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

Доверяйте нутру. Если в первом параграфе все плохо, во втором шансов уже мало. Если первые три вас не зацепили, вряд ли это ваш случай. С другой стороны, если вы чувствуете, что-то тут есть – переходите к интервью.

От себя могу добавить. Всегда стоит писать cover letter, причем вдумчивые и персонализированные. В процессе их написания часто приходит понимание - "а хочу ли сам я там работать?"

Книгу после прочтения я продал назад через Амазон.

Bernard Girard, "The Google Way"

Было интересно почитать про историю Google, посему купил вот эту книгу.

Bernard Girard, The Google Way



Не могу сказать, что мне особо понравилось, хоть фактов в книге предостачно: и про самое начало, и про выход на IPO (работая сейчас в сфере finance, знаю, как обычно инвестиционные банкиры наживаются на процедуре IPO, но Гугл их сильно в этом плане разочаровал, не дав им кусок своего пирога), и про правило 20%, и про систему peer review, и про наличие технической иерархии и про многое другое.

Разок прочитать можно, но не более того. Книгу продал назад через Amazon Market Place.

Задача про гномов

Товарищ рассказал интересную задачку и был очень удивлен, что я ее не слышал.

Поймал людоед несколько гномов (количество в задаче не задается), и сказал, что завтра он всех выстроит в колонну один за другим и оденет всем на головы либо черную, либо белую шапку. Гномы будут стоять так, что каждый будет видеть шапки только тех, кто впереди (последний видит всех, кроме себя, а первый – никого). Свою собственную шапку гномы не видят. Количество черных и белых шапок произвольное (хоть все белые, хоть все черные). Далее людоед, начиная с последнего, будет каждого спрашивать, какая шапка у него на голове. Гном может ответить только одним из двух слов «черная» или «белая». Если ответ неверный, но гном съедается, иначе переходят к следующему. В процессе поедания все пока еще живые гномы слышат, что проиходит сзади, то есть хоть они и не видят товарищей сзади, но слышат – когда кого съели, а кого нет, и также их ответы.

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

Вопрос: что за стратегию придумали гномы?

Задача имеет очень красивое решение, имеющее прямое отношение к компьютерной науке.

Ответ будет позже, если кто вдруг не догадается.

parsetInt() в JavaScript'e

Напоролся на совершенно замечательное поведение в parseInt()'e:

Я думал, что код ниже должен давать мне числа от 0 до 9:

<script>
var n = [ '00', '01', '02', '03', '04', '05', '06', '07', '08', '09' ];
for (var i = 0; i < n.length; ++i)
  document.writeln(parseInt(n[i]));
</script>

Но выводится:

0 1 2 3 4 5 6 7 0 0

И это поведение законно, так как лидирующие нули рассматриваются как признак восьмеричного числа, а 8 и 9 не являются восьмеричными знаками.

Правильно надо писать так:

<script>
var n = [ '00', '01', '02', '03', '04', '05', '06', '07', '08', '09' ];
for (var i = 0; i < n.length; ++i)
  document.writeln(parseInt(n[i], 10));
</script>

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

Общий виртуальный десктоп

В крупных конторах с множеством UNIX-программистов, работающих в основном через telnet/ssh/xterm, разумно сделать общий NFS-раздел, который виден всем, и также монтируется сразу на много машин. Во-первых, все имеют доступ практически ко всему в development пространстве, и во-вторых, содержимое моего home каталога всегда одно и то же на всех машинах (не надо вручную копировать файлы с машины на машину).

Минуту назад я не смог залогиниться xterm'ом из-за каких-то временных проблем в сети и попросил коллегу проверить, все ли работает. У него получилось, и он типа сказал в шутку, что жаль не может передать мне его телнетное окно.

Так вот, только родилась мысль -- а что, если все разработчики будут также "шарить" общий огро-о-о-мный виртуальный десктоп? Захотел что-то передать/показать коллеге -- просто перебросил окно в его "зону видимости".

Идея, конечно, утопичная, но красивая.

Веселые перестановки. Решение (сортировка перестановками соседних элементов)

Итак, мое решение вопроса о приведении одной последовательности к другой, когда можно только переставлять два элемента.

Нас просят привести одну последовательность (исходную) к другой (целевой). То есть логично предположить, что одна последовательность в нужном порядке (целевая), а вторая (исходная) - нет. Так надо просто отсортировать исходную последовательность "в целевую".

Так как целевая последовательность по условию не обязательно отсортированная, то при сортировке "к ней" нельзя просто сравнивать элементы исходной последовательности на больше/меньше, так как в этом случае мы получим на выходе сортировку по правилам системы исчисления. В нашем случае надо принять, что целевая последовательность и есть эталонный отсортированный алфавит, и он задает правила сортировки. При сравнении значений из этого алфавита надо понять, в какой позиции алфавита находится значение и использовать его индекс как ключ сортировки (функция less()).

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

#include <stdlib.h>
#include <stdio.h>

void swap(int* a, int i) {
  int t = a[i];
  a[i] = a[i + 1];
  a[i + 1] = t;
}

#define N 8

const int etalon[] = { 1, 5, 7, 4, 2, 9, 8, 6 };
int from[N] = { 8, 1, 4, 2, 5, 6, 9, 7 };

void insertion_sort(int* a, int n, int (*is_less)(int, int)) {
  int i, j;
  for (i = 1; i < n; ++i) 
    for (j = i - 1; j >= 0 && is_less(a[j + 1], a[j]); j--)
      swap(a, j);
}

void print_array(const char* title, const int* a, int n) {
  int i;
  printf("%9s: ", title);
  for (i = 0; i < n; ++i)
    printf("%d ", a[i]);
  printf("\n");
}

int less(int a, int b) {
  int ia = -1, ib = -1;
  int i;
  for (i = 0; i < N; ++i) {
    if (etalon[i] == a) ia = i;
    if (etalon[i] == b) ib = i;
    if (ia >= 0 && ib >= 0) break;
  }
  return ia < ib;
}

int main() {
  int i, j;

  print_array("Original", from, N);
  insertion_sort(from, N, less);
  print_array("Converted", from, N);
  print_array("Etalon", etalon, N);

  return 0;
}

Запускаем:

 Original: 8 1 4 2 5 6 9 7 
Converted: 1 5 7 4 2 9 8 6 
   Etalon: 1 5 7 4 2 9 8 6 

Вроде работает.

Теперь что со сложностью. Принято считать, что сортировка вставками - это O(N^2) для худшего случая. Так как для сравнения элементов нам приходится искать линейно по эталонной последовательности на каждом шаге, то это еще O(N). В этоге: O(N^3).

Как вариант ускорения, можно изначально сделать отсортированную по значениям копию эталонной последовательности, и хранить не только значение, но его индекс. В этом случае поиск элемента будет уже занимать не O(N), а O(log(N)), и общая сложность будет O(log(N)*N^2).

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

Указание на эти два факта лично я счел бы на однозначно достаточный ответ.