Bubble Sort

http://www.geeksforgeeks.org/recursive-bubble-sort/

1. Base Case: If array size is 1, return.
2. Do One Pass of normal Bubble Sort. This pass fixes last element of current subarray.
3. Recur for all elements except last of current subarray.

void bubbleSort(int arr[], int n)

{

    // Base case

    if (n == 1)

        return;

 

    // One pass of bubble sort. After

    // this pass, the largest element

    // is moved (or bubbled) to end.

    for (int i=0; i<n-1; i++)

        if (arr[i] > arr[i+1])

            swap(arr[i], arr[i+1]);

 

    // Largest element is fixed,

    // recur for remaining array

    bubbleSort(arr, n-1);

}

https://github.com/anujku/InterviewPractice/blob/master/src/com/anuj/interview/practice/sorting/simple/BubbleSort.java

	// Complexity : O(N^2) // Worst case performance O(n^2)
	// Best case performance O(n)
	// Average case performance O(n^2)
	// Worst case space complexity O(1) auxiliary
	private static int[] bubbleSort(int[] array) {
	for (int outer = array.length - 1; outer > 1; outer--) {
	for (int inner = 0; inner < outer; inner++) {
	if (array[inner] > array[inner + 1]) {
	int temp = array[inner];
	array[inner] = array[inner + 1];
	array[inner + 1] = temp;
	}
	}
	}
	return array;
	}
	private static int[] modifiedBubbleSort(int[] array) {
	boolean exchanged = false;
	for (int outer = array.length - 1; outer > 1; outer--) {
	exchanged = false;
	for (int inner = 0; inner < outer; inner++) {
	if (array[inner] > array[inner + 1]) {
	exchanged = true;
	int temp = array[inner];
	array[inner] = array[inner + 1];
	array[inner + 1] = temp;
	}
	}
	if (!exchanged) break;
	}
	return array;
	}