Blog posts

У одного из моих коллег в офисе висел плакат: очкарик склонился над компьютером и собирается нажать кнопку Download, за его спиной огромный лохматый казак с черной лохматой шевелюрой, выпучеными глазами и огромными кривыми зубами, в полушубке, опоясанный пулеметными лентами, с огромной красной звездой на папахе одобрительно похлопывает паренька по спине. Все это сопровождается подписью “When you download free music, you download communism!”

Это ответ на пост про быструю сортировку (quicksort).

Цитата: "Пока возился обратил внимание на забавный момент: как бы ни распределялись данные, количество нетривиальных вызовов Quicksort (когда i<j) всегда равно длине массива минус один. Сначала удивился, а потом дошло почему. Можете ответить?"

Исходная задачка:

На обычной плитке шоколада выдавлены канавки, чтобы удобнее ее было ломать. У вас есть шоколадка на которой есть три полоски в длину и пять в ширину. Понятное дело, это делит ее на 15 кусочков.

Задача: разломать ее на 15 кусочков сделав минимальное число разломов. Разлом делается так: берете со стола один из кусочков, ломаете его по канавке, кладете результат обратно на стол.

Вчера супруга, которая решила посмотреть вокруг место работы получше и начала каждый вечер делать программистские задачки на C#, C++ и Python, полвечера убила на быструю сортировку (quicksort). Я тем временем опять удивился насколько много граничных условий вылезает в исходном алгоритме Хоара. Да-да, знаю, уже придумали улучшенную и починенную версию, но захотелось исправить сохранив дух решения, с двумя индексами сходящимися к центру. И вот что получилось. Вроде работает. Кто-нибудь видит баг?

Вот фотография Круглого Озера с моего любимого трейла в начале зимы, точнее под Рождество 2007-го года:

А вот фотография того же озера в марте 2008-го:

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

Попытался заказать билет на самолет дочке для поездки на восточное побережье... Ну, выбор невелик, бывшая майкрософтовская Expedia или Yahoo Travel. Yahoo Travel на первой же странице отказался показывать календарь для выбора дат:

Много-много лет назад советский космонавт Юрий Гагарин первым вышел в космос на корабле Восток:

Всех с Днем Космонавтики!

All functions predefined in XPath 1.0 as defined by XPath 1.0 specifications by W3C.

This grammar is extracted from the official W3C XML 1.0 specifications where it is spread all across the document.