Bubble sort isn't a very efficient algorithm, with O(n
2) 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;
}
} |
No comments:
Post a Comment