Простые типы алгоритмов сортировки

  1. Пузырьковая сортировка ➝ O(n²)
  2. Сортировка вставками➝ O(n²)
  3. Сортировка выбором ➝ O (n²)
  4. Сортировка слиянием ➝ O (n * log n)
  5. Быстрая сортировка ➝ среднее: O(n * log n), наихудшее: O(n²)

Что такое сортировка вставками? Вот короткое видео, иллюстрирующее процесс.

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

Сложность в наихудшем случае: O(n²)

Сложность пространства в наихудшем случае: O(1), если выполняется сортировка по месту.

Основные шаги для реализации сортировки вставками в списке, скажем, [5, 4, 3, 2, 1]:

  1. Начните слева и двигайтесь до конца справа

2. Сравните текущий элемент с элементом слева от него.

3. Если текущий элемент меньше, поменять местами его с левым

4. Продолжайте сравнивать и менять местами влево, пока текущий элемент не окажется на своем месте.

5. Как только он окажется в нужном месте, перейдите к следующему элементу. В нашем текущем примере перейдите ко второму индексу, который равен 3.

6. Затем снова продолжите сравнение и замену. Продолжайте, пока все элементы не будут отсортированы

Вот код на JavaScript:

const insertionSort = (array) => { 
    // we start at index 1 because we know the first element
    // is already sorted
    for (let i = 1; i < array.length; i++) {
        // initialize left and right indices and elements
        let rightIdx = i
        let right = array[rightIdx]
        
        let leftIdx = rightIdx - 1
        let left = array[leftIdx]
        
        // if not at the beginning and left is greater than right
        while (leftIdx >= 0 && (left > right)) {
            // move the element to the left by
            // swapping the left and right elements
            swap(array, leftIdx, rightIdx)
            // move pointers to the left, so left
            // and right elements are repositioned
            leftIdx--
            rightIdx--
            left = array[leftIdx]
            right = array[rightIdx]
        }
    }
    return array
}
const swap = (array, left, right) => {
    let temp = array[right]
    array[right] = array[left]
    array[left] = temp
}
console.log(insertionSort([3, 2, 1])) // [1, 2, 3]

Сложность в наихудшем случае: O(n²)

Сложность пространства в наихудшем случае: O(1), если выполняется сортировка по месту.

Когда использовать сортировку вставками?

  1. Когда количество элементов невелико
  2. Это также может быть полезно, когда входной массив почти отсортирован, например, когда элементы неуместны в большом массиве.

Пример проблемы:

Отсортируйте полуотсортированный массив, в котором несортированные элементы находятся на k мест от его правильной позиции сортировки.

inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 12, 9, 10, 11], k = 3

Единственный элемент, который не отсортирован, — это значение 12 в индексе 8, которое должно быть в индексе 11.