Optimized Bubble Sort (Java)

Question

I would like to know how else I can optimize bubble sort so that it overlooks elements that have already been sorted, even after the first pass.

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]

We observe that [4,5,6] are already in sorted order, how can modify my code so that it overlooks this 3 elements in the next pass? (which means the sort would be more efficient?) Do you suggest a recursive method?

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

Thanks for your time!

Answer 1

you should use a variable "size" for the inner loop and change it to the latest swapped element in each cycle.This way your inner loop goes up to the latest "swapped" element and passes the rest that are unswapped (aka in their correctplace). i.e

do {
        int newsize =0;
        for (int i = 1; i < size; i++) {
            if (a[i - 1] > a[i]) {
                int temp;
                temp = a[i - 1];
                a[i - 1] = a[i];
                a[i] = temp;
                newsize =i;
            }
        }
        size = newsize;
   } while (size > 0);

Answer 2

 public static Integer[] optimizedbubbleSort(Integer[] input){
    long startTime = System.nanoTime();
    boolean swapped = true;
    for(int pass=input.length-1; pass>=0 && swapped; pass--){
        swapped = false;
        for(int i=0; i<pass; i++){
            if(input[i]>input[i+1]){
                int temp = input[i];
                input[i] = input[i+1];
                input[i+1] = temp;
                swapped = true;
            }
        }
    }
    System.out.println("Time taken for OPTIMIZED bubbleSort: "+(System.nanoTime() - startTime));
    return input;
}

Answer 3

I devised a method that reduces the number of iterations by excluding parts at the beginning and end of the array that have been ordered in previous loops.

static int[] BubbleSortOptimized(int arr[]) {
    int start = 0, stop = arr.length - 1, control = 0;
    boolean ordered, nsCaught;
    while (true){
        ordered = true;
        nsCaught = false;
        for (int i = start; i < stop; i++) {
            if (i > 1) {
                if (!nsCaught && arr[i-2] > arr[i-1]){
                    ordered = false;
                    start = i-2;
                    nsCaught = true;
                }
            }
            if (arr[i] > arr[i+1]){
                int hold = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = hold;
                control = i;
            }
        }
        System.out.println(Arrays.toString(arr));
        if (ordered) return arr;
        stop = control;
    }
}

But as @Daniel Fischer said in an earlier answer, it doesn't do a lot with larger arrays.

Answer 4

public class Tester {
    static boolean bubbleFlag = true;

    public static void main(String[] args) {
        int array[] = new int[] {
            1,
            9,
            2,
            3,
            4,
            5,
            6
        };
        bubbleSort(array);
    }

    private static void bubbleSort(int...array) {
        System.out.println("Before Sorting: " + Arrays.toString(array));

        for (int i = 0; i < array.length - 1; i++) {
            if (i > 0) if (bubbleFlag) break;

            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) array = swap(j, j + 1, array);
                System.out.println("Iteration " + i + " :" + Arrays.toString(array));
            }
            bubbleFlag = true;
        }
    }

    private static int[] swap(int i1, int i2, int...is) {
        bubbleFlag = false;
        is[i1] = is[i1] + is[i2];
        is[i2] = is[i1] - is[i2];
        is[i1] = is[i1] - is[i2];
        return is;
    }
}

Answer 5

    public static void BubbleSorter(params int[] input){
        int newSize = input.Length-1, size = 0;
        bool swap;
        do
        {
            swap = false;
            for (int j = 0; j < newSize; j++)
            {
                if (input[j] > input[j + 1])
                {
                    int temp = input[j + 1];
                    input[j + 1] = input[j];
                    input[j] = temp;
                    swap = true;
                    size = j;
                }
            } newSize = size;
        } while (swap);

        DisplayArrayElements(input);
    }

Answer 6

In the above example, the array got sorted after 3rd pass, but we will still continue with the 4th, 5th pass. Suppose if the array is already sorted, then there will be no swapping (because adjacent elements are always in order), but still we will continue with the passes and there will still be (n-1) passes.

If we can identify, that the array is sorted, then we should stop execution of further passes. This is the optimization over the original bubble sort algorithm.

If there is no swapping in a particular pass, it means the array has become sorted, so we should not perform the further passes. For this we can have a flag variable which is set to true before each pass and is made false when a swapping is performed.

void bubbleSort(int *arr, int n){
for(int i=0; i<n; i++)
{  
  bool flag = false;
   for(int j=0; j<n-i-1; j++)
   {
      if(array[j]>array[j+1])
      {
        flag = true;
         int temp = array[j+1];
         array[j+1] = array[j];
         array[j] = temp;
      }
   }
  // No Swapping happened, array is sorted
  if(!flag){ 
     return; 
  }}}