Различия

Здесь показаны различия между двумя версиями данной страницы.

--- basics_of_algorithms:sorting_algorithms [2023/10/04 21:36]
werwolf [Быстрая сортировка]
+++ basics_of_algorithms:sorting_algorithms [2023/10/04 22:18] (текущий)
werwolf [Универсальная функция сортировки]
@@ Строка 48: / Строка 48: @@
 Похожий принцип работает и с элементами массива при такой сортировке. Посмотрите на этот рисунок:
-{{ :basics_of_algorithms:image_processing20231003-26-zku720.jpg?500x700 |}}
+{{ :basics_of_algorithms:image_processing20231003-26-zku720.png?500x700 |}}
 {{ :basics_of_algorithms:bubble-sort.gif |}}
@@ Строка 257: / Строка 257: @@
 Этот алгоритм сначала проводит операции сравнения и находит наименьший элемент, а только потом помещает его в начало массива. После первого прохода алгоритм исключает первый элемент из рассмотрения и ищет минимальный элемент в оставшейся части массива, а затем помещаем его на второе место:
+{{ :basics_of_algorithms:image_processing20231003-35-a15wqx.jpg?500X700 |}}
 {{ :basics_of_algorithms:selection-sort.gif |}}
 Этот алгоритм работает гораздо быстрее пузырьковой сортировки, потому что сравнений здесь столько же, а вот обмен всего один — в самом конце.
@@ Строка 349: / Строка 349: @@
 Возьмем для примера массив, отсортированный в порядке убывания — от больших к меньшим. Чтобы разместить элементы в порядке возрастания, надо попарно поменять их местами: первый и последний, потом второй и предпоследний, и так далее, как показано на схеме:
-{{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjJmMTg0YzUyNjJlZTQzYTk3MzY3NTdlNTVkODhjN2E0LmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=d62599f53bace5421f278065934416db311f85f3d980b5ad569e14f663b5d182|Быстрая сортировка}}Сортировки массива в обратном порядке реализуется так:
+{{ :basics_of_algorithms:image_processing20231003-47-u6u9yi.jpg |}}
+Сортировки массива в обратном порядке реализуется так:
 <code javascript>
@@ Строка 365: / Строка 366: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 left = 0
 right = len(items) - 1
@@ Строка 376: / Строка 378: @@
     right -= 1
 </code>
+</details>
 <details>
@@ Строка 498: / Строка 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.
 Далее двигаем левый указатель и пропускаем элементы меньше опорного, и ищем неправильный элемент слева. Затем двигаем правый указатель, пропуская элементы больше опорного.
@@ Строка 504: / Строка 508: @@
 Таким образом мы ищем пару элементов, в которой левый больше правого. Когда пара найдена, меняем элементы местами. В нашем примере 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:
