**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);
}
}

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

Search Terms...

### Like this:

Like Loading...

## Comments are closed.