Javascript код пузыря сортировки нужно немного объяснить - PullRequest
Новая
       7

Javascript код пузыря сортировки нужно немного объяснить

0 голосов
/ 12 марта 2019

Я пишу программу для сортировки пузырьков, но что я не понимаю, так это строка j<len-i в этом коде?

я могу просто удалить -i из приведенной выше строки, это такжеработа, 

var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

var len = arr.length,
    i, j, stop;

for (i=0; i < len; i++){
    for (j=0; j<len-i;  j++){
        if (arr[j] > arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;

        }
    }
}

return arr;
}
console.log(bubble_Sort(arr));


//with -i in second for loop
var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

    var len = arr.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0; j<len-i;  j++){
            if (arr[j] > arr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                
            }
        }
    }

    return arr;
}
console.log(bubble_Sort(arr));

Без -i во втором цикле

Ответы [ 3 ]

1 голос
/ 12 марта 2019

Вы можете понять, почему это работает, если вы записываете arr для каждого цикла "i". 

var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

var len = arr.length,
    i, j, stop;

for (i=0; i < len; i++){
    for (j=0; j<len-i;  j++){
        if (arr[j] > arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;

        }
    }
    console.log(arr)
}

return arr;
}
console.log(bubble_Sort(arr));

(9) [3, 4, 5, 7, 8, 9, 0, -1, 30]

(9) [3, 4, 5, 7, 8, 0, -1, 9, 30]

(9) [3, 4, 5, 7, 0, -1, 8, 9, 30]

(9) [3, 4, 5, 0, -1, 7, 8, 9, 30]

(9) [3, 4, 0, -1, 5, 7, 8, 9, 30]

(9) [3, 0, -1, 4, 5, 7, 8, 9, 30]

(9) [0, -1, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

каждый цикл i перемещает большое число на нижнее, поэтому последнее число i стабильно.

0 голосов
/ 12 марта 2019

Это потому, что каждый раз последний элемент сортируется. После каждой итерации вы обнаружите, что последний элемент находится в правильном месте (для 0-й итерации - последний элемент находится в правильной позиции, для 1-й итерации - последние 2 элемента находятся в правильной позиции и т. Д.). Поэтому каждый раз, когда мы перебираем элементы len - i.

0 голосов
/ 12 марта 2019

Рассмотрим массив (сортируемый в порядке возрастания): 

[4, 3, 2, 1]

После запуска внутреннего цикла с помощью i = 0 вы получите:

[3, 2, 1, <strong>4</strong>]

Теперь, i=1 ...

Повторяя процесс снова, на следующей итерации, когда i=1 вы получите:

[2, 1, <strong>3, 4</strong>]

Теперь,i=2

Снова, повторяя цикл снова в i=2, вы получите:

[1, <strong>2, 3, 4</strong>]

Теперь i=3

Обратите внимание, как полужирный числа уже в отсортированном порядке.

Здесь у нас есть инвариант цикла для внешнего цикла (т. Е. Оператор, который выполняется для каждой итерации внешнего цикла), то есть последние i элементов массива расположены в отсортированном порядке.Или, с другой стороны, все элементы массива из [0, ... length-i) не отсортированы, и, следовательно, элементы из индекса length-i и далее расположены в отсортированном порядке.

Другими словами, когда вы смотрите на свой массив, вы видите, что после каждой итерации внешнего цикла все элементы массива из length-i, ..., length расположены в отсортированном порядке, и, следовательно, нет необходимости повторно сортировать / перепроверятьих.

Таким образом, предоставление len-i предотвращает повторную проверку элементов в уже отсортированном порядке, поскольку вы знаете, что их не нужно менять.

...