Что такое сортировка вставкой?

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

Как это работает?

Начните с создания доступной переменной с именем temp.

function insertionSort(array){ 
    let temp;
}

Итерируйте по массиву, начиная с индекса 1. Внутри этой первой итерации установите temp равным текущему индексу массива.

function insertionSort(array){
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
    }
}

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

Мы начнем со второй итерации, которая состоит из начала с индекса до нашего первого индекса первой итерации. Кроме того, мы добавим условие, если индекс перед текущим массивом больше, чем фактический текущий массив. Это будет выглядеть примерно так.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
  
       }
    }
}

В этом конкретном цикле есть важный трюк, который упускается из виду. Индекс j должен быть больше -1. Это реализовано, потому что, если цикл непрерывно сравнивает и сортирует порядок элементов, он в конечном итоге выйдет за пределы индекса от 0 до -1. Поэтому мы добавили условие, что индекс j должен быть больше -1.

После того, как вторая итерация будет установлена ​​и условия будут выполнены, мы переместим индекс j на 1 вместо temp.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
                array[j + 1] = array[j]
            }
     }
}

Затем мы выйдем из цикла for и поместим temp в открытое место. Как только все пройдет проверку, мы вернем массив.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
                array[j + 1] = array[j]
            }
array[j + 1] = temp
        }
    
    return array
}

Вот полный взгляд на решение ниже. Надеюсь, вам понравилось до следующего раза.

function insertionSort(array){
    
    let temp;
for(let i = 1; i < array.length; i++){
            temp = array[i]
for(var j = i-1; array[j] > temp && j <-1; j--){
                array[j + 1] = array[j]
            }
array[j + 1] = temp
        }
    
    return array
}
let myInsertion = [1,2,4,3,5,6]
console.log('insertionSort', insertionSort(myInsertion))