Как сделать сортировку по возрастанию в с

Обновлено: 05.07.2024

Сортировка — один из базовых видов активности или действий, выполняемых над предметами. Ещё в детсве детей учат сортировать, развивая мышление. Компьютеры и программы — тоже не исключение. Существует огромное множество алгоритмов. Предлагаю посмотреть, какие есть и как они работают. Кроме того, вдруг однажды вас спросят об одном из них на собеседовании?

Вступление

Сортировка элементов — одна из категорий алгоритмов, к которым разработчик должен привыкнуть. Если когда-то, когда я учился, информатика не воспринималась так серьёзно, сейчас уже в школе должны уметь реализовывать алгоритмы сортировки и понимать их. Базовые алгоритмы, самые простые, реализованы при помощи цикла for . Естественно, чтобы отсортировать коллекцию элементов,например, массив, нужно по этой коллекции как-то пройти. Например: Что можно сказать об этом участке кода? Мы имеем цикл, в котором меняем значение индекса ( int i ) с 0 до последнего элемента в массиве. Фактически, мы просто берём каждый элемент в массиве и печатаем его содержимое. Чем больше элементов в массиве, тем дольше будет выполняться код. То есть, если n — количество элементов, при n=10 программа будет выполняться дольше, чем при n=5, в 2 раза. Когда в нашей программе есть один цикл, время выполнения растёт линейно: чем больше элементов, тем дольше выполнение. Получается, что алгоритм кода выше работает за линейное время (n). В таких случаях говорят, что "сложность алгоритма" равна O(n). Это обозначение ещё называют "большое О" или "асимптотическое поведение". Но можно запомнить просто "сложность алгоритма". Тут настоятельно советую прочитать суперстатью на Хабре: "Введение в анализ сложности алгоритмов (часть 1)".


В этой статье вы узнаете как делать сортировку в JavaScript при помощи метода sort() , не только обычную, как предполагает этот метод, а с задаваемыми параметрами и в самом конце вы узнаете как сортировать объекты, вложенные в массив по различным критериям.

Сортировка массивов в JavaScript делается через метод array.sort() , этот метод возможно также недооценен, как и неверно многими понимаем. Во время вызова sort() , сам по себе он сортирует массив в алфавитном порядке, но не всё так просто, если попытаться зайти дальше. Давайте более детально посмотрим на работу этого метода.

Сортировка массива в алфавитном порядке

Выполнить такую сортировку довольно просто. Просто вызовите array.sort() без любых параметров:

Обратите внимание на возрастающий порядок. Чтобы сделать его убывающим, то самым простым способом тут будет применение другого метода для массивов в комбинации с sort() — это reverse() .

А теперь, перед тем, чтобы расслабиться, посмотрите на то, что случится когда мы вызовем array.sort() на массиве из чисел:

Хотя 7 в численном порядке меньше, чем 40 или 300, в лексикографическом порядке, семёрка больше, таким образом она оказывается в правее всех в отсортированном массиве. Всегда имейте в виду, что по-дефолту array.sort() сортирует элементы в лексикографическом порядке.

Итак, мы узнали то, что нужно знать для простого использования этого метода. Но существует куда больше, связанного с ним, чем может показаться с первого взгляда. Array.sort() допускает дополнительные параметры в виде функций, которые очень сильно могут помочь в сортировке массива, основываясь на любом заданном критерии, таком как сортировке массива в числовом порядке или перемешанная сортировка.

Передаём функцию в array.sort()

Как говорилось выше, array.sort() допускает дополнительные параметры в виде функций (давайте назовем её sortfunction ). Формат такой функции будет выглядеть таким образом:

Когда такая функция передаётся в array.sort() , элементы массива сортируются, основываясь на взаимосвязи между каждой парой элементов a и b и значением, отдаваемым функцией. Есть три возможных числа, которые отдадутся функцией: 0 (больше нуля).

В первом случае, когда меньше нуля, a отсортируется с индексом меньшими, чем b .

При нуле: a и b будут рассматриваться как равные и сортировка производиться не будет.

Больше нуля: Сортировка b будет меньшего индекса, чем a .

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

Чтобы отсортировать массив в числовом порядке, просто передайте sortfunction к array.sort() , а затем возвратите разницу между a и b , оба параметра автоматически отправятся в функцию:

Это работает так, как и должно работать, так как всякий раз когда a меньше, чем b , возвращается негативное значение, что ведет к тому, что меньший элемент всегда будет выставляться левее большего, а другими словами, порядок будет выстроен по возрастанию. Обратите внимание на то, что мы определили нашу функцию сортировки прямо внутри sort() , как анонимную, вместо того, чтобы создавать отдельную функцию и передавать ещё в sort() — оба варианта выдадут одинаковый результат.

