basics_of_algorithms:sorting_algorithms []

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Алгоритмы сортировки — Основы алгоритмов и структур данных ======

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

<code>
7, 3, 1, 9, 10, 2, 3, 6, 9, 4, 7, 5, 5, 4, 2, 8, 4, 7
</code>

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

<code>
1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 7, 8, 9, 9, 10
</code>

Не удивительно, что одной из самых полезных задач в программировании считается **сортировка** — перестановка элементов в массиве так, чтобы они располагались в убывающем или возрастающем порядке.

===== Чем полезна сортировка =====

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

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

При этом покупатели выбирают сортировку по своим целям:

  * По возрастанию цены в поисках выгодных предложений 
  * По убыванию цены, если готовы на дорогую покупку 

Чтобы интернет-магазин умел сортировать одни и те же записи по-разному, необходима **универсальная функция сортировки**, о которой поговорим в конце урока.

===== Три алгоритма сортировки =====

Существуют десятки алгоритмов сортировки, но изучать все слишком долго. Чтобы не останавливаться на этой теме, мы выбрали три фундаментальных алгоритма:

  * Пузырьковая сортировка 
  * Сортировка выбором 
  * Быстрая сортировка 

Все три алгоритма сортируют исходный массив, меняя местами его элементы и не требуя дополнительного пространства.

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

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

===== Пузырьковая сортировка =====

Один из самых простых методов — **пузырьковая сортировка**. Это название произошло от ассоциации с воздухом в воде: на дне пузырьки совсем маленькие, но постепенно поднимаются к поверхности, собирают кислород и увеличиваются.

Похожий принцип работает и с элементами массива при такой сортировке. Посмотрите на этот рисунок:

{{ :basics_of_algorithms:image_processing20231003-26-zku720.png?500x700 |}}
{{ :basics_of_algorithms:bubble-sort.gif |}}

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

Рассмотрим механизм работы данной сортировки на реальном примере. Возьмем массив и сравним элементы попарно от начала к концу: первый со вторым, второй с третьим, третий с четвертым и так далее.

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

Пузырьковая сортировка реализуется в JavaScript с помощью такой функции:

<code javascript>
const bubbleSort = (items) => {
  for (let limit = items.length - 1; limit > 0; limit -= 1) {
    for (let i = 0; i < limit; i += 1) {
      if (items[i] > items[i + 1]) {
        const temporary = items[i];
        items[i] = items[i + 1];
        items[i + 1] = temporary;
      }
    }
  }
};
</code>

<details>
<summary>Python</summary>

