Bubble Sort


Bubble Sort
Introduction:

1) Compares each element in an array with its adjacent element.
2) If the one on the right hand side is greater(or lesser based on the
order of sort required) the elements are swapped.
3) This iteration is performed multiple times untill, there is one iteration
which makes no swaps
Process:
Consider:[3,4,1,2] should be sorted in ascending order
Iteration 1:
Input: [3,4,1,2]
Step 1: compare 3 and 4. 3 <4 => no change => [3,4,1,2]
Step 2: Compare 4 and 1. 4 > 1 => swap => [3,1,4,2]
Step 3: Compare 4 and 2. 4 > 2 => swap => [3,1,2,4]
Result: [3,1,2,4] => Greatest element has moved to its position(the end)
swapped = true
Iteration 2:
Input: [3,1,2,4]
Step 1: compare 3 and 1. 3 > 1 => swap => [1,3,2,4]
Step 2: Compare 3 and 2. 3 > 2 => swap => [1,2,3,4]
Result: [1,2,3,4] => second greatest element has moved to its position(penultimate).
     Other elements have also fallen in place, which happened only because
of the input combination we have.
swapped = true
Iteration 3:
Input: [1,2,3,4]
Step 1: compare 1 and 2. 1 < 2 => no change => [1,2,3,4]
Result: [1,2,3,4] => All elements have fallen in place.
swapped = false
Since swapped flag is false, no more iterations are required.

 Note:
1)Step 3 is not performed in iteration 2, because we are certain that the greatest element
has moved to the end at the end of iteration 1.
2) Step 2 and 3 are not performent in iteration 3, because we are certain that greatest(as a part
of iteration 1) and second greatest (as a part of iteration 2) have moved to their respective places.
Performance:

As it can be seen from the above section, there are two loops in question
1) Inner loop 2) Outer loop
1) Inner loop:
Runs n times in the first iteration, n-1 times in the second iteration all the way up to 1 time
in the last iteration. So
n+(n-1)+.....+1
2) Outer loop:
Runs n times in the worst case.
Total complexity:
o(n *(n+(n-1)+(n-2)+...+1))
o(n*n)
o(n^2)
This is one of the least performing algorithms for sorting. The biggest draw back of this algorithm is
that it runs one extra iteration after sorting everything because it is unaware that everything is already

sorted. Code implementation: https://github.com/vinodm1986/Algorithms/blob/master/Sorting/bubble_sort.groovy Please let me know your comments!

Comments

Post a Comment

Popular posts from this blog

Dockerfile

This post serves as a quick note on how to create a Dockerfile. It is not intended to be a comprehensive guide for the same. 1) FROM   = The image from dockerhub on which the   current image should be based on   2) MAINTAINER   = This is just a free text field where you put in your Name or email id, just so that people can identify the maintainer   3) EXPOSE = The port on which the container should be exposed. This can be overridden while doing a docker run command.   4)   ENTRYPOINT = The command to be executed when the container   strats   up.   For Example: npm start   5) COPY   = used to copy the source code into the docker machine.   For   exmple : COPY . /var/www   Where .(dot) represents that the whole of current directory needs to be copied.   6) WORKDIR   = The root directory from where the commands need to be run. For example, while running npm start, the di...
Read more

ES-6 classes

Code for this and several other ES-6 features can be found in my  github ES-6 has introduced a “class” keyword and “extends” keyword which are similar looking to classes in Java. In reality these are nothing but a syntactic sugar over prototypical inheritance in ES-5. In ES-5 classes were depicted as follows: var PersonEs5 = function(firstName, lastName){ this.firstName = firstName; this.lastName =lastName; } var p1 = new PersonEs5('first','last'); With ES-6 the same class can be written as follows: class Person{ constructor(firstName,lastName){ this.firstName = firstName; this.lastName = lastName; } } Classes are nothing but functions under the cover. If the ES-6 code is compiled down to ES-5, the compiled version will be as follows: function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } } var Pers...
Read more

ES-6 Generators

Code for this and several other ES-6 features can be found in my  github Introduction: Generators have been introduced in Java script as a part of the latest ES6 release. This feature offers significant advantages in asynchronous programming. The Legacy stuff: Functions in Java script (or in most languages) have been a bunch of instructions which start with a single motive- which is to execute the instructions and race to completion. Let us consider for example: var add = function (a, b){ if(a < 0) a = a*-1; if(b < 0) b = b *-1; return a+b; } The add function declared above is a simple function which takes two input parameters. Checks if any of them is negative. If it is negative it makes it positive. Adds the two numbers and returns their sum. Basically, once the add function starts execution, it just runs. Any change that happens around it can influence it in no way. If a developer wants the add function to behave differently, the developer has to ...
Read more