Сортировка массива в числовом порядке, но по убывающей, отличается не многим и всего лишь требует реверса двух операндов a и b :

Делаем случайный порядок у массива

Чтобы перетасовать элементы в массиве нам нужно, чтобы sortfunction возвращал 0 рандомно, независимо от того, что выдаст a и b. Вот небольшой трюк с этим делом:

Как вы видите у array.sort() есть тайные стороны. На самом деле, вы даже можете сортировать массивы, которые содержат не только примитивы, а объекты со свойствами. Давайте рассмотрим этот вариант:

Сейчас мы пойдем дальше и предположим, что ваш массив содержит не только простые численные или строковые значения, а вместо них объекты со свойствами:

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

Сортировка по возрасту

Итак, давайте начнем сортировать наш массив employees по возрасту сотрудников в возрастающем порядке. Вот функция сравнения, которая это сделает:

С методом сортировки, указанным выше, наш массив теперь сортируется по свойству age (т.е. возраст). И таким образом, теперь у нас employee[0] это Edward, а employee[1] это George. Этот процесс очень похож на сортировку массива с числовыми значениями по возрастающей, но тут вместо вычета простого b из a , нам надо вычесть b.age из a.age , или иными словами свойство элемента, который мы хотим отсортировать.

Сортировка по имени

В наши дни сортировка по возрасту сотрудника может выглядеть довольно бесчувственной и некорректной, так что давайте отсортируем по именам сотрудников в возрастающем порядке. Вспомните, что по-дефолту, сортировка массива, который содержит примитивы, такие как строки, происходит в алфавитном порядке. Что говорит о том, что вам просто надо вызвать sort() метод, без любой функции сравнения, в общем просто myarray.sort() . Это не работает, так как данные по которым мы хотим отсортировать не являются массивом. Так что же делать? Фокус тут в том, чтобы вручную написать функцию сравнения, которая отсортирует массив по-алфавиту, что в свою очередь даст нам указать где находятся данные строк. Давайте посмотрим:

Это отсортирует массив employees по именам в возрастающем порядке, так что теперь employee[0] это Christine, employee[1] это Edward и так далее. Тут мы сравниваем две строки a.name с b.name и возвращаем -1, 1 или 0, в соответствии с сортировкой, точно определенной формулой, которую использует сам sort() , без передачи какой-либо другой функции. Как вы уже наверное выяснили, в JavaScript вы можете без сомнений сравнивать две строки.

Сортировка по дате

И наконец, предположим, что вам нужно отсортировать сотрудников по их дате выхода на пенсию. Эта информация хранится в свойстве retiredate и чтобы сделать всё интереснее, это будет не объект с датой, а просто строка. Что нам нужно сделать первым делом, так это создать валидный объект даты из строки даты выхода на пенсию, хоть впоследствии процесс и будет таким же, как и сортировка по числам:

Это отсортирует массив таким образом, что работник, выходящий на пенсию раньше всех, появится первым. employees[0] теперь будет Sarah. Это сработает, потому что JavaScript даст вам сравнить и/или сделать арифметические вычисления на объекте даты, который в первую очередь автоматически сконвертируется в числовой вид.

Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.

Виды алгоритмов сортировки

Сортировка пузырьком / Bubble sort

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

Сортировка пузырьком, пример

Плюсы и минусы

Пример реализации на Kotlin:

Сортировка перемешиванием / Shaker (cocktail, ripple, shuffle, shuttle) sort

Также известна как шейкерная или коктейльная сортировка.

Сортировка перемешиванием - это разновидность сортировки пузырьком. Отличие в том, что данная сортировка в рамках одной итерации проходит по массиву в обоих направлениях (слева направо и справа налево), тогда как сортировка пузырьком - только в одном направлении (слева направо).

Общая идея алгоритма:

  • Обход массива слева направо, аналогично пузырьковой - сравнение соседних элементов, меняя их местами, если левое значение больше правого. В итоге наибольшее число будет перемещено в конец массива.
  • Обход массива в обратном направлении (справа налево), начиная с элемента, который находится перед последним отсортированным. На этом этапе элементы также сравниваются между собой и меняются местами, чтобы наименьшее значение всегда было слева. В итоге наименьшее число будет перемещено в начало массива.

Пример реализации на Kotlin:

Сложность у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше (обычно менее чем в два раза быстрее).

Сортировка расчёской / Comb sort

Сортировка расчёской - еще одна разновидность сортировки пузырьком. Данная сортировка улучшает сортировку пузырьком за счет устранения маленьких значений в конце списка (черепах).

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

Оптимальное значение фактора уменьшения - 1,247.

Пример реализации на Kotlin:

Сортировка вставками / Insertion sort

