August 25, 2010

Optimized bubble sort c#

By Mohammed Abualrob Algorithms and Data Structures 1 Comment

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
{
    //Main
    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
        do
        {    //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])
                {
                    //Swap
                    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);
    }
}

//Main program

class Program

{

//Main

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])

{

//Swap

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.

8 BIT AVENUE

Optimized bubble sort c#

More from my site

About Author

Mohammed Abualrob

Add a Comment