Sunday, September 18, 2011

Bubble Sort - Algorithm & Implementation

package main.java.algo.sorting;

public class BubbleSort {

	/***
	 *** Algorithm
	 *** 
	 *** Compare each pair of adjacent elements from the beginning of an array
	 *** and, if they are in reversed order, swap them. If at least one swap has
	 *** been done, repeat step 1.
	 *** 
	 *** In every pass, the biggest elements keep moving towards the right.
	 *** After 1st pass, we'll have the biggest in rightmost.
	 *** In 2nd pass, we'll have 2nd biggest on last -1 position
	 *** 
	 ***/

	public void bubbleSort(int[] arr) {
		boolean swapped = true;
		int j = 0;
		int tmp;
		while (swapped) {
			swapped = false;
			j++;
			// in every one for loop, the largest element is pushed towards the right,
			for (int i = 0; i < arr.length - j; i++) {
				if (arr[i] > arr[i + 1]) {
					tmp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = tmp;
					swapped = true;
				}
			}
		}
	}

}

/***
 *** Average and worst case complexity of bubble sort is O(n2). Also, it makes O(n2) swaps in the worst case - when the list is already in desc sorted
 *** Bubble sort is adaptive. It means that for almost sorted array it gives O(n) estimation***/

1 comment: