ПостДень 2775. #Оффтоп

День 2775. #Оффтоп Сортировка I-Can’t-Believe-It-Can-Sort Думаю, что с каждым чуть ли не ежедневно случается ситуация, когда вы написали код и думаете, что он работает, а он не работает. А бывало ли у вас наоборот? Однажды один профессор на лекции про алгоритмы сортировки написал наивный и очевидно неверный алгоритм. Два вложенных цикла, внутри которых одно условие и смена элементов местами, если условие выполняется (некий неверный вариант пузырьковой сортировки): for i = 0 to length - 1: for j = 0 to length - 1: if A[i] < A[j]: swap(A[i], A[j]) Полная бессмыслица, которая, кажется, должна либо не сделать ничего, либо просто перемешать элементы. Однако позже выяснилось, что алгоритм действительно правильно сортирует элементы. Доказательство вот тут. Этот алгоритм стал популярным примером для изучения с помощью инструментов формальной верификации программ, позволяющих доказать, что подобная контринтуитивная структура действительно работает. В итоге алгоритм назвали сортировкой «Не-Могу-Поверить-Что-Это-Сортирует» (I-Can’t-Believe-It-Can-Sort). Про него и про другие алгоритмы сортировки в новом видео Мэта Паркера. А если вы хотите подробно изучить все алгоритмы сортировки, можно на пару часиков залипнуть вот сюда.