/******************************************************************************
Bubble Sort
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.searchAndSort;

import FlexOr.container.*;

/** Sort an array of objects using bubble sort.

<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public class BubbleSort implements ArraySort {

/**
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public void sort(final Object[] array, final BinaryPredicate bp) {
       execute(array, bp);
   }

/** The bubble sort method.

@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public static void execute(final Object[] array, final BinaryPredicate bp) {
       Object tmp;
       boolean swapWasNotDone = true;

       //Loop invariant: for i : 0..array.length :: ( sorted(array[0..i-1])
       
       for (int i = 0 ; i < array.length-1 ; i++) {
           
           // Loop invariant: array[j] bp array[j+1 .. array.length-1]
       
           for (int j = array.length-1 ; j > i ; j--) {
               if (bp.execute(array[j], array[j-1])) {
                   tmp = array[j]; array[j] = array[j-1]; array[j-1] = tmp;
                   swapWasNotDone = false;
               }
           }
           if (swapWasNotDone) break;
       }
   }
}