CODEWITHSUNDEEP
javascriptbubble-sort
Rich J
Rich J

Reputation: 35

js Bubble sort not processing all elements correctly

I pass in elements array [5,4,3]. The bubble sort manages to push 5 the end, this is fine, but when it loops through a third time to locate the second to last element, the loop breaks and the incorrect ordered array is returned... not sure why, cheers guys 

this.bubbleSort = function (elements) {

        //Loop through to the second to last index. By the time we get to the last index, its already //been compared with what’s in front of it
        var hasHadChange;
        for (var x = 0; x < elements.length - 1; x++) {
            hasHadChange = false;

            //Loop through to the second to last index.
            for (var y = 0; y < elements.length - 1; y++) {

                //Check the current item(x) in the array plus the item next to current item (x+1), if its larger
                if (elements[y] > elements[y + 1]) {

                    //Acknowledge there has been a change
                    hasHadChange = true;

                    //Swap the items around
                    var temp = elements[y];
                    elements[y] = elements[y + 1];
                    elements[y + 1] = temp;
                    //This continues until the largest value has bubbled to the right
                }
            }
        }
        return elements;
    }

Upvotes: 0

Views: 123

Answers (3)

vjdhama
vjdhama

Reputation: 5078

You should use separate variables in inner and outer loops. Using y in inner loop instead will give you the correct answer.

var bubbleSort = function (elements) {

    //Loop through to the second to last index. By the time we get to the last index, its already //been compared with what’s in front of it
    var hasHadChange;
    for (var x = 0; x < elements.length - 1; x++) {
        hasHadChange = false;

        //Loop through to the second to last index.
        for (y = 0; y < elements.length - 1; y++) {

            //Check the current item(x) in the array plus the item next to current item (x+1), if its larger
            if (elements[y] > elements[y + 1]) {

                //Acknowledge there has been a change
                hasHadChange = true;

                //Swap the items around
                var temp = elements[y];
                elements[y] = elements[y + 1];
                elements[y + 1] = temp;
                //This continues until the largest value has bubbled to the right
            }
        }
    }
    return elements;
}

The reason behind this is variable hoisting.

When a variable is declared, it breaks into two parts. One part moves to top of it's scope, other stays at it's position. For Example,

function foo() {
    if (false) {
        var x = 1;
    }
    var y = 1;
}

Will look like :

function foo() {
    var x = undefined;  //Declaration of x is hoisted
    var y = undefined;   //Declaration of y is hoisted
    if (false) {
        x = 1; //Assignment still occurs where we intended
    }
    y = 1; //Assignment still occurs where we intended
}

This is what happened in the code. Using same variable in both loops makes them overwrite each other values. Hence the result.

From ECMAScript standard 5.1 :

A variable statement declares variables that are created as defined in 10.5. Variables are initialised to undefined when created. A variable with an Initialiser is assigned the value of its AssignmentExpression when the VariableStatement is executed, not when the variable is created.

See this MDN doc for more details. Look for topic var hoisting.

Update

Using let which has block level scope, you can have variable x in both loops. 

var bubbleSort = function (elements) {

    //Loop through to the second to last index. By the time we get to the last index, its already //been compared with what’s in front of it
    var hasHadChange;
    for (var x = 0; x < elements.length - 1; x++) {
        hasHadChange = false;

        //Loop through to the second to last index.
        for (let x = 0; x < elements.length - 1; x++) {

            //Check the current item(x) in the array plus the item next to current item (x+1), if its larger
            if (elements[x] > elements[x + 1]) {

                //Acknowledge there has been a change
                hasHadChange = true;

                //Swap the items around
                var temp = elements[x];
                elements[x] = elements[x + 1];
                elements[x + 1] = temp;
                //This continues until the largest value has bubbled to the right
            }
        }
    }
    return elements;
}

Upvotes: 0

tomasb
tomasb

Reputation: 1673

You are using the same control variable x for both for-cycles, should use different like x and y for example.

Upvotes: 0

Guffa
Guffa

Reputation: 700472

You need to use separate variables for the inner and the outer loop. When you exit the inner loop, x will be equal to the length, so the outer loop will end also.

Upvotes: 1

Related Questions