Optimized bubble sort c#

Optimized version of bubble sort

Bubble sort is a slow comparison based sorting algorithm. Can you suggest one way to optimize it.

Optimized bubble sort complexity and solution

Bubble sort works by repeatedly visiting all elements of the list to be sorted comparing each pair of adjacent elements and swapping them if they are not in order. This process continues until no swaps are needed which indicates that the list is sorted. The worst case complexity of bubble sort is O(n^2). On the other hand the best case complexity is O(n) when the list is already sorted. Bubble sort algorithm can be optimized by observing that all elements after the last swap are sorted so there is no need to check them again. We can exploit this fact to prevent the inner loop from exceeding the position of the last swap.

Optimized bubble sort algorithm

Here is an example optimized bubble sort code

//Main program
class Program
    static void Main()
        //Input array
        int[] A = new int[10] { 7, 6, 5, 4, 3, 2, 1, 8, 9, 10 };

        //Initial array size. We are going to
        //keep decreasing this value based on
        //the last swap we encounter.
        int n = 10;

        //Keep looping until list is sorted
        {    //This variable is used to store the
            //position of the last swap
            int sw = 0;

            //Loop through all elements in the list
            for (int i = 0; i < n - 1; i++) 
                //If the current pair of elements is 
                //not in order then swap them and update 
                //the position of the swap 
                if (A[i] > A[i + 1])
                    int temp = A[i];
                    A[i] = A[i + 1];
                    A[i + 1] = temp;

                    //Save swap position
                    sw = i + 1;

            //We do not need to visit all elements
            //we only need to go as far as the last swap
            //so we update (n)
            n = sw;

        //Once n = 1 then the whole list is sorted
        while (n > 1);

Please use the comments section below for feedback. Thanks for reading.

Search Terms...

Leave a Reply