Про методы сортировки

[rikki_t_tavi]

Читала книгу про алгоритмы для жизни (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

Есть и в русском переводе, и даже в киндлмагазине: Алгоритмы для жизни: Простые способы принимать верные решения

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

Comments

[llena-i.livejournal.com]

ну вы даете, такое придумать, восторг и уважение. я столько лет программистка, а никогда к жизни не думала алгоритмы применять.
правда, не могу не отметить, что большинство "быстрых" алгоритмов работают хорошо только на больших объемах данных, тысячах и десятках тысяч объектов, а на 100-200 и бабл-сорт хорош будет. но идея все равно классная!

сортировочные танцы вам ютуб уже показал? https://youtu.be/EdIKIf9mHk0

[july17-hm.livejournal.com]

а если пройти по всему списку и написать ранг привлекательности каждого дела от 1 до 10, а потом отсортировать по этой колонке - не быстрее будет? по крайней мере 1 проход, а не несколько :)

[rikki-t-tavi.livejournal.com]

А если всем ранг будет 10?:)
Зачем мне вообше непривлекательные пункты хранить?

[martichka.livejournal.com]

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

[irene-dy.livejournal.com]

А если список сделать не в ворде, а в какой нибудь специальной списочной программе, вроде todoist, не будет проще, чем в ворде? Там же можно хватать пункт списка и тащить куда надо.

[rikki-t-tavi.livejournal.com]

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

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

[martichka.livejournal.com]

У программистов для этого популярно trello
Одно дело — одна карточка, можно хватать и двигать карточки туда-сюда по списку
(заодно в канбан-доску можно играть, таскать дела по столбцам — в очереди, в процессе, выполнено и пр.опциональные)
Многие для долгоиграющих домашних дел используют

[tigra-olga.livejournal.com]

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

[rikki-t-tavi.livejournal.com]

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

[tigra-olga.livejournal.com]

Кстати да, я тоже так думаю - подсознание рулит)

[polarstar60.livejournal.com]

Я фсю жижнь так и делала -- при переездах, перестановках,наведении общего порядка!!! А люди, оказываются , книги на эту тему пишут!

[rikki-t-tavi.livejournal.com]

А что именно вы делали? Пузырьковую сортировку?

[polarstar60.livejournal.com]

Ой, как все по-научному! СКажем,во время переезда, чтобы вес был более-менее одинаковый, в коробках все подряд; при всем желании книги невозможно поместить отдельно; ни один грузчик не поднимет тякую тяжесть.И
после того, как определилась,что где будет лежать, разбирая ящик, кладу поближе вещи, которые будут лежать в шкафу в одной комнате. Или поближе к двери складываю кухонную утварь. Иду на кухню -- захватываю с собой и раскладываю все по местам. Как-то так. Но сначала, конечно , надо определиться, где что будет находиться.

[fbpa.livejournal.com]

(я долгое время работала программистом и сейчас тоже часто программирую)

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

Например, есть такой вариант сортировки - сортировка слиянием или merge sort. Я опишу его сейчас попроще, но в целом можно не вникать, как он работает, основная мысль - что массив делится много раз на попалам, это мне нужно, чтобы проиллюстрировать, чем отличаются алгоритмы на практике. Так вот, весь массив делится на две части, потом каждая из частей еще раз делится попалам и еще раз попалам, до тех пор пока не останутся действительно маленькие кучки, например, в 3 элемента. А 3 элемента отсортировать легко. Теперь получается вот что: весь первоначальный массив поделен на много маленьких кучек по 2-3 элемента и все эти мелкие кучки отсортированы. Теперь настало время их объединять, а объединить два отсортированных массива просто и нужно гораздо меньше сравнений.

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

Если я выбираю bubble sort, то я прохожу вдоль полки, просматривая книги и, увидев не порядок, меняю книги местами, пока каждая книга не займет свое место. Если у меня всего 2-4 книги стоят не на своем месте, это займет минуту-две.

Если же я выберу merge sort, о, тут все происходит так: я вываливаю все книги с полки на пол, начинаю их делить на кучки, потом кучки делить на новые кучки и так до того момента, пока в каждой кучке не останется по 2-3 книги. Но это еще не все! Теперь я беру по две кучки и начинаю их объединять, потом объединять двойные кучки, потом объединять объединенные двойные кучки и так до тех пор, пока все книги не будут отсортированны и уже после этого я их поставлю обратно на полку. Потому что очень эффективный в случае реально больших плохо отсортированных массивов алгоритм merge sort вчистую проигрывает bubble sort-у для маленьких почти отсортированных массивов.

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

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

Ну а программистам по идее надо знать, как конкретно реализованы разные виды сортировки и их слабые\сильные места, чтобы правильно применять нужный вид сортировки. На самом деле, конечно, в 99% случаев используется quick sort.

[rikki-t-tavi.livejournal.com]

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