Best Case for Bubble Sort

Question

I want to know what will be the best case for a bubble sort ? There may be a case wherein there may be no swapping for the say last 2 passes for example. I'm doing my program in C language. Suppose i have an array of 5 elements and i give the elements as 1 2 5 4 3 then there would be no change in the last 2 passes?

Answer 1

Best case scenario is one pass. The list would already be sorted.
No swap = done.

Answer 2

Please see Bubble sort:

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.

• Worst case performance O(n²)
• Best case performance O(n)
• Average case performance O(n²)
• Worst case space complexity O(n) total, O(1) auxiliary
• Optimal No

Answer 3

It's hard to tell if you mean

1. What is the best case algorithmic complexity of the bubble sort, in which case C# makes no difference, the answer is O(n) for an already sorted input.
2. When, if ever, you should consider using a bubble sort.

In the latter case, you don't, because for the small cases the Shell sort and Insertion sort will both outperform it. Some of the best performing sorting routines I've seen are hybrids Quick Sort that use a Shell Sort for "small" sections of the array.

Answer 4

It's not possible for a bubble sort not to swap for two passes.

A pass without swapping means the list is already sorted.

Answer 5

The best case is when the data is already sorted. Another good case is when there are a tiny number of items to sort - I once used it when my typical list was two items and occasionally went to four.

Answer 6

A bubble sort is rarely your best case for doing a sort. It is exceptionally slow and inefficient. Many other sorting algorithms are faster. For example, you may consider using something like a QuickSort.

The fastest sorting algorithm I am aware of was developed by Steffan Nilsson and is described in the following article.

http://www.ddj.com/architect/184404062;jsessionid=VWL2QD1NWIEIJQE1GHOSKHWATMY32JVN?_requestid=396640

If you just want to know how to implement a bubble sort, you can find a good article here.

http://en.wikipedia.org/wiki/Bubble_sort

Answer 7

Rather than implement a bubblesorter (which as others point out can be complex and slow). Have you tried sorting with LINQ. I recently did away with a gigantic bubble sorter with a line like this:

var result = from foo in collectionOfFoos
             orderby foo.Author, foo.Title descending
             select foo;

This took a large collection and sorted them first by Author and then by title. It unit tests quite nicely too.

Answer 8

Best Case: The best case would be if the list were already sorted. a) there will be comparisons as it is but no exchanges and execution time is in O(n2) b) But if we keep a track of exchanges in each pass and terminate the program checking if no exchanges. Then the program would require only one pass and max. (n-1) comparisons are required in that single pass and we can say that the complexity is of order of O(n).