<code python> 
def bubble_sort(items):
    for limit in range(len(items) - 1, 0, -1):
        for i in range(limit):
              if items[i] > items[i + 1]:
                  items[i], items[i + 1] = items[i + 1], items[i]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function bubbleSort($items)
{
    for ($limit = count($items) - 1; $limit > 0; $limit -= 1) {
        for ($i = 0; $i < $limit; $i += 1) {
            if ($items[$i] > $items[$i + 1]) {
                $temporary = $items[$i];
                $items[$i] = $items[$i + 1];
                $items[$i + 1] = $temporary;
            }
        }
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {
    public static void bubbleSort(int[] items) {
        for (var limit = items.length - 1; limit > 0; limit--) {
            for (var i = 0; i < limit; i++) {
                if (items[i] > items[i + 1]) {
                    var temporary = items[i];
                    items[i] = items[i + 1];
                    items[i + 1] = temporary;
                }
            }
        }
    }
}
</code>
</details>

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

**Внутренний цикл** на следующем проходе движется до предпоследнего элемента, а затем до пред-пред-последнего — и так до тех пор, пока не остается один элемент в левой части:

<code javascript>
for (let limit = items.length - 1; limit > 0; limit -= 1) {
  // ...
}
</code>

<details>
<summary>Python</summary>

<code python>
for limit in range(len(items) - 1, 0, -1):
    # ...
</code>
</details>


<details>
<summary>PHP</summary>

<code php>
<?php

for ($limit = count(items) - 1; $limit > 0; $limit -= 1) {
    // ...
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
for (var limit = items.length - 1; limit > 0; limit--) {
    // ...
}
</code>
</details>


Мы помним, что в JavaScript элементы массива нумеруются с 0 — следовательно, индекс последнего элемента массива ''items'' равен ''items.length - 1''.

Обмен двух элементов выполняется с помощью временной переменной, которую мы назвали ''temporary'' (т.е. **временная**):

<code javascript>
const temporary = items[i];
items[i] = items[i + 1];
items[i + 1] = temporary;
</code>

<details>
<summary>Python</summary>

<code python>
# В Python временная переменная не требуется
items[i], items[i + 1] = items[i + 1], items[i]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$temporary = $items[$i];
$items[$i] = $items[$i + 1];
$items[$i + 1] = $temporary;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var temporary = items[i];
items[i] = items[i + 1];
items[i + 1] = temporary;
</code>
</details>

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

<code javascript>
const items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2];
bubbleSort(items);
console.log(items); // => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5]
</code>

<details>
<summary>Python</summary>

<code python>
items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2]
bubble_sort(items)
print(items)  # => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$items = [2, 3, 4, 3, 1, 2, 4, 5, 1, 2];
bubbleSort($items);
print_r($items); // => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5]
</code>
</details>

<details>
<summary>Java</summary>

<code java>
int[] items = {2, 3, 4, 3, 1, 2, 4, 5, 1, 2};
App.bubbleSort(items);
System.out.println(Arrays.toString(items));
// => [1, 1, 2, 2, 2, 3, 3, 4, 4, 5]
</code>
</details>

При пузырьковой сортировке соседние элементы часто меняются местами, поэтому она работает довольно медленно. Чтобы сэкономить время, можно сократить количество перестановок. В этом поможет **сортировка выбором**.

===== Сортировка выбором =====

Этот алгоритм сначала проводит операции сравнения и находит наименьший элемент, а только потом помещает его в начало массива. После первого прохода алгоритм исключает первый элемент из рассмотрения и ищет минимальный элемент в оставшейся части массива, а затем помещаем его на второе место:

{{ :basics_of_algorithms:image_processing20231003-35-a15wqx.jpg?500X700 |}}
{{ :basics_of_algorithms:selection-sort.gif |}}
Этот алгоритм работает гораздо быстрее пузырьковой сортировки, потому что сравнений здесь столько же, а вот обмен всего один — в самом конце.

Рассмотрим функцию, реализующую сортировку выбором в Java Script:

<code javascript>
const selectionSort = (items) => {
  for (let i = 0; i < items.length - 1; i += 1) {
    let indexMin = i;
    for (let j = i + 1; j < items.length; j += 1) {
      if (items[j] < items[indexMin]) {
        indexMin = j;
      }
    }

    const temporary = items[i];
    items[i] = items[indexMin];
    items[indexMin] = temporary;
  }
};
</code>

<details>
<summary>Python</summary>

<code python>
def selection_sort(items):
    for i in range(len(items) - 1):
        index_min = i
        for j in range(i + 1, len(items)):
              if items[j] < items[index_min]:
                  index_min = j
        items[i], items[index_min] = items[index_min], items[i]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function selectionSort($items)
{
    for ($i = 0; i < count($items) - 1; $i += 1) {
        $indexMin = $i;
        for ($j = $i + 1; $j < count(items); $j += 1) {
            if ($items[$j] < $items[$indexMin]) {
                $indexMin = $j;
            }
        }

        $temporary = $items[$i];
        $items[$i] = $items[$indexMin];
        $items[$indexMin] = $temporary;
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {
    public static void selectionSort(int[] items) {
        for (var i = 0; i < items.length - 1; i++) {
            var indexMin = i;
            for (var j = i + 1; j < items.length; j++) {
                if (items[j] < items[indexMin]) {
                    indexMin = j;
                }
            }

            var temporary = items[i];
            items[i] = items[indexMin];
            items[indexMin] = temporary;
        }
    }
}
</code>
</details>

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

===== Быстрая сортировка =====

Можно сделать сортировку еще быстрее, если менять местами не соседние элементы, а элементы на самом большом расстоянии друг от друга.

Возьмем для примера массив, отсортированный в порядке убывания — от больших к меньшим. Чтобы разместить элементы в порядке возрастания, надо попарно поменять их местами: первый и последний, потом второй и предпоследний, и так далее, как показано на схеме:

{{ :basics_of_algorithms:image_processing20231003-47-u6u9yi.jpg |}}
Сортировки массива в обратном порядке реализуется так:

<code javascript>
let left = 0;
let right = items.length - 1;

while (left < right) {
  const temporary = items[left];
  items[left] = items[right];
  items[right] = temporary;

  left += 1;
  right -= 1;
}
</code>

<details>
<summary>Python</summary>

<code python>
left = 0
right = len(items) - 1

while left < right:
    items[left], items[right] = items[right], items[left]
    left += 1
    right -= 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$left = 0;
$right = count($items) - 1;

while ($left < $right) {
    $temporary = $items[$left];
    $items[$left] = $items[$right];
    $items[$right] = $temporary;

    $left += 1;
    $right -= 1;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var left = 0;
var right = items.length - 1;

while (left < right) {
  var temporary = items[left];
  items[left] = items[right];
  items[right] = temporary;

  left++;
  right--;
}
</code>
</details>

В примере выше мы создали две переменные-указателя. Переменная ''left'' указывает на следующий элемент для обмена слева, а переменная ''right'' — справа. Для обмена используем уже знакомую временную переменную ''temporary'':

<code javascript>
const temporary = items[left];
items[left] = items[right];
items[right] = temporary;
</code>

<details>
<summary>Python</summary>

<code python>
# В Python временная переменная не требуется
items[left], items[right] = items[right], items[left]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$temporary = $items[$left];
$items[$left] = $items[$right];
$items[$right] = $temporary;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var temporary = items[left];
items[left] = items[right];
items[right] = temporary;
</code>
<details>

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

<code javascript>
left += 1;
right -= 1;
</code>

<details>
<summary>Python</summary>

<code python>
left += 1
right -= 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$left += 1;
$right -= 1;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
left++;
right--;
</code>
</details>

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

Частичное упорядочивание делается с помощью программы, похожей на пример выше. Для начала выбираем **опорный элемент** — это условный средний элемент, который помогает отличить маленькие элементы от больших. Затем устанавливаем два указателя на начало и конец массива.

==== Принцип работы быстрой сортировки ====

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

{{ :basics_of_algorithms:image_processing20231003-24-trn55f.jpg |}}
В качестве опорного элемента выбрано число 4. Левый указатель смотрит на 5, а правый — на 3.

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

Таким образом мы ищем пару элементов, в которой левый больше правого. Когда пара найдена, меняем элементы местами. В нашем примере 5 и 3 находятся в неправильной позиции — их надо поменять:

{{ :basics_of_algorithms:image_processing20231003-24-y3v74i.jpg |}}
Ищем следующую пару для обмена. Справа от 3 находится 4 — наш следующий кандидат для обмена. Обратите внимание, что 4 — опорный элемент, но он тоже принимает участие в сравнениях и обменах.

Слева от числа 5 находятся числа 6, 9 и 7. Они больше опорного элемента 4, поэтому указатель их пропускает. В итоге он останавливается на числе 2:

{{ :basics_of_algorithms:image_processing20231003-23-6az633.jpg |}}
Меняем их местами и ищем следующую пару. Следующие кандидаты — числа 10 и 1:

{{ :basics_of_algorithms:image_processing20231003-35-m8dsb6.jpg |}}
Меняем их местами и останавливаемся, потому что левый и правый указатели упираются друг в друга. Мы получили **частично упорядоченный массив**. Разбиваем его на две части там, где указатели встретились:

{{ :basics_of_algorithms:image_processing20231003-25-cbibo7.jpg |}}
Продолжаем частичное упорядочивание левой и правой половин массива. Правая половина перед упорядочиванием показана на рисунке:

{{ :basics_of_algorithms:image_processing20231003-30-rxos8m.jpg |}}
Выбираем новый опорный элемент из подмассива. На этот раз это 7. Сдвигая указатели, меняем местами пары 10 и 5, а также 8 и 6. Числа 4 и 9 останутся на своих местах. Частично упорядоченный подмассив принимает такой вид:

{{ :basics_of_algorithms:image_processing20231003-30-sdbdvm.jpg |}}
Левый и правый указатель встречаются посередине — на числе 7. Мы снова разбиваем массив на две половины и переходим к упорядочиванию левой и правой половин.

==== Как реализовать быструю сортировку ====

Попробуем реализовать алгоритм на JavaScript. Начнем с функции частичного упорядочивания:

<code javascript>
const partition = (items, left, right, pivot) => {
  while (true) {
    while (items[left] < pivot) {
      left += 1;
    }

    while (items[right] > pivot) {
      right -= 1;
    }

    if (left >= right) {
      return right + 1;
    }

    const temporary = items[left];
    items[left] = items[right];
    items[right] = temporary;

    left += 1;
    right -= 1;
  }
};
</code>

<details>
<summary>Python</summary>

<code python>
def partition(items, left, right, pivot):
    while True:
        while items[left] < pivot:
            left += 1

        while items[right] > pivot:
            right -= 1

        if left >= right:
            return right + 1

        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function partition($items, $left, $right, $pivot)
{
    while (true) {
        while ($items[$left] < $pivot) {
            $left += 1;
        }

        while ($items[$right] > $pivot) {
            $right -= 1;
        }

        if ($left >= $right) {
            return $right + 1;
        }

        const temporary = $items[$left];
        $items[$left] = $items[$right];
        $items[$right] = temporary;

        $left += 1;
        $right -= 1;
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {
    public static int partition(int[] items, int left, int right, int pivot) {
        while (true) {
            while (items[left] < pivot) {
                left++;
            }

            while (items[right] > pivot) {
                right--;
            }

            if (left >= right) {
                return right + 1;
            }

            var temporary = items[left];
            items[left] = items[right];
            items[right] = temporary;

            left++;
            right--;
        }
    }
}
</code>
</details>

В качестве параметров функция получает:

  * Массив ''items'' 
  * Указатели на левую и правую часть подмассива ''left'' и ''right'' 
  * Опорный элемент для сравнения ''pivot'' 

Сначала в цикле пропускаются элементы слева, которые меньше опорного:

<code javascript>
while (items[left] < pivot) {
  left += 1;
}
</code>

<details>
<summary>Python</summary>

<code python>
while items[left] < pivot:
    left += 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

while ($items[$left] < $pivot) {
    $left += 1;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
while (items[left] < pivot) {
    left++;
}
</code>
</details>

Затем пропускаются элементы справа, которые больше опорного:

<code javascript>
while (items[right] > pivot) {
  right -= 1;
}
</code>

<details>
<summary>Python</summary>

<code python>
while items[right] > pivot:
    right -= 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

while ($items[$right] > $pivot) {
    $right -= 1;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
while (items[right] > pivot) {
    right--;
}
</code>
</details>

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

Решим, что функция ''partition'' возвращает индекс элемента, где начинается правый подмассив:

<code javascript>
if (left >= right) {
  return right + 1;
}
</code>

<details>
<summary>Python</summary>

<code python>
if left >= right:
    return right + 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

if ($left >= $right) {
    return $right + 1;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
if (left >= right) {
    return right + 1;
}
</code>
</details>

Если указатели остановились, то они указывают на два элемента в неверном порядке. Левый указатель смотрит на элемент, который больше опорного. При этом правый указатель смотрит на элемент, который меньше опорного.

Меняем местами и сдвигаем элементы, чтобы в следующей итерации продолжить поиск следующей неправильной пары:

<code java>
const temporary = items[left];
items[left] = items[right];
items[right] = temporary;

left += 1;
right -= 1;
</code>

<details>
<summary>Python</summary>

<code python>
items[left], items[right] = items[right], items[left]
left += 1
right -= 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$temporary = $items[$left];
$items[$left] = $items[$right];
$items[$right] = $temporary;

$left += 1;
$right -= 1;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var temporary = items[left];
items[left] = items[right];
items[right] = temporary;
</code>
</details>

Обычно условие завершения цикла пишут в начале (оператор ''while'') или в конце (оператор ''do…while''). В функции ''partition()'' условие становится известно в середине цикла.

В языках программирования нет специального синтаксиса для такой ситуации. Обычно программисты записывают бесконечный цикл с помощью конструкции ''while (true)'', а выход из цикла делают с помощью операторов ''break'' или ''return'':

<code javascript>
while (true) {
  // ...

  if (left >= right) {
    return right + 1;
  }

  // ...
}
</code>

<details>
<summary>Python</summary>

<code>
while True:
    # ...

    if left >= right:
        return right + 1

    # ...
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

while (true) {
    // ...

    if ($left >= $right) {
        return $right + 1;
    }

    // ...
}
</code>
</details>

<details>
<summary>Java</summary>

<code java> 
while (true) {
    // ...

    if (left >= right) {
        return right + 1;
    }

    // ...
}
</code>
</details>

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

Про рекурсию мы говорили на прошлом уроке. Так выглядит рекурсивный алгоритм быстрой сортировки. Он немного похож на рекурсивную функцию бинарного поиска:

<code javascript>
const sort = (items, left, right) => {
  const length = right - left + 1;

  if (length < 2) {
    return;
  }

  const pivot = items[left];

  const splitIndex = partition(items, left, right, pivot);
  sort(items, left, splitIndex - 1);
  sort(items, splitIndex, right);
};
</code>

<details>
<summary>Python</summary>

<code>
def sort(items, left, right):
    length = right - left + 1

    if length < 2:
        return

    pivot = items[left]
    split_index = partition(items, left, right, pivot)
    sort(items, left, split_index - 1)
    sort(items, split_index, right)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function sort($items, $left, $right)
{
    $length = $right - $left + 1;

    if ($length < 2) {
       return;
    }

    $pivot = $items[$left];

    $splitIndex = partition($items, $left, $right, $pivot);
    sort($items, $left, splitIndex - 1);
    sort($items, $splitIndex, $right);
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {
    public static int partition(int[] items, int left, int right, int pivot) {
        // ...
    }

    public static void sort(int[] items, int left, int right) {
        var length = right - left + 1;

        if (length < 2) {
            return;
        }

        var pivot = items[left];

        var splitIndex = partition(items, left, right, pivot);
        sort(items, left, splitIndex - 1);
        sort(items, splitIndex, right);
    }
}
</code>
</details>

Для упорядочивания нужно не менее двух элементов. Поэтому мы остановим рекурсивный вызов, когда встретим пустой подмассив или подмассив с одним элементом:

<code javascript>
const length = right - left + 1;

if (length < 2) {
  return;
}
</code>

Python

<code>
length = right - left + 1

if length < 2:
    return
</code>

<details>
<summary>PHP</summary> 

<code php>
<?php

$length = $right - $left + 1;

if ($length < 2) {
    return;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var length = right - left + 1;

if (length < 2) {
    return;
}
</code>
</details>

Функция ''partition'' возвращает индекс первого элемента в правом подмассиве. Это помогает функции ''sort'' корректно вызвать саму себя:

<code javascript>
const splitIndex = partition(items, left, right, pivot);
sort(items, left, splitIndex - 1);
sort(items, splitIndex, right);
</code>

<details>
<summary>Python</summary>

<code python>
split_index = partition(items, left, right, pivot)
sort(items, left, split_index - 1)
sort(items, split_index, right)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$splitIndex = partition($items, $left, $right, $pivot);
sort($items, $left, $splitIndex - 1);
sort($items, $splitIndex, $right);
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var splitIndex = partition(items, left, right, pivot);
sort(items, left, splitIndex - 1);
sort(items, splitIndex, right);
</code>
</details>

Единственный код, который вызывает вопросы — выбор опорного элемента:

<code javascript>
const pivot = items[left];
</code>

<details>
<summary>Python</summary>

<code python>
pivot = items[left]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$pivot = $items[$left];
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var pivot = items[left];
</code>
</details>

Почему мы всегда выбираем самый левый элемент подмассива?

Средний элемент должен находиться ровно посередине отсортированного массива. В таком случае его называют **медианой**. Чтобы узнать медиану, нужно иметь отсортированный массив, а чтобы отсортировать массив — знать медиану. Получается замкнутый круг.

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

Можно выбрать самый левый элемент в качестве опорного элемента — как видно на примере выше, это работает.

Выше мы написали универсальную функцию, которая может сортировать отдельные подмассивы. Сложность в том, что такой функцией не очень удобно пользоваться — приходится передавать параметры ''left'' и ''right'' даже тогда, когда надо отсортировать массив целиком.

Чтобы упростить себе жизнь, напишем вспомогательную функцию, которая всегда сортирует массив целиком:

<code javascript>
const quicksort = (items) => sort(items, 0, items.length - 1);

const items = [ 57, 10, 52, 43, 55, 93, 34, 24, 99 ];
quicksort(items);
console.log(items); // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ]
</code>

<details>
<summary>Python</summary>

<code python>
def quicksort(items):
    sort(items, 0, len(items) - 1)

items = [57, 10, 52, 43, 55, 93, 34, 24, 99]
quicksort(items)
print(items)  # => [10, 24, 34, 43, 52, 55, 57, 93, 99]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function quicksort($items)
{
  return sort($items, 0, count($items) - 1);
}

$items = [ 57, 10, 52, 43, 55, 93, 34, 24, 99 ];
quicksort($items);
print_r($items); // => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ]
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {

    public static void quicksort(int[] items) {
        return sort(items, 0, items.length - 1);
    }

    // ...
}

int[] items = [ 57, 10, 52, 43, 55, 93, 34, 24, 99 ];
App.quicksort(items);
System.out.println(Arrays.toString($items));
// => [ 10, 24, 34, 43, 52, 55, 57, 93, 99 ]
</code>
</details>

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

===== Универсальная функция сортировки =====

Мы реализовали три функции сортировки, каждая из которых упорядочивает в возрастающем порядке элементы простых типов: чисел, дат, строк.

Вспомним пример с интернет-магазином, в котором мы сталкиваемся с более сложной задачей — сортировкой по разным атрибутам. Представим, что нам предстоит сортировать товары по трем атрибутам:

  * Название — ''name'' 
  * Цена — ''price'' 
  * Рейтинг — ''rating'' 

Сам массив выглядит так:

<code javascript>
const products = [
  { name: "Телевизор", price: 100000, rating: 9.1 },
  { name: "Холодильник", price: 20000, rating: 8.3 },
  { name: "Пылесос", price: 14000, rating: 7.5 },
  { name: "Стиральная машина", price: 30000, rating: 9.2 },
  { name: "Миелофон", price: 200000, rating: 8.7 },
  { name: "Микроволновка", price: 7000, rating: 8.2 },
  { name: "Проигрыватель", price: 20000, rating: 9.0 },
  { name: "Посудомоечная машина", price: 80000, rating: 7.8 },
  { name: "Мультиварка", price: 5000, rating: 7.1 },
];
</code>

<details>
<summary>Python</summary>

<code python>
products = [
  {"name": "Телевизор", "price": 100000, "rating": 9.1},
  {"name": "Холодильник", "price": 20000, "rating": 8.3},
  {"name": "Пылесос", "price": 14000, "rating": 7.5},
  {"name": "Стиральная машина", "price": 30000, "rating": 9.2},
  {"name": "Миелофон", "price": 200000, "rating": 8.7},
  {"name": "Микроволновка", "price": 7000, "rating": 8.2},
  {"name": "Проигрыватель", "price": 20000, "rating": 9.0},
  {"name": "Посудомоечная машина", "price": 80000, "rating": 7.8},
  {"name": "Мультиварка", "price": 5000, "rating": 7.1},
]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$products = [
    ['name' => 'Телевизор', 'price' => 100000, 'rating' => 9.1],
    ['name' => 'Холодильник', 'price' => 20000, 'rating' => 8.3],
    ['name' => 'Пылесос', 'price' => 14000, 'rating' => 7.5],
    ['name' => 'Стиральная машина', 'price' => 30000, 'rating' => 9.2],
    ['name' => 'Миелофон', 'price' => 200000, 'rating' => 8.7],
    ['name' => 'Микроволновка', 'price' => 7000, 'rating' => 8.2],
    ['name' => 'Проигрыватель', 'price' => 20000, 'rating' => 9.0],
    ['name' => 'Посудомоечная машина', 'price' => 80000, 'rating' => 7.8],
    ['name' => 'Мультиварка', 'price' => 5000, 'rating' => 7.1],
];
</code>
</details>

<details>
<summary>Java</summary>

<code java>
Map[] products = {
  Map.of ("name", "Телевизор", "price", 100000, "rating", 9.1),
  Map.of ("name", "Холодильник", "price", 20000, "rating", 8.3),
  Map.of ("name", "Пылесос", "price", 14000, "rating", 7.5),
  Map.of ("name", "Стиральная машина", "price", 30000, "rating", 9.2),
  Map.of ("name", "Миелофон", "price", 200000, "rating", 8.7),
  Map.of ("name", "Микроволновка", "price", 7000, "rating", 8.2),
  Map.of ("name", "Проигрыватель", "price", 20000, "rating", 9.0),
  Map.of ("name", "Посудомоечная машина", "price", 80000, "rating", 7.8),
  Map.of ("name", "Мультиварка", "price", 5000, "rating", 7.1)
};
</code>
</details>

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

Каждую из трех видов сортировок выше можно сделать универсальной — и тогда алгоритм сможет сортировать данные любого типа. Для этого надо добавить еще один параметр — функцию сравнения (компаратор). Универсальная функция сортировки вызывает компаратор каждый раз, когда требуется сравнить два элемента и определить, какой из них больше.

У компаратора два параметра — два элемента массива, которые надо сравнить. Если первый больше второго, компаратор возвращает 1. Если первый меньше второго, компаратор возвращает -1. Если элементы равны, компаратор возвращает 0.

Вот так будет выглядеть компаратор, сравнивающий элементы по цене:

<code javascript> 
const compareByPrice = (item1, item2) => {
  if (item1.price < item2.price) {
    return -1;
  } else if (item1.price == item2.price) {
    return 0;
  } else {
    return 1;
  }
};
</code>

<details>
<summary>Python</summary> 

<code python>
def compare_by_price(item1, item2):
    if item1[price] < item2[price]:
        return -1
    elif item1[price] == item2[price]:
        return 0
    else:
        return 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function compareByPrice($item1, $item2)
{
    if ($item1['price'] < $item2['price']) {
        return -1;
    } else if ($item1['price'] == $item2['price']) {
        return 0;
    } else {
        return 1;
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByPrice = (item1, item2) -> {
        var price1 = (int) item1.get("price");
        var price2 = (int) item2.get("price");

        if (price1 < price2) {
            return -1;
        } else if (price1 == price2) {
            return 0;
        } else {
            return 1;
        }
};
</code>
</details>

А вот так — компаратор, сравнивающий элементы по рейтингу:

<code javascript>
const compareByRating = (item1, item2) => {
  if (item1.rating < item2.rating) {
    return -1;
  } else if (item1.rating == item2.rating) {
    return 0;
  } else {
    return 1;
  }
};
</code>

<details>
<summary>Python</summary>

<code python>
def compare_by_rating(item1, item2):
    if item1[rating] < item2[rating]:
        return -1
    elif item1[rating] == item2[rating]:
        return 0
    else:
        return 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function compareByRating($item1, $item2)
{
    if ($item1['rating'] < $item2['rating']) {
        return -1;
    } else if ($item1['rating'] == $item2['rating']) {
        return 0;
    } else {
        return 1;
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
public static ToIntBiFunction<Map<String, Object>, Map<String, Object>> compareByRating = (item1, item2) -> {
        var rating1 = (double) item1.get("rating");
        var rating2 = (double) item2.get("rating");

        if (rating1 < rating2) {
            return -1;
        } else if (rating1 == rating2) {
            return 0;
        } else {
            return 1;
        }
};
</code>
</details>

Универсальная функция сравнивает два элемента, но не использует операторы «больше» или «меньше». Вместо этого она вызывает компаратор и проверяет результат. Так выглядит универсальная пузырьковая сортировка:

<code javascript>
const bubbleSort = (items, comparator) => {
  for (let limit = items.length - 1; limit > 0; limit -= 1) {
    for (let i = 0; i < limit; i += 1) {
      if (comparator(items[i], items[i + 1]) > 0) {
        const temporary = items[i];
        items[i] = items[i + 1];
        items[i + 1] = temporary;
      }
    }
  }
};
</code>
</details>

<details>
<summary>Python</summary>

<code python>
def bubble_sort(items, comparator):
    for limit in range(len(items) - 1, 0, -1):
        for i in range(limit):
            if comparator(items[i], items[i + 1]) > 0:
                items[i], items[i + 1] = items[i + 1], items[i]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function bubbleSort($items, $comparator)
{
    for ($limit = count(items) - 1; $limit > 0; $limit -= 1) {
        for ($i = 0; $i < $limit; $i += 1) {
            if (comparator($items[$i], $items[$i + 1]) > 0) {
                $temporary = $items[$i];
                $items[$i] = $items[$i + 1];
                $items[$i + 1] = $temporary;
            }
        }
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {
    public static void bubbleSort(Map[] items, ToIntBiFunction comparator) {
        for (var limit = items.length - 1; limit > 0; limit--) {
            for (var i = 0; i < limit; i++) {
                if (comparator.applyAsInt(items[i], items[i + 1]) > 0) {
                    var temporary = items[i];
                    items[i] = items[i + 1];
                    items[i + 1] = temporary;
                }
            }
        }
    }
}
</code>
Инструменты пользователя

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

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