Yet another bubble sort comparison

Bubble sort isn't a very efficient algorithm, with O(n²) average and worse-case performance.  Anyway, here are some of the algorithm's original and optimized implementations in Java that I've googled up.  This computer club blog has a nice impl in java, python, and c++.  The Algorithmist wiki, which appears to be a nice and concise resource for prep work, also has a couple of optimizations.

/**  * Sbubble sort impls  *   * @author sshakil  *   */ public class BubbleSort {   private static int array[] = { 9, 1, 8, 10, 4, 1 };   public static void main(String args[]) {     System.out.print("Bubble Sort: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     int[] sorted = bubbleSort(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     // Optimized     System.out.print("\n\nBubble Sort Optimized: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     // Optimized 2     System.out.print("\n\nBubble Sort Optimized 2: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized2(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     // Optimized 3     System.out.print("\n\nBubble Sort Optimized 3: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized3(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }          // Optimized 4     System.out.print("\n\nBubble Sort Optimized 4: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized4(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }   }   /**    * Bubble sort, original    *     * @param arr    * @return    */   private static int[] bubbleSort(int[] arr) {     int i, j, temp;     int swaps = 0;     int iters = 0;     for (i = 0; i < arr.length; i++) {       for (j = 0; j < (arr.length - 1); j++) {         iters++;         if (arr[j] > arr[j + 1]) {           // move the bigger number (arr[j]) up:           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;           swaps++;         }       }     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }   /**    * Based on a nicely written implementation from:     * {@link http://csalgorithm.wordpress.com/2010/03/13/optimized-bubble-sort/}    *     * @param arr    * @return    */   private static int[] bubbleSortOptimized(int[] arr) {     int lastSwapped = arr.length;     int i, temp;     int swaps = 0;     int iters = 0;     while (lastSwapped > 1) {       int newLastSwapped = 0;       for (i = 0; i < lastSwapped - 1; i++) {         iters++;         if (arr[i] > arr[i + 1]) {           temp = arr[i + 1];           arr[i + 1] = arr[i];           arr[i] = temp;           newLastSwapped = i + 1;           swaps++;         }       }       lastSwapped = newLastSwapped;     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }   /**    * Based on pseudo code from:     * {@link http://www.algorithmist.com/index.php/Bubble_sort}    *     * @param arr    * @return    */   private static int[] bubbleSortOptimized2(int[] arr) {     int i, j, temp;     boolean swaped = false;     int swaps = 0;     int iters = 0;     for (i = 0; i < arr.length; i++) {       swaped = false;       for (j = 0; j < (arr.length - 1); j++) {         iters++;         if (arr[j] > arr[j + 1]) {           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;           swaped = true;           swaps++;         }       }       if (!swaped)         break;     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }   /**    * Based on pseudo code from:     * {@link http://www.algorithmist.com/index.php/Bubble_sort}    *     * @param arr    * @return    */   private static int[] bubbleSortOptimized3(int[] arr) {     int i, j, temp;     boolean swaped = false;     int swaps = 0;     int iters = 0;     for (i = 0; i < arr.length; i++) {       swaped = false;       for (j = 0; j < (arr.length - i - 1); j++) {         iters++;         if (arr[j] > arr[j + 1]) {           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;           swaped = true;           swaps++;         }       }       if (!swaped)         break;     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }      /**    * From:     * {@link http://stackoverflow.com/questions/8690732/    * bubble-sort-implementation-to-sort-arrays-how-effecient}    * @param arr    * @return    */   private static int[] bubbleSortOptimized4(int[] arr) {     boolean swapped = true;     int i = 0;     int j = 0;     int temp;     int swaps = 0;     int iters = 0;     while (swapped) {       swapped = false;       i++;       for (j= 0; j < arr.length - i; j++) {         iters++;         if (arr[j] > arr[j + 1]) {           temp = arr[j];           arr[j] = arr[j + 1];           arr[j + 1] = temp;           swapped = true;           swaps++;         }       }     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   } }

Final != Immutable

Just learned that in Java 1.6 (or anything after 1.3, from what I recall from the blog that I read), the final modifier on a primitive int array does not imply immutability (non-modifiable); found this when playing with a couple of sorting algorithms.  In the code below, if we want to use the same static array 'array' to be printed before sending it to various successive sorting methods, then we should send clones of it:

public class InsertionSort {   private static int array[] = { 5, 9, 7, 4, 1 };   public static void main(String args[]) {     System.out.print("Insertion Sort: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     int[] sorted = insertionSort(array.clone());     System.out.print("\nSorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     System.out.print("\n\nBubble Sort: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSort(array.clone());     System.out.print("\nSorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }   }   private static int[] insertionSort(int[] arr) {     int i, j, newValue;     for (i = 1; i < arr.length; i++) {       newValue = arr[i];       j = i;       while (j > 0 && arr[j - 1] > newValue) {         arr[j] = arr[j - 1];         j--;       }       arr[j] = newValue;     }     return arr;   }   private static int[] bubbleSort(int[] arr) {     int i, j, temp;     for (i = 0; i < arr.length; i++) {       for (j = 0; j < (arr.length - 1); j++) {         if (arr[j] > arr[j + 1]) {           // move the bigger number (arr[j]) up:           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;         }       }     }     return arr;   } }

-->