Инструменты пользователя
basics_of_algorithms:sorting_algorithms
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:sorting_algorithms [2023/10/03 19:48] werwolf создано |
basics_of_algorithms:sorting_algorithms [2023/10/04 22:18] (текущий) werwolf [Универсальная функция сортировки] |
||
|---|---|---|---|
| Строка 48: | Строка 48: | ||
| Похожий принцип работает и с элементами массива при такой сортировке. Посмотрите на этот рисунок: | Похожий принцип работает и с элементами массива при такой сортировке. Посмотрите на этот рисунок: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImJkMWMyMjIwMTM2MzhiYTI3NTBlYTIwYWZjMzBkMGRhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=bf2193f69d2e92c4700be20f47bd7f7d23f9f486360c8ce23ac426674a41520c|Пузырьковая сортировка}}Мы идем по массиву и перемещаем вправо самый большой элемент из просмотренных. Так мы находим элемент со значением 10, который в итоге побеждает во всех сравнениях и оказывается в правом конце массива. | + | {{ :basics_of_algorithms:image_processing20231003-26-zku720.png?500x700 |}} |
| + | {{ :basics_of_algorithms:bubble-sort.gif |}} | ||
| + | |||
| + | Мы идем по массиву и перемещаем вправо самый большой элемент из просмотренных. Так мы находим элемент со значением 10, который в итоге побеждает во всех сравнениях и оказывается в правом конце массива. | ||
| Рассмотрим механизм работы данной сортировки на реальном примере. Возьмем массив и сравним элементы попарно от начала к концу: первый со вторым, второй с третьим, третий с четвертым и так далее. | Рассмотрим механизм работы данной сортировки на реальном примере. Возьмем массив и сравним элементы попарно от начала к концу: первый со вторым, второй с третьим, третий с четвертым и так далее. | ||
| Строка 56: | Строка 59: | ||
| Пузырьковая сортировка реализуется в JavaScript с помощью такой функции: | Пузырьковая сортировка реализуется в JavaScript с помощью такой функции: | ||
| - | <code> | + | <code javascript> |
| const bubbleSort = (items) => { | const bubbleSort = (items) => { | ||
| for (let limit = items.length - 1; limit > 0; limit -= 1) { | for (let limit = items.length - 1; limit > 0; limit -= 1) { | ||
| Строка 70: | Строка 73: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def bubble_sort(items): | def bubble_sort(items): | ||
| for limit in range(len(items) - 1, 0, -1): | for limit in range(len(items) - 1, 0, -1): | ||
| Строка 79: | Строка 83: | ||
| items[i], items[i + 1] = items[i + 1], items[i] | items[i], items[i + 1] = items[i + 1], items[i] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 98: | Строка 104: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static void bubbleSort(int[] items) { | public static void bubbleSort(int[] items) { | ||
| Строка 116: | Строка 124: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Мы видим здесь два вложенных цикла. **Внешний цикл** ограничивает внутренний цикл на каждом проходе. Сначала он простирается до конца массива, но после первого прохода там оказывается максимальный элемент. | Мы видим здесь два вложенных цикла. **Внешний цикл** ограничивает внутренний цикл на каждом проходе. Сначала он простирается до конца массива, но после первого прохода там оказывается максимальный элемент. | ||
| Строка 121: | Строка 130: | ||
| **Внутренний цикл** на следующем проходе движется до предпоследнего элемента, а затем до пред-пред-последнего — и так до тех пор, пока не остается один элемент в левой части: | **Внутренний цикл** на следующем проходе движется до предпоследнего элемента, а затем до пред-пред-последнего — и так до тех пор, пока не остается один элемент в левой части: | ||
| - | <code> | + | <code javascript> |
| for (let limit = items.length - 1; limit > 0; limit -= 1) { | for (let limit = items.length - 1; limit > 0; limit -= 1) { | ||
| // ... | // ... | ||
| Строка 127: | Строка 136: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| for limit in range(len(items) - 1, 0, -1): | for limit in range(len(items) - 1, 0, -1): | ||
| # ... | # ... | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | ||
| - | <code> | + | <details> |
| + | <summary>PHP</summary> | ||
| + | |||
| + | <code php> | ||
| <?php | <?php | ||
| Строка 143: | Строка 156: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| for (var limit = items.length - 1; limit > 0; limit--) { | for (var limit = items.length - 1; limit > 0; limit--) { | ||
| // ... | // ... | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| + | |||
| Мы помним, что в JavaScript элементы массива нумеруются с 0 — следовательно, индекс последнего элемента массива ''items'' равен ''items.length - 1''. | Мы помним, что в JavaScript элементы массива нумеруются с 0 — следовательно, индекс последнего элемента массива ''items'' равен ''items.length - 1''. | ||
| Строка 156: | Строка 173: | ||
| Обмен двух элементов выполняется с помощью временной переменной, которую мы назвали ''temporary'' (т.е. **временная**): | Обмен двух элементов выполняется с помощью временной переменной, которую мы назвали ''temporary'' (т.е. **временная**): | ||
| - | <code> | + | <code javascript> |
| const temporary = items[i]; | const temporary = items[i]; | ||
| items[i] = items[i + 1]; | items[i] = items[i + 1]; | ||
| Строка 162: | Строка 179: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| # В Python временная переменная не требуется | # В Python временная переменная не требуется | ||
| items[i], items[i + 1] = items[i + 1], items[i] | items[i], items[i + 1] = items[i + 1], items[i] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 178: | Строка 198: | ||
| $items[$i + 1] = $temporary; | $items[$i + 1] = $temporary; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var temporary = items[i]; | var temporary = items[i]; | ||
| items[i] = items[i + 1]; | items[i] = items[i + 1]; | ||
| items[i + 1] = temporary; | items[i + 1] = temporary; | ||
| </code> | </code> | ||
| + | </details> | ||
| На каждом шаге мы находим наибольший элемент в массиве, а последний оставшийся неизбежно оказывается наименьшим — так мы получаем упорядоченный массив. Проверим работу алгоритма: | На каждом шаге мы находим наибольший элемент в массиве, а последний оставшийся неизбежно оказывается наименьшим — так мы получаем упорядоченный массив. Проверим работу алгоритма: | ||
| - | <code> | + | <code javascript> |
| const items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2]; | const items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2]; | ||
| bubbleSort(items); | bubbleSort(items); | ||
| Строка 195: | Строка 218: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2] | items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2] | ||
| bubble_sort(items) | bubble_sort(items) | ||
| print(items) # => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] | print(items) # => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 212: | Строка 238: | ||
| print_r($items); // => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] | print_r($items); // => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| int[] items = {2, 3, 4, 3, 1, 2, 4, 5, 1, 2}; | int[] items = {2, 3, 4, 3, 1, 2, 4, 5, 1, 2}; | ||
| App.bubbleSort(items); | App.bubbleSort(items); | ||
| Строка 221: | Строка 249: | ||
| // => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] | // => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] | ||
| </code> | </code> | ||
| + | </details> | ||
| При пузырьковой сортировке соседние элементы часто меняются местами, поэтому она работает довольно медленно. Чтобы сэкономить время, можно сократить количество перестановок. В этом поможет **сортировка выбором**. | При пузырьковой сортировке соседние элементы часто меняются местами, поэтому она работает довольно медленно. Чтобы сэкономить время, можно сократить количество перестановок. В этом поможет **сортировка выбором**. | ||
| Строка 228: | Строка 257: | ||
| Этот алгоритм сначала проводит операции сравнения и находит наименьший элемент, а только потом помещает его в начало массива. После первого прохода алгоритм исключает первый элемент из рассмотрения и ищет минимальный элемент в оставшейся части массива, а затем помещаем его на второе место: | Этот алгоритм сначала проводит операции сравнения и находит наименьший элемент, а только потом помещает его в начало массива. После первого прохода алгоритм исключает первый элемент из рассмотрения и ищет минимальный элемент в оставшейся части массива, а затем помещаем его на второе место: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjhiNjI5NWY2YmRhNTZjZDc3YWRjYTlkMTVkYWE4YWRkLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=30408593712626cf6e45f5428412ec61277425149f292a478ca1d7f2d85475ec|Сортировка выбором}}Этот алгоритм работает гораздо быстрее пузырьковой сортировки, потому что сравнений здесь столько же, а вот обмен всего один — в самом конце. | + | {{ :basics_of_algorithms:image_processing20231003-35-a15wqx.jpg?500X700 |}} |
| + | {{ :basics_of_algorithms:selection-sort.gif |}} | ||
| + | Этот алгоритм работает гораздо быстрее пузырьковой сортировки, потому что сравнений здесь столько же, а вот обмен всего один — в самом конце. | ||
| Рассмотрим функцию, реализующую сортировку выбором в Java Script: | Рассмотрим функцию, реализующую сортировку выбором в Java Script: | ||
| - | <code> | + | <code javascript> |
| const selectionSort = (items) => { | const selectionSort = (items) => { | ||
| for (let i = 0; i < items.length - 1; i += 1) { | for (let i = 0; i < items.length - 1; i += 1) { | ||
| Строка 249: | Строка 280: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def selection_sort(items): | def selection_sort(items): | ||
| for i in range(len(items) - 1): | for i in range(len(items) - 1): | ||
| Строка 260: | Строка 292: | ||
| items[i], items[index_min] = items[index_min], items[i] | items[i], items[index_min] = items[index_min], items[i] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 282: | Строка 316: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static void selectionSort(int[] items) { | public static void selectionSort(int[] items) { | ||
| Строка 303: | Строка 339: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| В реализации мы сохраняем не сам минимальный элемент, а его индекс в массиве. Это нужно потому, что в конце каждого прохода минимальный элемент записывается в начало массива. При этом элемент, который был там до этого, нужно вставить куда-то в неупорядоченную половину — легче всего просто поменять их местами. | В реализации мы сохраняем не сам минимальный элемент, а его индекс в массиве. Это нужно потому, что в конце каждого прохода минимальный элемент записывается в начало массива. При этом элемент, который был там до этого, нужно вставить куда-то в неупорядоченную половину — легче всего просто поменять их местами. | ||
| Строка 312: | Строка 349: | ||
| Возьмем для примера массив, отсортированный в порядке убывания — от больших к меньшим. Чтобы разместить элементы в порядке возрастания, надо попарно поменять их местами: первый и последний, потом второй и предпоследний, и так далее, как показано на схеме: | Возьмем для примера массив, отсортированный в порядке убывания — от больших к меньшим. Чтобы разместить элементы в порядке возрастания, надо попарно поменять их местами: первый и последний, потом второй и предпоследний, и так далее, как показано на схеме: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjJmMTg0YzUyNjJlZTQzYTk3MzY3NTdlNTVkODhjN2E0LmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=d62599f53bace5421f278065934416db311f85f3d980b5ad569e14f663b5d182|Быстрая сортировка}}Сортировки массива в обратном порядке реализуется так: | + | {{ :basics_of_algorithms:image_processing20231003-47-u6u9yi.jpg |}} |
| + | Сортировки массива в обратном порядке реализуется так: | ||
| - | <code> | + | <code javascript> |
| let left = 0; | let left = 0; | ||
| let right = items.length - 1; | let right = items.length - 1; | ||
| Строка 328: | Строка 366: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| left = 0 | left = 0 | ||
| right = len(items) - 1 | right = len(items) - 1 | ||
| Строка 339: | Строка 378: | ||
| right -= 1 | right -= 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 357: | Строка 398: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var left = 0; | var left = 0; | ||
| var right = items.length - 1; | var right = items.length - 1; | ||
| Строка 373: | Строка 416: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| В примере выше мы создали две переменные-указателя. Переменная ''left'' указывает на следующий элемент для обмена слева, а переменная ''right'' — справа. Для обмена используем уже знакомую временную переменную ''temporary'': | В примере выше мы создали две переменные-указателя. Переменная ''left'' указывает на следующий элемент для обмена слева, а переменная ''right'' — справа. Для обмена используем уже знакомую временную переменную ''temporary'': | ||
| - | <code> | + | <code javascript> |
| const temporary = items[left]; | const temporary = items[left]; | ||
| items[left] = items[right]; | items[left] = items[right]; | ||
| Строка 382: | Строка 426: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| # В Python временная переменная не требуется | # В Python временная переменная не требуется | ||
| items[left], items[right] = items[right], items[left] | items[left], items[right] = items[right], items[left] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 398: | Строка 445: | ||
| $items[$right] = $temporary; | $items[$right] = $temporary; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var temporary = items[left]; | var temporary = items[left]; | ||
| items[left] = items[right]; | items[left] = items[right]; | ||
| items[right] = temporary; | items[right] = temporary; | ||
| </code> | </code> | ||
| + | <details> | ||
| На каждой итерации цикла после обмена мы увеличиваем левый указатель, сдвигая его вправо, и одновременно уменьшаем правый, сдвигая влево: | На каждой итерации цикла после обмена мы увеличиваем левый указатель, сдвигая его вправо, и одновременно уменьшаем правый, сдвигая влево: | ||
| - | <code> | + | <code javascript> |
| left += 1; | left += 1; | ||
| right -= 1; | right -= 1; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| left += 1 | left += 1 | ||
| right -= 1 | right -= 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 429: | Строка 482: | ||
| $right -= 1; | $right -= 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| left++; | left++; | ||
| right--; | right--; | ||
| </code> | </code> | ||
| + | </details> | ||
| Похожий подход применяется в алгоритме быстрой сортировки. Он частично упорядочивает массив, перемещая в начало маленькие элементы, а в конец — большие. | Похожий подход применяется в алгоритме быстрой сортировки. Он частично упорядочивает массив, перемещая в начало маленькие элементы, а в конец — большие. | ||
| Строка 445: | Строка 501: | ||
| Чтобы не запутаться в алгоритме быстрой сортировки, разберем его на схематичном примере. В самом начале наш массив выглядит так: | Чтобы не запутаться в алгоритме быстрой сортировки, разберем его на схематичном примере. В самом начале наш массив выглядит так: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjQ0MGVjYWM5MDQxMzVlYTk0NGU4ZDIzOWM5NDJkNjRkLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=c39c1f76a65ab0c6c24ee97c61e48817561482ce19f0844f83f5b88a4e41ae95|Быстрая сортировка}}В качестве опорного элемента выбрано число 4. Левый указатель смотрит на 5, а правый — на 3. | + | {{ :basics_of_algorithms:image_processing20231003-24-trn55f.jpg |}} |
| + | В качестве опорного элемента выбрано число 4. Левый указатель смотрит на 5, а правый — на 3. | ||
| Далее двигаем левый указатель и пропускаем элементы меньше опорного, и ищем неправильный элемент слева. Затем двигаем правый указатель, пропуская элементы больше опорного. | Далее двигаем левый указатель и пропускаем элементы меньше опорного, и ищем неправильный элемент слева. Затем двигаем правый указатель, пропуская элементы больше опорного. | ||
| Строка 451: | Строка 508: | ||
| Таким образом мы ищем пару элементов, в которой левый больше правого. Когда пара найдена, меняем элементы местами. В нашем примере 5 и 3 находятся в неправильной позиции — их надо поменять: | Таким образом мы ищем пару элементов, в которой левый больше правого. Когда пара найдена, меняем элементы местами. В нашем примере 5 и 3 находятся в неправильной позиции — их надо поменять: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjU3YjgxNzE2NzgyNTBiNTg1NWUzNmEwNjI3MWE4NGM4LmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4a306026587b9219e97382e05f5b63c0369e885a3c8d02cce31c0717f07a134e|Быстрая сортировка}}Ищем следующую пару для обмена. Справа от 3 находится 4 — наш следующий кандидат для обмена. Обратите внимание, что 4 — опорный элемент, но он тоже принимает участие в сравнениях и обменах. | + | {{ :basics_of_algorithms:image_processing20231003-24-y3v74i.jpg |}} |
| + | Ищем следующую пару для обмена. Справа от 3 находится 4 — наш следующий кандидат для обмена. Обратите внимание, что 4 — опорный элемент, но он тоже принимает участие в сравнениях и обменах. | ||
| Слева от числа 5 находятся числа 6, 9 и 7. Они больше опорного элемента 4, поэтому указатель их пропускает. В итоге он останавливается на числе 2: | Слева от числа 5 находятся числа 6, 9 и 7. Они больше опорного элемента 4, поэтому указатель их пропускает. В итоге он останавливается на числе 2: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjUyOWNkZjY4ODRlNWY3NWU5MjExZmE1MDZjNDU1NmFlLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=dcb5c0f140468e718d4ea4e5e7aa1dedfa017fdd4c4b4e5d3d1991a4ab80d86e|Быстрая сортировка}}Меняем их местами и ищем следующую пару. Следующие кандидаты — числа 10 и 1: | + | {{ :basics_of_algorithms:image_processing20231003-23-6az633.jpg |}} |
| + | Меняем их местами и ищем следующую пару. Следующие кандидаты — числа 10 и 1: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImMxM2Q3ODk2MTU5YmU1Njk5NWMwZjk3ZjliMDBmODU0LmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=36335b58aa154e557eb5f078a740d483ad3e066bfb386950531e004a7f21e23a|Быстрая сортировка}}Меняем их местами и останавливаемся, потому что левый и правый указатели упираются друг в друга. Мы получили **частично упорядоченный массив**. Разбиваем его на две части там, где указатели встретились: | + | {{ :basics_of_algorithms:image_processing20231003-35-m8dsb6.jpg |}} |
| + | Меняем их местами и останавливаемся, потому что левый и правый указатели упираются друг в друга. Мы получили **частично упорядоченный массив**. Разбиваем его на две части там, где указатели встретились: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImYwODhjOGQ0ZTAwYjFhMjBlODFkYTg3MTQ1MTQzNjRjLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=cd16a2224e8025e603665fd3247eb20e56aea9ea98b18248ed8d5041b9c11de2|Быстрая сортировка}}Продолжаем частичное упорядочивание левой и правой половин массива. Правая половина перед упорядочиванием показана на рисунке: | + | {{ :basics_of_algorithms:image_processing20231003-25-cbibo7.jpg |}} |
| + | Продолжаем частичное упорядочивание левой и правой половин массива. Правая половина перед упорядочиванием показана на рисунке: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjFkMTZhZjk1OGQ4YjlhZWFlMTc0ZDU2ZjI3NzhkYmY3LmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=434b5aa635e871cf02738b4eb4a80c38b03be7bea28fff8556bafd3d63a78e1b|Быстрая сортировка}}Выбираем новый опорный элемент из подмассива. На этот раз это 7. Сдвигая указатели, меняем местами пары 10 и 5, а также 8 и 6. Числа 4 и 9 останутся на своих местах. Частично упорядоченный подмассив принимает такой вид: | + | {{ :basics_of_algorithms:image_processing20231003-30-rxos8m.jpg |}} |
| + | Выбираем новый опорный элемент из подмассива. На этот раз это 7. Сдвигая указатели, меняем местами пары 10 и 5, а также 8 и 6. Числа 4 и 9 останутся на своих местах. Частично упорядоченный подмассив принимает такой вид: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6ImE3ZGU4NjNjM2I5ODFjODAxNmQyMTIwN2EwOTRlZWY0LmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=b438511b6c10a9baf752d108abce6e7592ee91db340680deb51792f56d8db948|Быстрая сортировка}}Левый и правый указатель встречаются посередине — на числе 7. Мы снова разбиваем массив на две половины и переходим к упорядочиванию левой и правой половин. | + | {{ :basics_of_algorithms:image_processing20231003-30-sdbdvm.jpg |}} |
| + | Левый и правый указатель встречаются посередине — на числе 7. Мы снова разбиваем массив на две половины и переходим к упорядочиванию левой и правой половин. | ||
| ==== Как реализовать быструю сортировку ==== | ==== Как реализовать быструю сортировку ==== | ||
| Строка 469: | Строка 532: | ||
| Попробуем реализовать алгоритм на JavaScript. Начнем с функции частичного упорядочивания: | Попробуем реализовать алгоритм на JavaScript. Начнем с функции частичного упорядочивания: | ||
| - | <code> | + | <code javascript> |
| const partition = (items, left, right, pivot) => { | const partition = (items, left, right, pivot) => { | ||
| while (true) { | while (true) { | ||
| Строка 494: | Строка 557: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def partition(items, left, right, pivot): | def partition(items, left, right, pivot): | ||
| while True: | while True: | ||
| Строка 512: | Строка 576: | ||
| right -= 1 | right -= 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 542: | Строка 608: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int partition(int[] items, int left, int right, int pivot) { | public static int partition(int[] items, int left, int right, int pivot) { | ||
| Строка 571: | Строка 639: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| В качестве параметров функция получает: | В качестве параметров функция получает: | ||
| Строка 580: | Строка 649: | ||
| Сначала в цикле пропускаются элементы слева, которые меньше опорного: | Сначала в цикле пропускаются элементы слева, которые меньше опорного: | ||
| - | <code> | + | <code javascript> |
| while (items[left] < pivot) { | while (items[left] < pivot) { | ||
| left += 1; | left += 1; | ||
| Строка 586: | Строка 655: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| while items[left] < pivot: | while items[left] < pivot: | ||
| left += 1 | left += 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 602: | Строка 674: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| while (items[left] < pivot) { | while (items[left] < pivot) { | ||
| left++; | left++; | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Затем пропускаются элементы справа, которые больше опорного: | Затем пропускаются элементы справа, которые больше опорного: | ||
| - | <code> | + | <code javascript> |
| while (items[right] > pivot) { | while (items[right] > pivot) { | ||
| right -= 1; | right -= 1; | ||
| Строка 619: | Строка 694: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| while items[right] > pivot: | while items[right] > pivot: | ||
| right -= 1 | right -= 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 635: | Строка 713: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| while (items[right] > pivot) { | while (items[right] > pivot) { | ||
| right--; | right--; | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Если указатели встретились или зашли друг за друга, мы завершаем цикл и возвращаем место встречи в качестве результата. Нам предстоит разбить массив на два подмассива, поэтому надо решить, что именно возвращать. Мы можем сказать, что граница — это место, где заканчивается левый подмассив, или место, где начинается правый. Большой разницы здесь нет. | Если указатели встретились или зашли друг за друга, мы завершаем цикл и возвращаем место встречи в качестве результата. Нам предстоит разбить массив на два подмассива, поэтому надо решить, что именно возвращать. Мы можем сказать, что граница — это место, где заканчивается левый подмассив, или место, где начинается правый. Большой разницы здесь нет. | ||
| Строка 648: | Строка 729: | ||
| Решим, что функция ''partition'' возвращает индекс элемента, где начинается правый подмассив: | Решим, что функция ''partition'' возвращает индекс элемента, где начинается правый подмассив: | ||
| - | <code> | + | <code javascript> |
| if (left >= right) { | if (left >= right) { | ||
| return right + 1; | return right + 1; | ||
| Строка 654: | Строка 735: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if left >= right: | if left >= right: | ||
| return right + 1 | return right + 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 670: | Строка 754: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (left >= right) { | if (left >= right) { | ||
| return right + 1; | return right + 1; | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Если указатели остановились, то они указывают на два элемента в неверном порядке. Левый указатель смотрит на элемент, который больше опорного. При этом правый указатель смотрит на элемент, который меньше опорного. | Если указатели остановились, то они указывают на два элемента в неверном порядке. Левый указатель смотрит на элемент, который больше опорного. При этом правый указатель смотрит на элемент, который меньше опорного. | ||
| Строка 683: | Строка 770: | ||
| Меняем местами и сдвигаем элементы, чтобы в следующей итерации продолжить поиск следующей неправильной пары: | Меняем местами и сдвигаем элементы, чтобы в следующей итерации продолжить поиск следующей неправильной пары: | ||
| - | <code> | + | <code java> |
| const temporary = items[left]; | const temporary = items[left]; | ||
| items[left] = items[right]; | items[left] = items[right]; | ||
| Строка 692: | Строка 779: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| items[left], items[right] = items[right], items[left] | items[left], items[right] = items[right], items[left] | ||
| left += 1 | left += 1 | ||
| right -= 1 | right -= 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 712: | Строка 802: | ||
| $right -= 1; | $right -= 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var temporary = items[left]; | var temporary = items[left]; | ||
| items[left] = items[right]; | items[left] = items[right]; | ||
| items[right] = temporary; | items[right] = temporary; | ||
| </code> | </code> | ||
| + | </details> | ||
| Обычно условие завершения цикла пишут в начале (оператор ''while'') или в конце (оператор ''do…while''). В функции ''partition()'' условие становится известно в середине цикла. | Обычно условие завершения цикла пишут в начале (оператор ''while'') или в конце (оператор ''do…while''). В функции ''partition()'' условие становится известно в середине цикла. | ||
| Строка 725: | Строка 818: | ||
| В языках программирования нет специального синтаксиса для такой ситуации. Обычно программисты записывают бесконечный цикл с помощью конструкции ''while (true)'', а выход из цикла делают с помощью операторов ''break'' или ''return'': | В языках программирования нет специального синтаксиса для такой ситуации. Обычно программисты записывают бесконечный цикл с помощью конструкции ''while (true)'', а выход из цикла делают с помощью операторов ''break'' или ''return'': | ||
| - | <code> | + | <code javascript> |
| while (true) { | while (true) { | ||
| // ... | // ... | ||
| Строка 737: | Строка 830: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| <code> | <code> | ||
| Строка 748: | Строка 842: | ||
| # ... | # ... | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 764: | Строка 860: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| while (true) { | while (true) { | ||
| // ... | // ... | ||
| Строка 778: | Строка 876: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Частично упорядоченный массив нельзя назвать полностью отсортированным. Чтобы закончить сортировку, мы должны рекурсивно повторить упорядочивание для левой и правой половин массива. | Частично упорядоченный массив нельзя назвать полностью отсортированным. Чтобы закончить сортировку, мы должны рекурсивно повторить упорядочивание для левой и правой половин массива. | ||
| Строка 783: | Строка 882: | ||
| Про рекурсию мы говорили на прошлом уроке. Так выглядит рекурсивный алгоритм быстрой сортировки. Он немного похож на рекурсивную функцию бинарного поиска: | Про рекурсию мы говорили на прошлом уроке. Так выглядит рекурсивный алгоритм быстрой сортировки. Он немного похож на рекурсивную функцию бинарного поиска: | ||
| - | <code> | + | <code javascript> |
| const sort = (items, left, right) => { | const sort = (items, left, right) => { | ||
| const length = right - left + 1; | const length = right - left + 1; | ||
| Строка 799: | Строка 898: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| <code> | <code> | ||
| Строка 813: | Строка 913: | ||
| sort(items, split_index, right) | sort(items, split_index, right) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 834: | Строка 936: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int partition(int[] items, int left, int right, int pivot) { | public static int partition(int[] items, int left, int right, int pivot) { | ||
| Строка 858: | Строка 962: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Для упорядочивания нужно не менее двух элементов. Поэтому мы остановим рекурсивный вызов, когда встретим пустой подмассив или подмассив с одним элементом: | Для упорядочивания нужно не менее двух элементов. Поэтому мы остановим рекурсивный вызов, когда встретим пустой подмассив или подмассив с одним элементом: | ||
| - | <code> | + | <code javascript> |
| const length = right - left + 1; | const length = right - left + 1; | ||
| Строка 878: | Строка 983: | ||
| </code> | </code> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 889: | Строка 995: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var length = right - left + 1; | var length = right - left + 1; | ||
| Строка 899: | Строка 1007: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Функция ''partition'' возвращает индекс первого элемента в правом подмассиве. Это помогает функции ''sort'' корректно вызвать саму себя: | Функция ''partition'' возвращает индекс первого элемента в правом подмассиве. Это помогает функции ''sort'' корректно вызвать саму себя: | ||
| - | <code> | + | <code javascript> |
| const splitIndex = partition(items, left, right, pivot); | const splitIndex = partition(items, left, right, pivot); | ||
| sort(items, left, splitIndex - 1); | sort(items, left, splitIndex - 1); | ||
| Строка 908: | Строка 1017: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| split_index = partition(items, left, right, pivot) | split_index = partition(items, left, right, pivot) | ||
| sort(items, left, split_index - 1) | sort(items, left, split_index - 1) | ||
| sort(items, split_index, right) | sort(items, split_index, right) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 925: | Строка 1037: | ||
| sort($items, $splitIndex, $right); | sort($items, $splitIndex, $right); | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var splitIndex = partition(items, left, right, pivot); | var splitIndex = partition(items, left, right, pivot); | ||
| sort(items, left, splitIndex - 1); | sort(items, left, splitIndex - 1); | ||
| sort(items, splitIndex, right); | sort(items, splitIndex, right); | ||
| </code> | </code> | ||
| + | </details> | ||
| Единственный код, который вызывает вопросы — выбор опорного элемента: | Единственный код, который вызывает вопросы — выбор опорного элемента: | ||
| - | <code> | + | <code javascript> |
| const pivot = items[left]; | const pivot = items[left]; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| pivot = items[left] | pivot = items[left] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $pivot = $items[$left]; | $pivot = $items[$left]; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var pivot = items[left]; | var pivot = items[left]; | ||
| </code> | </code> | ||
| + | </details> | ||
| Почему мы всегда выбираем самый левый элемент подмассива? | Почему мы всегда выбираем самый левый элемент подмассива? | ||
| Строка 972: | Строка 1093: | ||
| Чтобы упростить себе жизнь, напишем вспомогательную функцию, которая всегда сортирует массив целиком: | Чтобы упростить себе жизнь, напишем вспомогательную функцию, которая всегда сортирует массив целиком: | ||
| - | <code> | + | <code javascript> |
| const quicksort = (items) => sort(items, 0, items.length - 1); | const quicksort = (items) => sort(items, 0, items.length - 1); | ||
| Строка 980: | Строка 1101: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def quicksort(items): | def quicksort(items): | ||
| sort(items, 0, len(items) - 1) | sort(items, 0, len(items) - 1) | ||
| Строка 990: | Строка 1112: | ||
| print(items) # => [10, 24, 34, 43, 52, 55, 57, 93, 99] | print(items) # => [10, 24, 34, 43, 52, 55, 57, 93, 99] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 1005: | Строка 1129: | ||
| print_r($items); // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ] | print_r($items); // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| Строка 1023: | Строка 1149: | ||
| // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ] | // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ] | ||
| </code> | </code> | ||
| + | </details> | ||
| Быстрая сортировка намного эффективнее сортировки выбором. Причем эта разница особенно видна на больших массивах. Если сортировать миллион элементов, сортировка выбором окажется медленнее в десятки тысяч раз. | Быстрая сортировка намного эффективнее сортировки выбором. Причем эта разница особенно видна на больших массивах. Если сортировать миллион элементов, сортировка выбором окажется медленнее в десятки тысяч раз. | ||
| Строка 1038: | Строка 1165: | ||
| Сам массив выглядит так: | Сам массив выглядит так: | ||
| - | <code> | + | <code javascript> |
| const products = [ | const products = [ | ||
| { name: "Телевизор", price: 100000, rating: 9.1 }, | { name: "Телевизор", price: 100000, rating: 9.1 }, | ||
| Строка 1052: | Строка 1179: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| products = [ | products = [ | ||
| {"name": "Телевизор", "price": 100000, "rating": 9.1}, | {"name": "Телевизор", "price": 100000, "rating": 9.1}, | ||
| Строка 1067: | Строка 1195: | ||
| ] | ] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 1085: | Строка 1215: | ||
| ]; | ]; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| Map[] products = { | Map[] products = { | ||
| Map.of ("name", "Телевизор", "price", 100000, "rating", 9.1), | Map.of ("name", "Телевизор", "price", 100000, "rating", 9.1), | ||
| Строка 1101: | Строка 1233: | ||
| }; | }; | ||
| </code> | </code> | ||
| + | </details> | ||
| Можно реализовать несколько функций сортировки, но есть и более эффективный способ. Интернет-магазину подойдет **универсальная функция сортировки**. | Можно реализовать несколько функций сортировки, но есть и более эффективный способ. Интернет-магазину подойдет **универсальная функция сортировки**. | ||
| Строка 1110: | Строка 1243: | ||
| Вот так будет выглядеть компаратор, сравнивающий элементы по цене: | Вот так будет выглядеть компаратор, сравнивающий элементы по цене: | ||
| - | <code> | + | <code javascript> |
| const compareByPrice = (item1, item2) => { | const compareByPrice = (item1, item2) => { | ||
| if (item1.price < item2.price) { | if (item1.price < item2.price) { | ||
| Строка 1122: | Строка 1255: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def compare_by_price(item1, item2): | def compare_by_price(item1, item2): | ||
| if item1[price] < item2[price]: | if item1[price] < item2[price]: | ||
| Строка 1133: | Строка 1267: | ||
| return 1 | return 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 1150: | Строка 1286: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByPrice = (item1, item2) -> { | public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByPrice = (item1, item2) -> { | ||
| var price1 = (int) item1.get("price"); | var price1 = (int) item1.get("price"); | ||
| Строка 1167: | Строка 1305: | ||
| }; | }; | ||
| </code> | </code> | ||
| + | </details> | ||
| А вот так — компаратор, сравнивающий элементы по рейтингу: | А вот так — компаратор, сравнивающий элементы по рейтингу: | ||
| - | <code> | + | <code javascript> |
| const compareByRating = (item1, item2) => { | const compareByRating = (item1, item2) => { | ||
| if (item1.rating < item2.rating) { | if (item1.rating < item2.rating) { | ||
| Строка 1182: | Строка 1321: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def compare_by_rating(item1, item2): | def compare_by_rating(item1, item2): | ||
| if item1[rating] < item2[rating]: | if item1[rating] < item2[rating]: | ||
| Строка 1193: | Строка 1333: | ||
| return 1 | return 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 1210: | Строка 1352: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByRating = (item1, item2) -> { | public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByRating = (item1, item2) -> { | ||
| var rating1 = (double) item1.get("rating"); | var rating1 = (double) item1.get("rating"); | ||
| Строка 1227: | Строка 1371: | ||
| }; | }; | ||
| </code> | </code> | ||
| + | </details> | ||
| Универсальная функция сравнивает два элемента, но не использует операторы «больше» или «меньше». Вместо этого она вызывает компаратор и проверяет результат. Так выглядит универсальная пузырьковая сортировка: | Универсальная функция сравнивает два элемента, но не использует операторы «больше» или «меньше». Вместо этого она вызывает компаратор и проверяет результат. Так выглядит универсальная пузырьковая сортировка: | ||
| - | <code> | + | <code javascript> |
| const bubbleSort = (items, comparator) => { | const bubbleSort = (items, comparator) => { | ||
| for (let limit = items.length - 1; limit > 0; limit -= 1) { | for (let limit = items.length - 1; limit > 0; limit -= 1) { | ||
| Строка 1243: | Строка 1388: | ||
| }; | }; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def bubble_sort(items, comparator): | def bubble_sort(items, comparator): | ||
| for limit in range(len(items) - 1, 0, -1): | for limit in range(len(items) - 1, 0, -1): | ||
| Строка 1253: | Строка 1400: | ||
| items[i], items[i + 1] = items[i + 1], items[i] | items[i], items[i + 1] = items[i + 1], items[i] | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 1272: | Строка 1421: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static void bubbleSort(Map[] items, ToIntBiFunction comparator) { | public static void bubbleSort(Map[] items, ToIntBiFunction comparator) { | ||
basics_of_algorithms/sorting_algorithms.1696351703.txt.gz · Последние изменения: 2023/10/03 19:48 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
