Как найти массив по убыванию

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

• По убыванию цены, если готовы на дорогую покупку

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

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

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

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;
      }
    }
  }
};

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]

<?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;
            }
        }
    }
}

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;
                }
            }
        }
    }
}

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

for limit in range(len(items) - 1, 0, -1):
    # ...

<?php

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

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

const temporary = items[i];
items[i] = items[i + 1];
items[i + 1] = temporary;

# В Python временная переменная не требуется
items[i], items[i + 1] = items[i + 1], items[i]

<?php

$temporary = $items[$i];
$items[$i] = $items[$i + 1];
$items[$i + 1] = $temporary;

var temporary = items[i];
items[i] = items[i + 1];
items[i + 1] = temporary;

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]

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]

<?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]

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]

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;
  }
};

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]

<?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;
    }
}

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;
        }
    }
}

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;
}

left = 0
right = len(items) - 1

while left < right:
    items[left], items[right] = items[right], items[left]
    left += 1
    right -= 1

<?php

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

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

    $left += 1;
    $right -= 1;
}

var left = 0;
var right = items.length - 1;

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

  left++;
  right--;
}

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

# В Python временная переменная не требуется
items[left], items[right] = items[right], items[left]

<?php

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

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

<?php

$left += 1;
$right -= 1;

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

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

В качестве опорного элемента выбрано число 4. Левый указатель смотрит на 5, а правый — на 3.

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

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

Ищем следующую пару для обмена. Справа от 3 находится 4 — наш следующий кандидат для обмена. Обратите внимание, что 4 — опорный элемент, но он тоже принимает участие в сравнениях и обменах.

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

Меняем их местами и ищем следующую пару. Следующие кандидаты — числа 10 и 1:

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

Продолжаем частичное упорядочивание левой и правой половин массива. Правая половина перед упорядочиванием показана на рисунке:

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

Левый и правый указатель встречаются посередине — на числе 7. Мы снова разбиваем массив на две половины и переходим к упорядочиванию левой и правой половин.

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

Попробуем реализовать алгоритм на 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;
  }
};

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

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;
    }
}

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--;
        }
    }
}

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

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

while (items[left] < pivot) {
  left += 1;
}

Python

while items[left] < pivot:
    left += 1

PHP

<?php

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

Java

while (items[left] < pivot) {
    left++;
}

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

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

Python

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

PHP

<?php

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

Java

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

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

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

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

Python

if left >= right:
    return right + 1

PHP

<?php

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

Java

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

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

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

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

left += 1;
right -= 1;

Python

items[left], items[right] = items[right], items[left]
left += 1
right -= 1

PHP

<?php

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

$left += 1;
$right -= 1;

Java

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

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

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

while (true) {
  // ...

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

  // ...
}

Python

while True:
    # ...

    if left >= right:
        return right + 1

    # ...

PHP

<?php

while (true) {
    // ...

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

    // ...
}

Java

while (true) {
    // ...

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

    // ...
}

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

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

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);
};

Python

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)

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);
}

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);
    }
}

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

const length = right - left + 1;

if (length < 2) {
  return;
}

Python

length = right - left + 1

if length < 2:
    return

PHP

<?php

$length = $right - $left + 1;

if ($length < 2) {
    return;
}

Java

var length = right - left + 1;

if (length < 2) {
    return;
}

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

const splitIndex = partition(items, left, right, pivot);
sort(items, left, splitIndex - 1);
sort(items, splitIndex, right);

Python

split_index = partition(items, left, right, pivot)
sort(items, left, split_index - 1)
sort(items, split_index, right)

PHP

<?php

$splitIndex = partition($items, $left, $right, $pivot);
sort($items, $left, $splitIndex - 1);
sort($items, $splitIndex, $right);

Java

var splitIndex = partition(items, left, right, pivot);
sort(items, left, splitIndex - 1);
sort(items, splitIndex, right);

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

const pivot = items[left];

Python

PHP

<?php

$pivot = $items[$left];

Java

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

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

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

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

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

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

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 ]

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]

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 ]

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 ]

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

• Название — name

• Цена — price

• Рейтинг — rating

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 },
];

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},
]

<?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],
];

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)
};

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

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

<?php

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

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;
        }
};

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

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

<?php

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

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;
        }
};

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;
      }
    }
  }
};

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]

<?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;
            }
        }
    }
}

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;
                }
            }
        }
    }
}