Sorting - Bubble Sort

HackerRank > Cracking the Coding Interview > Sorting: Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Given an X element array of distinct elements, sort the array in ascending order using the Bubble Sort algorithm. Once sorted, print the following three lines:

  1. Array is sorted in X swaps, where X is the number of swaps taken to sort
  2. First Element: X, where X is the first element in the sorted array.
  3. Last Element: X, where X is the last element in the sorted array.
Input format
  • The first line contains an integer, denoting the number of elements in array.
  • The second line contains space-separated integers describing the respective values in the array

Solution


process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

function main() {
    var n = parseInt(readLine());
    a = readLine().split(' ');
    a = a.map(Number);

/////////////// Start Code Here ////////////////////

    // Set variable to calculate number of iterations, used in stdout line 1
    var counter = 0;
    // Make array more readible for rest of code
    var arr = a;
    var len = a.length;

        // Iterate through the array, checking if the left element is greater than the right element
        for (var i = len-1; i>=0; i--){
            for(var j = 1; j<=i; j++){
                if(arr[j-1]>arr[j]){
                    // When it is, swap the elements around and count how many times this function has been performed
                    var temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                    counter++;
                }
            }
        }
   console.log("Array is sorted in " + counter + " swaps.");
   console.log("First Element: " + arr[0]);
   console.log("Last Element: " + arr[len-1]);

/////////////// End Code Here ////////////////////
}