Optimized Bubble Sort


The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n − 1 items when running for the n-th time.



Optimized Bubble Sort Visualization

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
10 21 12 37 14 59 56 74 80 39 20

Number of passes completed :



      




Trace
  • procedure optimized_bubble_sort (list [n])
  •  for all elements in list of size [n]
  •    if list[i] > list[i+1]
  •       swap(list[i], list[i+1])
  •       n=n-1
  •    end if
  •  end for
  •            return list
  •        end BubbleSort




Optimized Bubble Sort Code in C:

                      
                        #include <stdio.h>
 
                        int main()
                        {
                          int array[100], n, c, d, swap;
                         
                          printf("Enter number of elements\n");
                          scanf("%d", &n);
                         
                          printf("Enter %d integers\n", n);
                         
                          for (c = 0; c < n; c++)
                            scanf("%d", &array[c]);
                         
                          for (c = 0 ; c < n - 1; c++)
                          {
                            for (d = 0 ; d < n - c - 1; d++)
                            {
                              if (array[d] > array[d+1]) /* For decreasing order use < */
                              {
                                swap       = array[d];
                                array[d]   = array[d+1];
                                array[d+1] = swap;
                              }
                            }
                          }
                         
                          printf("Sorted list in ascending order:\n");
                         
                          for (c = 0; c < n; c++)
                             printf("%d\n", array[c]);
                         
                          return 0;
                        }