-{{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. Мы снова разбиваем массив на две половины и переходим к упорядочиванию левой и правой половин.
 ==== Как реализовать быструю сортировку ====
@@ Строка 522: / Строка 532: @@
 Попробуем реализовать алгоритм на JavaScript. Начнем с функции частичного упорядочивания:
-<code>
+<code javascript>
 const partition = (items, left, right, pivot) => {
   while (true) {
@@ Строка 547: / Строка 557: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def partition(items, left, right, pivot):
     while True:
@@ Строка 565: / Строка 576: @@
         right -= 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 595: / Строка 608: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     public static int partition(int[] items, int left, int right, int pivot) {
@@ Строка 624: / Строка 639: @@
 }
 </code>
+</details>
 В качестве параметров функция получает:
@@ Строка 633: / Строка 649: @@
 Сначала в цикле пропускаются элементы слева, которые меньше опорного:
-<code>
+<code javascript>
 while (items[left] < pivot) {
   left += 1;
@@ Строка 639: / Строка 655: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 while items[left] < pivot:
     left += 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 655: / Строка 674: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 while (items[left] < pivot) {
     left++;
 }
 </code>
+</details>
 Затем пропускаются элементы справа, которые больше опорного:
-<code>
+<code javascript>
 while (items[right] > pivot) {
   right -= 1;
@@ Строка 672: / Строка 694: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 while items[right] > pivot:
     right -= 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 688: / Строка 713: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 while (items[right] > pivot) {
     right--;
 }
 </code>
+</details>
 Если указатели встретились или зашли друг за друга, мы завершаем цикл и возвращаем место встречи в качестве результата. Нам предстоит разбить массив на два подмассива, поэтому надо решить, что именно возвращать. Мы можем сказать, что граница — это место, где заканчивается левый подмассив, или место, где начинается правый. Большой разницы здесь нет.
@@ Строка 701: / Строка 729: @@
 Решим, что функция ''partition'' возвращает индекс элемента, где начинается правый подмассив:
-<code>
+<code javascript>
 if (left >= right) {
   return right + 1;
@@ Строка 707: / Строка 735: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 if left >= right:
     return right + 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 723: / Строка 754: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 if (left >= right) {
     return right + 1;
 }
 </code>
+</details>
 Если указатели остановились, то они указывают на два элемента в неверном порядке. Левый указатель смотрит на элемент, который больше опорного. При этом правый указатель смотрит на элемент, который меньше опорного.
@@ Строка 736: / Строка 770: @@
 Меняем местами и сдвигаем элементы, чтобы в следующей итерации продолжить поиск следующей неправильной пары:
-<code>
+<code java>
 const temporary = items[left];
 items[left] = items[right];
@@ Строка 745: / Строка 779: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 items[left], items[right] = items[right], items[left]
 left += 1
 right -= 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 765: / Строка 802: @@
 $right -= 1;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 var temporary = items[left];
 items[left] = items[right];
 items[right] = temporary;
 </code>
+</details>
 Обычно условие завершения цикла пишут в начале (оператор ''while'') или в конце (оператор ''do…while''). В функции ''partition()'' условие становится известно в середине цикла.
@@ Строка 778: / Строка 818: @@
 В языках программирования нет специального синтаксиса для такой ситуации. Обычно программисты записывают бесконечный цикл с помощью конструкции ''while (true)'', а выход из цикла делают с помощью операторов ''break'' или ''return'':
-<code>
+<code javascript>
 while (true) {
   // ...
@@ Строка 790: / Строка 830: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code>
@@ Строка 801: / Строка 842: @@
     # ...
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 817: / Строка 860: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 while (true) {
     // ...
@@ Строка 831: / Строка 876: @@
 }
 </code>
+</details>
 Частично упорядоченный массив нельзя назвать полностью отсортированным. Чтобы закончить сортировку, мы должны рекурсивно повторить упорядочивание для левой и правой половин массива.
@@ Строка 836: / Строка 882: @@
 Про рекурсию мы говорили на прошлом уроке. Так выглядит рекурсивный алгоритм быстрой сортировки. Он немного похож на рекурсивную функцию бинарного поиска:
-<code>
+<code javascript>
 const sort = (items, left, right) => {
   const length = right - left + 1;
@@ Строка 852: / Строка 898: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code>
@@ Строка 866: / Строка 913: @@
     sort(items, split_index, right)
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 887: / Строка 936: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     public static int partition(int[] items, int left, int right, int pivot) {
@@ Строка 911: / Строка 962: @@
 }
 </code>
+</details>
 Для упорядочивания нужно не менее двух элементов. Поэтому мы остановим рекурсивный вызов, когда встретим пустой подмассив или подмассив с одним элементом:
-<code>
+<code javascript>
 const length = right - left + 1;
@@ Строка 931: / Строка 983: @@
 </code>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 942: / Строка 995: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 var length = right - left + 1;
@@ Строка 952: / Строка 1007: @@
 }
 </code>
+</details>
 Функция ''partition'' возвращает индекс первого элемента в правом подмассиве. Это помогает функции ''sort'' корректно вызвать саму себя:
-<code>
+<code javascript>
 const splitIndex = partition(items, left, right, pivot);
 sort(items, left, splitIndex - 1);
@@ Строка 961: / Строка 1017: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 split_index = partition(items, left, right, pivot)
 sort(items, left, split_index - 1)
 sort(items, split_index, right)
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 978: / Строка 1037: @@
 sort($items, $splitIndex, $right);
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 var splitIndex = partition(items, left, right, pivot);
 sort(items, left, splitIndex - 1);
 sort(items, splitIndex, right);
 </code>
+</details>
 Единственный код, который вызывает вопросы — выбор опорного элемента:
-<code>
+<code javascript>
 const pivot = items[left];
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 pivot = items[left]
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
 $pivot = $items[$left];
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 var pivot = items[left];
 </code>
+</details>
 Почему мы всегда выбираем самый левый элемент подмассива?
@@ Строка 1025: / Строка 1093: @@
 Чтобы упростить себе жизнь, напишем вспомогательную функцию, которая всегда сортирует массив целиком:
-<code>
+<code javascript>
 const quicksort = (items) => sort(items, 0, items.length - 1);
@@ Строка 1033: / Строка 1101: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def quicksort(items):
     sort(items, 0, len(items) - 1)
@@ Строка 1043: / Строка 1112: @@
 print(items)  # => [10, 24, 34, 43, 52, 55, 57, 93, 99]
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1058: / Строка 1129: @@
 print_r($items); // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ]
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
@@ Строка 1076: / Строка 1149: @@
 // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ]
 </code>
+</details>
 Быстрая сортировка намного эффективнее сортировки выбором. Причем эта разница особенно видна на больших массивах. Если сортировать миллион элементов, сортировка выбором окажется медленнее в десятки тысяч раз.
@@ Строка 1091: / Строка 1165: @@
 Сам массив выглядит так:
-<code>
+<code javascript>
 const products = [
   { name: "Телевизор", price: 100000, rating: 9.1 },
@@ Строка 1105: / Строка 1179: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 products = [
   {"name": "Телевизор", "price": 100000, "rating": 9.1},
@@ Строка 1120: / Строка 1195: @@
 ]
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1138: / Строка 1215: @@
 ];
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 Map[] products = {
   Map.of ("name", "Телевизор", "price", 100000, "rating", 9.1),
@@ Строка 1154: / Строка 1233: @@
 };
 </code>
+</details>
 Можно реализовать несколько функций сортировки, но есть и более эффективный способ. Интернет-магазину подойдет **универсальная функция сортировки**.
@@ Строка 1163: / Строка 1243: @@
 Вот так будет выглядеть компаратор, сравнивающий элементы по цене:
-<code>
+<code javascript>
 const compareByPrice = (item1, item2) => {
   if (item1.price < item2.price) {
@@ Строка 1175: / Строка 1255: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def compare_by_price(item1, item2):
     if item1[price] < item2[price]:
@@ Строка 1186: / Строка 1267: @@
         return 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1203: / Строка 1286: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByPrice = (item1, item2) -> {
         var price1 = (int) item1.get("price");
@@ Строка 1220: / Строка 1305: @@
 };
 </code>
+</details>
 А вот так — компаратор, сравнивающий элементы по рейтингу:
-<code>
+<code javascript>
 const compareByRating = (item1, item2) => {
   if (item1.rating < item2.rating) {
@@ Строка 1235: / Строка 1321: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def compare_by_rating(item1, item2):
     if item1[rating] < item2[rating]:
@@ Строка 1246: / Строка 1333: @@
         return 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1263: / Строка 1352: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByRating = (item1, item2) -> {
         var rating1 = (double) item1.get("rating");
@@ Строка 1280: / Строка 1371: @@
 };
 </code>
+</details>
 Универсальная функция сравнивает два элемента, но не использует операторы «больше» или «меньше». Вместо этого она вызывает компаратор и проверяет результат. Так выглядит универсальная пузырьковая сортировка:
-<code>
+<code javascript>
 const bubbleSort = (items, comparator) => {
   for (let limit = items.length - 1; limit > 0; limit -= 1) {
@@ Строка 1296: / Строка 1388: @@
 };
 </code>
+</details>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def bubble_sort(items, comparator):
     for limit in range(len(items) - 1, 0, -1):
@@ Строка 1306: / Строка 1400: @@
                 items[i], items[i + 1] = items[i + 1], items[i]
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1325: / Строка 1421: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     public static void bubbleSort(Map[] items, ToIntBiFunction comparator) {

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы