Сортировка без циклов на JavaScript

Как мы знаем, при сортировке элементов в программировании всегда применяют циклы. Циклы используются для повторяющихся операций, или хотя бы для перебора входных элементов. А можно ли сделать сортировку без циклов (без использования операторов for, do while, goto)?

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

Немного о сортировке и алгоритмах

Сортировка - это упорядочивание сравнимых элементов. Существует много алгоритмов сортировки.

Есть очень простой алгоритм - сортировка пузырьком. Его суть заключается в следующем: циклично проходиться по всему массиву, сортируя по 1 элементу за раз, пока есть что сортировать. Это не эффективный алгоритм, он широко используется в обучении программированию. Так как при сортировке пузырьком отсортированные элементы «накапливаются» в одном конце массива - его уже можно не сортировать. Это отличие позволяет сократить количество итераций при сортировке. Некоторые упрощённые реализации сортировки пузырьком могут пренебрегать этим, делая 2 полных цикла по входному массиву данных.

Сортировка без циклов и массивов - пример, исходный код

Как можно убрать циклы в реализации сортировки на языке программирования? Можно воспользоваться стандартной функцией сортировки array.sort() в JavaScript, но это только замаскирует циклы - они есть внутри реализации этой функции. Если мы знаем заранее количество элементов в массиве, то можем выписать последовательность команд сравнения и замены последовательно. То есть разворачиваем цикл в линейную последовательность команд.

На примере массива A из 2-х переменных это выглядит так:

• если A[1]>A[2] то поменять A[1] и A[2]

Что делать с массивом из 3-х переменных? Всё так же просто::

• если A[1]>A[2] то поменять A[1] и A[2]
• если A[2]>A[3] то поменять A[2] и A[3]
• если A[1]>A[2] то поменять A[1] и A[2]

Что делать с массивом из 4-х элементов? То же самое - их можно написать последовательно, но их получится много. Число операций сравнения и условной перестановки возрастает, но они похожи. Процесс написания такой программы сортировки можно автоматизировать, что и было сделано на JavaScript. Кроме того, можно сортировать так не только массивы, но и отдельные переменные, что не возможно запрограммировать при нормальных циклах.

В форме генератора программы сортировки введите число переменных, можете поставить дополнительные параметры сортировки, затем нажмите кнопку «Сгенерировать» чтобы получить программу сортировки на JS.

Вы получили рабочий пример сортировки пузырьком без применения циклов! Это решение можно легко перевести с JS на другие C++ подобные языки программирования. Для этого замените var на int или другие типы данных, в вашем любимом языке программирования.

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

Зачем это нужно, и где применяется?

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

Не смотря на кажущуюся абсурдность разворачивания циклов, иногда сам метод разворачивания циклов применяют в реальных программах. Это иногда делалось для оптимизации кода к некоторым архитектурам процессоров, используя на полную мультискалярную архитектуру конвеера. Многие современные процессоры (на 2017 год) в этом уже не нуждаются, так как они сами умеют "разворачивать" циклы, или же используются инструкции SSE для работы с массивами. Например, требуется прибавить к массиву A всегда состоящему из 5 элементов число x, тогда часто код A[0]+=x, A[1]+=x, A[2]+=x, A[3]+=x, A[4]+=x будет выполняться в разы быстрее, чем циклом. Но это зависит от конкретной модели ЦП. Для подсчёта сумм, разворачивают циклы по другому - делают много циклов с несколькими счёткиками (s1, s2, s3, s4), затем суммируя результаты. В C++ при оптимизации компилятор сам может определять такие циклы и разворачивать их (компилятор gcc с параметром -o3). Стоит отметить, что если компилятору явно указать архитектуру процессора и поддерживаемые инструкции (SSE, и др.), то компилятор может принять более верное решение, и использовать более лучшие решения, чем разворачивание циклов. Скомпилированная так программа будет использовать все возможности конкретной модели ЦП, но может не заработать на других компьютерах, у которых будет старый процессор, или через много лет, когда эти технологии устареют и от них откажутся (пример - 3DNow!).

Разворачивание циклов в C++ требует глубокого знания и понимания внутренних процессов компьютера, и требует отдельной статьи. Большинству программистов не обязательно о них знать, так как это касается очень узкого круга задач, и большинство современных компиляторов оптимизируют автоматически гораздо лучше, чем программисты могут это сделать вручную.