/*
 * [BubbleSort.java]
 *
 * Summary: Sort an array using a primitive Bubblesort.
 *
 * Copyright: (c) 2009-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.8+
 *
 * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 2010-12-28 initial version
 */
package com.mindprod.example;

import static java.lang.System.*;

/**
 * Sort an array using a primitive Bubblesort.
 * <p/>
 * This algorithm is very slow when the number of elements to sort is large.
 * It is just for learning purposes, not a production sort.
 * Its saving grace is it is simple to code.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.0 2010-12-28
 * @since 2010-12-28
 */
public final class BubbleSort
    {
    /**
     * Sort an array in place using a BubbleSort algorithm.
     *
     * @param a an array of integers, unsorted
     */
    private static void sort( int a[] )
        {
        for ( int i = a.length; --i >= 0; )
            {
            boolean flipped = false;
            for ( int j = 0; j < i; j++ )
                {
                if ( a[ j ] > a[ j + 1 ] )
                    {
                    // if pair out of order, swap them.
                    int temp = a[ j ];
                    a[ j ] = a[ j + 1 ];
                    a[ j + 1 ] = temp;
                    flipped = true;
                    }
                }
            if ( !flipped )
                {
                return;
                }
            }
        }

    /**
     * test driver
     *
     * @param args not used
     */
    public static void main( String[] args )
        {
        int[] a = { 9, 7, 8, 5, 4 };
        sort( a );
        for ( int elt : a )
            {
            out.println( elt );   // prints 4 5 7 8 9
            }
        }
    }