Сортировка вставками - алгоритм, при котором каждый последующий элемент массива сравнивается с предыдущими элементами (отсортированными) и вставляется в нужную позицию.

Общая идея алгоритма:

  • Сравниваем второй элемент с первым элементом массива и при необходимости меняем их местами. Условно эти элементы (первый и второй) будут являться отсортированным массивом, остальные элементы - неотсортированным.
  • Сравниваем следующий элемент из неотсортированного массива с элементами отсортированного и вставляем в нужную позицию.
  • Повторям шаг 2 до тех пор, пока в неотсортированном массиве не останется элементов.

Пример реализации на Kotlin:

Сортировка Шелла / Shell sort

Сортировка Шелла - усовершенствованная разновидность сортировки вставками.

Сначала сравниваются и сортируются между собой значения, стоящие друг от друга на некотором расстоянии - d. После этого расстояние d уменьшается и процедура повторяется до тех пор, пока значение d не станет минимальным, т.е. d = 1. Это означает, что сортировка достигла последнего шага. А на последнем шага элементы сортируются обычной сортировкой вставками.

Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:

  • первая итерация - d1 = N/2, где N - размер массива;
  • последующие итерации - di = di-1/2;
  • последняя итерация - dk = 1

Существуют и другие последовательности.

Пример реализации на Kotlin:

Сортировка выбором / Selection Sort

Сортировка выбором - это алгоритм, при котором многократно осуществляется поиск минимального элемента в неотсортированной части массива и его помещение в конец отсортированной части массива.

