Thursday, December 7, 2017

Java Bubble sort

Example:
we have array of 5 numbers: [5,3,4,1,2]
To sort this array with Bubble sort we must compare each pair of adjacent items - if the order is wrong - swap them:
At step 3.2 our array will be sorted but algorithm doesn't know that so the algorithm will:
  1.  make external loop (array.length) times, one time for each index of the array,
  2.  and internal loop pairs_in_an_array times, one time for each adjacent pair  
  3. (let's count pairs in [5,3,4,1,2] :  
  4. 1) [5,3] ; 2) [3,4] ; 3) [4,1] ; 4) [1,2] - it's equal to (array.length - 1))
  1. loop 1:
    1. [5,3,4,1,2] -> [3,5,4,1,2]
    2. [3,5,4,1,2] -> [3,4,5,1,2]
    3. [3,4,5,1,2] -> [3,4,1,5,2]
    4. [3,4,1,5,2] -> [3,4,1,2,5]
  2. loop 2: 
    1. [3,4,1,2,5] -> [3,4,1,2,5]
    2. [3,4,1,2,5] -> [3,1,4,2,5]
    3. [3,1,4,2,5] -> [3,1,2,4,5]
    4. [3,1,2,4,5] -> [3,1,2,4,5]
  3. loop 3:
    1. [3,1,2,4,5] -> [1,3,2,4,5]
    2. [1,3,2,4,5] -> [1,2,3,4,5]
    3. [1,2,3,4,5] -> [1,2,3,4,5]
    4. [1,2,3,4,5] -> [1,2,3,4,5] 
  4. loop 4:
    1. [1,2,3,4,5] -> [1,2,3,4,5]
    2. [1,2,3,4,5] -> [1,2,3,4,5]
    3. [1,2,3,4,5] -> [1,2,3,4,5]
    4. [1,2,3,4,5] -> [1,2,3,4,5]
  5. loop 5: 
    1. [1,2,3,4,5] -> [1,2,3,4,5]
    2. [1,2,3,4,5] -> [1,2,3,4,5]
    3. [1,2,3,4,5] -> [1,2,3,4,5]
    4. [1,2,3,4,5] -> [1,2,3,4,5]
The algorithm called bubble sort because each high element goes to the top of the array as bubble goes to the top of the water reservoir.
Algorithm itself is too slow and impractical to be used in production environment. 

public class BubbleSort 
{
    public static void main(String[] args) throws Exception 

    {
    }

    public static void sort(int[] array) 

    {
        // extI - external loop iterator
        // intI - internal loop iterator
        for (int extI = 0; extI < array.length; extI++)

        {
            for (int intI = 0; intI < array.length-1; intI++)

            {
                if (array[intI + 1] < array[intI])

                {
                    int temp = array[intI + 1];
                    array[intI + 1] = array[intI];
                    array[intI] = temp;
                }
            }
        }
    }
}

No comments:

Post a Comment