Время выполнения алгоритмов Hackkerrank проблема сортировки вставки

Question

Задача - вывести количество смен, которое требуется для сортировки массива. мой код:

function runningTime(arr) {
    var count=0;
    var temp;
    for(var i=1 ; i<arr.length; i++){
        for(var j=0 ; j<i; j++){
            if(arr[j]>arr[i]){
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                count++;
            }
        }
    }
    return count;

}

console.log(runningTime([4, 4, 3, 4]));

не проходит этот образец теста: 4 4 3 4. ожидаемый результат равен 2, а мой возвращает 1, почему он должен возвращать 2? а где я не прав?

вот ссылка на проблему: вставка сортировки, проблема хакерранка

Answer 1

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

function runningTime(arr) {
    var count = 0;
    var temp;
    for (var i = 0; i < arr.length; i++) {
        let pos = i;
        for (var j = i; j >= 0; j--) {
        if (arr[j] > arr[i]) {
            pos = j;
            count++;
        }
        }
        var temp = arr[pos];
        arr[pos] = arr[i];
        arr[i] = temp;
    }
    return count;
}