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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
//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.
is it the most efficient bubble sort algorithm or could it be even more optimalized?