Про методы сортировки
Читала книгу про алгоритмы для жизни (Algorithms to Live By: The Computer Science of Human Decisions ) и оттуда ушла читать подробнее в интернете про методы сортировки. Программисты о них знают хорошо - их учат разным существующим способам разобрать кучу случайно сваленных элементов на ровную последовательность в нужном порядке. Методов этих множество - они отличаются тем, сколько шагов нужно сделать до окончательной сортировки. Это ведь тоже важно. Если у меня куча книг на полке и мне нужно их поставить в каком-то порядке, каждая перестановка - это мне нужно вытащить книгу, перенести ее куда-то и всунуть там. Чтобы не отвалилась рука и не ушла неделя, лучше выбрать метод, где перестановок таких будет как можно меньше.
Самый простой метод, который и мне приходил в голову, для сортировки дел по важности - это смотреть на два рядом стоящих пункта и менять их местами, если один важнее другого. Потом смотреть на следующую пару и тоже сравнивать, важнее одно дело другого. И менять их местами, ну, или оставлять их в том же порядке. И так идти от начала до конца списка. Потом повторять. И так, пока все дела не встанут на свое место по мере важности. Или все книги в нужном порядке. Или все бусины от большой к самой маленькой.
Это самый неэффективный метод, хотя первым приходит в голову. Называется «пузырьковый» - или еще «тонущий». То есть там в результате перемен либо самые маленькие легкие пузырьки всплывают вверх, либо тяжелый «тонут» вниз, чем тяжелее, тем ниже. Он самый длинный и неэффективный и отдельные специалисты даже ратуют за то, чтобы его перестали преподавать студентам.
Но мне вот он тоже первым в голову пришел! Перекладывать две соседние карточки, или два соседних пункта в списке.
Однако я начиталась и более эффективных способов и стала пробовать их.
Для эксперимента взяла одну часть большого списка сканерского финиша. Это была часть «крафты» и туда ушло все, что не входило в какие-то понятные группы типа «рисование» или «вязание». Понятно, что там были одни проекты интереснее, легче и более готовые к работе, чем другие. Тут встал вопрос - а какой у меня будет принцип сортировки? Скажем, у сортировки списка чисел, которые стоят в перепутанном порядке, принцип может быть простой - расставить числа от меньшего к большему. А что у меня?
Можно было расставить в порядке от «у меня все готово для этого дела» до - «у меня есть только идея». Или по принципу - насколько оно уже сделано. Есть те, что совсем не начаты, а есть те, которым осталось немного до завершения. Можно рассортировать по легкости. Вот эти самые легкие - и их можно быстро сделать и получить радость «поставил галочку», а те - самые сложные, для них нужно много усилий. Или по принципу «насколько хорошо оно будет выглядеть на инстаграме» - а что, тоже принцип! Или по принципу важности - что нужнее и важнее - я не знаю - для карьеры, для заработка, для обучения и продвижения мастерства.
Я задумалась и поняла, что тогда нужно делать несколько сортировок, а потом сводить все в таблицу, где у каждого дела будут баллы по разным принципам и дальше можно будет выбирать дело с наибольшей суммой баллов. Но это было слишком объемно. А попробовать метод сортировки мне хотелось прямо сейчас!
И я решила, что буду ориентироваться просто на внутреннее чувство - сколько радостного предвкушения у меня вызывает вид этого дела, что мне веселее делать, что охотнее я представляю сделанным.
И для сортировки я выбрала метод quicksort, «быстрая сортировка».
Там сначала сортируешь быстро всю группу, а затем все более мелкие части ее. Нужно выбрать один элемент (по-русски «опорный», по-английски «pivot») и быстро раскидать всю группу выше и ниже его. То есть смотреть на каждый элемент - лучше он выбранного опорного или хуже. Я выбрала просто средний в списке и смотрела вокруг него. Если пункт был интереснее и веселее - я переносила его в начало первой половины, а если скучнее и сложнее - в конец второй.
Это, кстати, очень интересно и совершенно неожиданно. Некоторые пункты, которые мне казались до этого важными, ушли во вторую половину, а те, что были помечены «когда-нибудь», вдруг всплывали наверх.
Так что весь список у меня оказался рассортированным на две (неравные) половины - 1)лучше и интереснее выбранного пункта и 2)неинтереснее и сложнее его. На этом я ушла спать в предвкушении, как завтра продолжу. И утром первым делом продолжила. Взяла верхнюю половину, выбрала там опять один пункт и начала перемещать пункты выше и ниже его. Кстати, в первой сортировке у меня все вертелось вокруг пункта «фриволите на игле». А во второй вокруг пункта «расписать пингвинов на деревянной заготовке» :)
То есть в первом шаге я разделила все дела нате, что «интереснее и привлекательнее фриволите на игле» и «менее интересные и привлекательные, чем фриволите на игле». А во втором шаге более интересные, чем фриволите, дела делились на две половины - более интересные, чем роспись пингвина или менее интересные.
В этом способе нужно так последовательно разбирать все меньшие группы, быстро раскидывая их на то, что ниже и выше опорного пункта. Пока не останутся группки из двух пунктов, которые легко поменять местами. И так останется список, полностью выровненный от самого приятного до самого наименее приятного.
Но я наигралась раньше, надо сказать:) Мне же хотелось не на самом деле выровнять список, а только попробовать алгоритм сортировки. К тому же возникла проблема, которая может и у настоящих программистов возникать - а что делать с пунктами, которые равны и которые нельзя поставить выше или ниже из-за понятной величины? У программистов есть решение - их ставят рядом, но в том же порядке, в котором они встречались в первоначальном списке. А у меня было сложнее. Вот, скажем, три дела обладают совершенно одинаковой притягательностью - но ведь в списке они все равно встанут друг за другом - под номерами, скажем, 35, 36 и 37. И будет казаться, что дело 35 лучше, чем 37. А это не так! Я не придумала, что с ними делать. Нельзя же в список из пунктов поставить горизонтальную строку из трех пунктов? Даже если я поставлю - там все равно будет какой-то порядок и что-то окажется первым. Я подумывала помечать их каким-то значком, отмечающим, что они равны, или выделять одним и тем же цветом.
Но в общем я наигралась в свое удовольствие. Кат-пейст с пунктами все равно утомительно делать в ворде. Наверное, если написать все на карточках, будет гораздо легче и быстрее перемещать физические карточки. Но их еще нужно написать! Или распечатать список, убрав номера, и нарезать на полоски. Хм, а это идея!
Вообще система эта раскидывания вокруг опорного пункта мне напомнила, как я в детстве училась решать всякие сложные (или олимпиадные) задачи. Там есть такой способ деления на группы - и именно, когда тебя просят выяснить самое маленькое количество ходов. Вот вроде такого: у тебя есть десять монет, одна из них фальшивая и весит меньше остальных, у тебя есть простые весы с двумя чашками - за какое наименьшее количество взвешиваний можно найти эту монету?
Простой ход мысли (пузырьковый) говорит нам - взвешивать по паре монет, перебирая их, пока мы не найдем ту, которая будет легче соседки. А можно пойти укрупненным путем - разделить пополам и взвесить по пять монет на каждой чашке - одна половина будет легче, так мы обнаружим группу, в которой фальшивая монета. Потом взять эту группу из пяти монет и положить по две монеты на каждую чашку. Если они равны, фальшивая та, что осталась на столе. Если не равны - мы опять нашли группу из двух монет, в которой одна фальшивая.
В общем, со списками своих проектов я все поняла и знаю теперь как быстро их сортировать на более перспективные и менее. И даже если я не будут так делать со всем списком, я могу в своем методе рандомном включить еще и сортировку. То есть сейчас я, чтобы не тратить время на вычисления, просто кидаю жребий и делаю то, что выпало под этим номером. А можно, если выпало дело не такое интересное или для которого ничего не готово, не просто перебрасывать жребий, а еще и перемещать пункт в списке - в самый конец, например. И в следующий раз не включать его в выборы.
Кстати! Вы знаете, что голосовой помощник на телефоне может выбирать случайное число? Я теперь никаких кубиков не бросаю и даже сайт с рендомным выбором не ищу, я просто говорю - Эй, Сири, выбери мне число между единицей и 252. И Сири такая, нежным голосом с английским акцентом - 89.
А я продолжаю читать о разных других алгоритмах сортировки и предвкушаю разные интересные проверки впереди. То, как я собирала мамины старинные рассыпавшиеся бусы, оказывается, называется heapsort. И таким методом я выбирала дела, когда была подростком.Он у меня назывался «выбирать самые крупные или самые мелкие бусины, когда делаешь дела».
Я этот текст написала в самом начале работы. С тех пор я уже огромный список сканерского финиша отсортировала весь. Потом напишу, как именно. И что я вычитала в книге - как лучше выбирать дела.
Книга в оригинале вот: Algorithms to Live By: The Computer Science of Human Decisions
Есть и в русском переводе, и даже в киндлмагазине: Алгоритмы для жизни: Простые способы принимать верные решения
Название, как часто у русских переводов, уводит в сторону. Упоминание программирования из него выбросили, оставили только завлекаловку со словом "простые". Но там практически все основано на компьютерных науках и методах.