Общая идея алгоритма:

  • Данный алгоритм условно делит массив на две части:
    • подмассив, который уже отсортирован (находится в левой части массива),
    • подмассив, который нужно отсортировать (находится в правой части массива).

    Пример реализации на Kotlin:

    Быстрая сортировка / Quick Sort

    Быстрая сортировка - это алгоритм типа “разделяй и властвуй”.

    Общая идея алгоритма:

    Пример реализации на Kotlin:

    Сортировка слиянием / Merge sort

    Сортировка слиянием - это алгоритм типа “разделяй и властвуй”.

    Общая идея алгоритма:

    • Массив разбивается на две части примерно одинакового размера. Разбиение получившихся массивов повторяется до тех пор, пока размер каждого массива не достигнет единицы.
    • Каждая из получившихся частей сортируется отдельно, после чего происходит слияние двух массивов следующим образом:
      • На каждом шаге сравниваем первые элементы массивов, берём наименьшее значение и записываем в результирующий массив.
      • Когда один из массив закончился, добавляем оставшиеся элементы второго массива в результирующий массив.

      Пример реализации на Kotlin:

      Пирамидальная сортировка / Heap sort

      Пирамидальная сортировка - это улучшенная сортировка выбором.

      Для сортировки используется бинарное сортирующее дерево - дерево, у которого выполнены условия:

      • Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
      • Значение в любой вершине не меньше значения её потомков.

      сортирующее дерево

      Общая идея алгоритма:

      Сортировка подсчётом / Counting sort

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

      Общая идея алгоритма (простой вариант):

      • Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями.
      • Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C - это значения массива A, а значение в массиве C - это то, сколько раз это число повторяется в массиве A.
      • Проходим по массиву C и переносим значения в массив A.

      Пример реализации на Kotlin:

      • n - размер отсортированного массива, а k - размер вспомогательного массива

      Блочная (карманная, корзинная) сортировка / Bucket sort

      Блочная сортировка - это алгоритм, основанный на разделении входного массива на несколько частей - блоки/сегменты - и использовании другого алгоритма для их сортировки.

      Общая идея алгоритма:

      • Делим массив на блоки таким образом, чтобы элементы в каждом следующем блоке были всегда больше, чем в предыдущем.
      • Сортируем каждый блок, используя какой-либо другой алгоритм сортировки, либо рекурсивно тем же методом разбиения на блоки.
      • Объединяем все блоки в один массив.

      Пример реализации на Kotlin:

      Поразрядная (цифровая) сортировка / Radix sort

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

      Перед началом сортировки необходимо знать:

      • length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове);
      • rang количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).

      Общая идея алгоритма:

      • Создаём пустые массивы, количество которых равно rang.
      • Распределяем исходные значения по этим массивам. Распределение осуществляется по значению младшего (крайнего) разряда.
      • Соединяем значения в той последовательности, в которой они находятся после распределения по спискам.
      • Повторяем шаги 1-2 для оставшихся разрядов.

      Пример реализации на Kotlin:

      • w - количество бит, требуемых для хранения каждого ключа.

      Битонная сортировка / Bitonic sort

      Битонная сортировка - алгоритм, основанный на понятии битонных последовательностей и операций над ними.

      Битонная последовательность - последовательность, которая сначала возрастает, а потом убывает.

      Общая идея алгоритма:

      • Создаём битонную последовательность. В результате получаем два массива: первый отсортирован в порядке возрастания, второй - в порядке убывания.
      • Последовательно сравниваем элементы первого и второго массивов (сначала первые элементы, потом вторые и т.д.). Если какой либо элемент из второго массива окажется меньше, то меняем его местами с элементом из первого массива. В результате в первом массиве окажутся наименьшие элементы из обоих массивов, а во втором - наибольшие. При этом каждый из массивов будет являться битонной последовательностью.
      • Рекурсивно применяем второй шаг к отсортированным массивам, после чего массивы можно склеить.

      Битонная сортировка

      Чтобы превратить произвольную последовательность в битонную, нужно:

      • разделить последовательность пополам;
      • первую часть отсортировать по возрастанию;
      • вторую часть отсортировать по убыванию.

      Пример реализации на Kotlin:

      Timsort

      Timsort - гибридный алгоритм, сочетающий в себе сортировку вставками и сортировку слиянием.

      Если вам нужно отсортировать список, то к вашим услугам куча способов, самый простой из которых - кнопки сортировки на вкладке или в меню Данные (Data - Sort) . Бывают, однако, ситуации, когда сортировку списка нужно делать автоматически, т.е. формулами. Такое может потребоваться, например, при формировании данных для выпадающего списка, при вычислении данных для диаграмм и т.д. Как же "на лету" сортировать список формулой?

      Способ 1. Числовые данные

      Если список содержит только числовую информацию, то его сортировку можно легко сделать с помощью функций НАИМЕНЬШИЙ (SMALL) и СТРОКА (ROW) :

      Функция НАИМЕНЬШИЙ (SMALL) выдергивает из массива (столбец А) n-й по счету наименьший элемент. Т.е. НАИМЕНЬШИЙ(A:A;1) - это самое маленькое число из столбца, НАИМЕНЬШИЙ(А:А;2) - второе по счету наименьшее и т.д.

      Функция СТРОКА (ROW) выдает порядковый номер строки для указанной ячейки, т.е. СТРОКА(А1)=1, СТРОКА(A2)=2 и т.д. В данном случае она используется просто как генератор последовательности чисел n=1,2,3… для нашего отсортированного списка. С тем же успехом можно было сделать дополнительный столбец, заполнить его вручную числовой последовательностью 1,2,3… и ссылаться на него вместо функции СТРОКА.

      Способ 2. Текстовый список и обычные формулы

      Если в списке не числа, а текст, то функция НАИМЕНЬШИЙ (SMALL) уже не сработает, поэтому придется пойти другим, чуть более длинным, путем.

      Сначала добавим служебный столбец с формулой, где будет вычисляться порядковый номер каждого имени в будущем отсортированном списке с помощью функции СЧЁТЕСЛИ (COUNTIF) :

      В английской версии это будет:

      =COUNTIF(A:A," (SMALL) из первого способа:

      Ну, и наконец, осталось просто вытащить из списка имена по их номерам. Для этого можно использовать такую формулу:

      Функция ПОИСКПОЗ (MATCH) ищет в столбце В нужный порядковый номер (1, 2, 3 и т.д.) и выдает, по сути, номер строки, где находится это число. Функция ИНДЕКС (INDEX) вытаскивает из столбца А имя по этому номеру строки.

      Способ 3. Формула массива

      Этот способ представляет собой, по сути, тот же алгоритм расстановки, что и в Cпособе-2, но реализованный формулой массива. Для упрощения формулы диапазону ячеек С1:С10 было дано имя List (выделить ячейки, нажать Ctrl+F3 и кнопку Создать):

      В ячейку Е1 копируем нашу формулу:

      =ИНДЕКС(List; ПОИСКПОЗ(НАИМЕНЬШИЙ(СЧЁТЕСЛИ(List; " Или в англоязычной версии:

      и нажимаем Ctrl+Shift+Enter, чтобы ввести ее как формулу массива. Потом полученную формулу можно скопировать вниз на всю длину списка.

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

      Во-первых, диапазон List нужно будет задать динамически. Для этого при создании нужно указать не фиксированный диапазон C3:C10, а специальную формулу, которая будет ссылаться на все имеющиеся значения независимо от их количества. Нажмите Alt+F3 или откройте вкладку Формулы - Диспетчер имен (Formulas - Name Manager) , создайте новое имя и в поле Ссылка (Reference) впишите вот такую формулу (я предполагаю, что диапазон сортируемых данных начинается с ячейки C1):

      = ЕСЛИОШИБКА( ИНДЕКС(List; ПОИСКПОЗ(НАИМЕНЬШИЙ(СЧЁТЕСЛИ(List; " ;"")

      Читайте также: