Я сделал это! В прошлом месяце я окончила программу иммерсивной инженерии программного обеспечения Flatiron School. Ура! Теперь, когда время прошло, пора сосредоточиться на поиске работы. Вместе с поиском работы идут собеседования, которые носят как технический, так и нетехнический характер. По этой причине я решил посвятить несколько следующих моих блогов структурам данных и алгоритмам. Хотя мы кратко познакомились с этим во Flatiron, мы не практиковались в этом слишком много. Поэтому я решил писать о них в блогах.

Во-первых, алгоритмы сортировки (в Javascript)!

Что такое алгоритм сортировки? Почему это важно?

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

Общие алгоритмы сортировки

Вот некоторые из наиболее распространенных алгоритмов сортировки:

  1. Выбор Сортировка
  2. Пузырьковая сортировка
  3. Вставка сортировки
  4. Сортировка кучи
  5. Быстрая сортировка
  6. Сортировка слиянием

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

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

Выбор Сортировка

Этот метод сортирует массив в порядке возрастания, многократно выбирая минимальный элемент и помещая его в начало. Есть разные способы реализовать этот метод, но один из них - это работа с двумя подмассивами в исходном массиве, одна часть - это отсортированный раздел, а оставшаяся - несортированный раздел. Преимущество этого заключается в том, что он не использует слишком много памяти, поскольку делает только один своп за раз. Однако недостатком является то, что он использует вложенные циклы, что приводит к временной сложности O (n²). Просмотрите код ниже:

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

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

Вставка сортировки

Этот метод можно сравнить с сортировкой колоды карт в руке. Эта сортировка также имеет дело с двумя подмассивами в исходном массиве, отсортированным подмассивом и несортированным массивом. После каждой итерации значения из несортированного массива перемещаются в отсортированный массив и вставляются в правильную позицию отсортированного массива. В этом методе также используется вложенный цикл, что усложняет его выполнение. Однако этот метод сортировки обычно используется, когда количество элементов невелико или когда только несколько элементов неуместны в большом массиве. Примечание. V8 Engine Chrome использует этот тип сортировки для своих .sort (). Просмотрите код ниже:

В следующем блоге я рассмотрю некоторые из более быстрых методов сортировки, такие как сортировка слиянием! Удачной сортировки!

Ресурсы:

  1. Объяснение алгоритмов сортировки, FreeCodeCamp, по состоянию на 15 октября 2020 г., https://www.freecodecamp.org/news/sorting-algorithms-explained/
  2. JS: Sorting Algorithms, по состоянию на 15 октября 2020 г., https://khan4019.github.io/front-end-Interview-Questions/sort.html
  3. Временные сложности всех алгоритмов сортировки, GeeksForGeeks, по состоянию на 15 октября 2020 г., https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
  4. Selection Sort, GeekForGeeks, по состоянию на 16 октября 2020 г., https://www.geeksforgeeks.org/selection-sort/
  5. Bubble Sort, GeekForGeeks, по состоянию на 16 октября 2020 г., https://www.geeksforgeeks.org/bubble-sort/
  6. Сортировка вставкой, GeekForGeeks, по состоянию на 16 октября 2020 г., https://www.geeksforgeeks.org/insertion-sort/