Организуйте свои данные для более быстрого поиска и повышения эффективности других вычислений.
Сортировка информации чрезвычайно важна из-за огромных преимуществ, которые она предлагает. Когда данные организованы осмысленным образом, получение информации и выполнение других вычислений становятся более быстрыми и эффективными. Сортировка - такая популярная тема, что метод сортировки встроен во многие языки программирования. Это также хорошо изученная тема, о чем свидетельствует разнообразие доступных подходов. Типы сортировки включают пузырь, выделение, вставку, слияние, быструю, кучу, основание, подсчет и, конечно же, некоторые другие.
Для сортировки небольших и простых наборов данных встроенный метод, вероятно, будет работать нормально. Например, вот успешно отсортированный массив строк, состоящий всего из одной буквы, с использованием встроенного метода сортировки Javascript:
const letters = ['a', 'd', 'z', 'e', 'r', 'b']; letters.sort(); --> ['a', 'b', 'd', 'e', 'r', 'z']
С этим нет проблем, но что, если у нас есть массив чисел, который мы хотели бы отсортировать? Кажется достаточно простым:
const basket = [2, 65, 34, 2, 1, 7, 8]; basket.sort(); --> [1, 2, 2, 34, 65, 7, 8]
О нет, не похоже, что он отсортирован правильно ... с каких это пор 65 меньше 7? Это отличный пример того, почему встроенный метод сортировки в Javascript не всегда дает ожидаемые результаты. Очевидно, мы ожидали увидеть 34 и 65 после 7 и 8, так почему метод сортировки вернул это? Чтобы понять это, нам нужно заглянуть под капот в Javascript .sort ().
Чтобы понять, почему вызов встроенного метода сортировки для массива чисел может не дать желаемых результатов, нам нужно точно понимать, как Javascript сортирует этот набор значений. В Javascript встроенный метод сортировки преобразует числа в строки и сравнивает первый символьный код / юникод каждого элемента. При сортировке всего одной буквы ничего неожиданного не происходит. Однако все усложняется, когда числа больше 9. Вот сравнение кодов символов a и b:
'a'.charCodeAt(0) --> 97 'b'.charCodeAt(0) --> 98
Но если мы сравним первые коды символов 65 и 7:
'65'.charCodeAt(0) --> 54 '7'.charCodeAt(0) --> 55
Ага! 54 стоит перед 55, поэтому 65 было помещено перед 7 в отсортированном массиве. Таким образом, похоже, что встроенный в Javascript метод сортировки может быть не лучшим для сортировки чисел больше 9. Чтобы правильно отсортировать массив чисел, нам нужно будет создать нашу собственную функцию и передать ее в качестве аргумента при вызове .sort ():
const basket = [2, 65, 34, 2, 1, 7, 8];
basket.sort(function(a, b){
return a - b;
});
--> [1, 2, 2, 7, 8 34, 65]
Пользовательская функция также полезна при сортировке группы строк, содержащих символы с диакритическими знаками:
const spanish = ['único', 'árbol', 'fútbol', 'cosas']
spanish.sort(function(a, b){
return a.localeCompare(b)
});
--> ['árbol', 'cosas', 'fútbol', 'único']
При создании собственных алгоритмов сортировки следует рассмотреть возможность использования множества различных типов. Вариантов может быть множество, но становится намного проще, если вы знаете преимущества использования одного типа над другим. Типы, о которых я расскажу, обычно считаются наиболее популярными: пузырь, выделение, слияние и быстрое.
Пузырьковая сортировка и сортировка по выбору обычно являются первыми типами, которые знакомят новичков при изучении сортировки из-за их простоты и сходства. Пузырьковая сортировка использует технику всплывания и замены элементов рядом друг с другом до тех пор, пока не будет отсортирован полный список. Сортировка по выбору выбирает наименьший элемент и делает его первым (или последовательным) элементом в списке. Оба типа сортировки имеют временную сложность O (n²) - что чертовски медленно, а пространственную сложность - O (1) - лучшее, что вы можете сделать с точки зрения памяти.
Временная сложность O (n²) не очень эффективна. Чтобы улучшить это измерение, следует использовать такие типы сортировки, как «Слияние» и «Быстрая сортировка», в которых используется метод «разделяй и властвуй». Их временная сложность обычно составляет O (n log n), а их пространственная сложность - O (n). Слияние - наиболее эффективный подход к сортировке данных, но он также является наиболее сложным, поскольку использует рекурсию. Хотя мы должны сравнить каждый элемент один раз, нам нужно сравнить только локальные списки (а не сравнивать все со всем). Список разделяется, переупорядочивается, а затем он объединяется снова.
Быстрая сортировка также использует метод «разделяй и властвуй» вместе с техникой поворота. В среднем это самый быстрый метод сортировки с временной сложностью O (n log n). Несмотря на название Quick, он рискует стать чрезвычайно медленным с временной сложностью O (n²), если наихудший сценарий окажется верным. Этот подход выбирает элемент в качестве назначенного значения поворота и выполняет итерацию по списку, ища элементы меньшего значения для размещения в начале списка или в последовательном порядке. В худшем случае стержнем будет самый маленький или самый большой элемент. Это означает, что каждый элемент будет сравниваться с осью, что отнимает очень много времени.
При сортировке данных может возникнуть соблазн реализовать метод Bubble или Selection из-за простоты, но в большинстве случаев есть более быстрый способ. Чтобы превзойти время O (n²) Пузыря и Выделения, разумно воспользоваться преимуществами методов, в которых используются методы разделения и владения, такие как Слияние и Быстрая сортировка. Хотя Quick обычно более эффективен по времени, чем Merge, если вы выберете «плохой» элемент сводки (то есть самое высокое или самое низкое значение), вы рискуете сделать быструю сортировку очень медленной. Тщательно выбирайте подход и удачи в сортировке!
