CODEWITHSUNDEEP
algorithmbubble-sort
Yash
Yash

Reputation:

Best Case for Bubble Sort

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?

Upvotes: 13

Views: 66356

Answers (9)

tempmail
tempmail

Reputation: 186

There are multiple ways to write the bubble sort algorithm, it seems like over time the algorithm has gotten better, and more efficient. The first bubble sort algorithm I learned is below. The algorithm below Best and Worst Case is O(n^2).

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2     for j = A.length downto i + 1
3         if A[j] < A[j - 1]
4             exchange A[j] with A[j - 1]

The algorithm that Wikipedia uses (below) seems to be an improvement using a flag to tell if the elements have been swapped or not, which allows the bubble sort algorithm best case to be O(n) instead of O(n^2)

    procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat 
        swapped = false
        for i = 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap( A[i-1], A[i] )
                swapped = true
            end if
        end for
    until not swapped
end procedure

Here is a video that helps explain a little bit about the first algorithm in the C programming language: https://youtu.be/qOpNrqqTsk4

Upvotes: 12

baz
baz

Reputation: 1587

either wikipedia or i'm wrong but for me best case and worst case are both O(n2) this is from the book Introduction to Algorithms

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2     for j = A.length downto i + 1
3         if A[j] < A[j - 1]
4             exchange A[j] with A[j - 1]

so regardles of whether the array is sorted or not there is no one pass becoz even if line 4 is skipped line 2 and 3 are executed propotionally to n2 times

edit: i think i got it wikipedia are right after all but one has to modify the algorithm by adding let's say boolean variable is_exchange setting it to false before entering the second loop and if it's false again after exiting the loop then we are done and in that case time will be O(n) becoz second loop is executed n times

Upvotes: 0

user239103
user239103

Reputation:

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

Upvotes: 29

Andrew Hare
Andrew Hare

Reputation: 351516

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

Upvotes: 12

Anthony Gatlin
Anthony Gatlin

Reputation: 4413

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

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308206

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.

Upvotes: 2

Bryan Menard
Bryan Menard

Reputation: 13384

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

A pass without swapping means the list is already sorted.

Upvotes: 1

Sam Harwell
Sam Harwell

Reputation: 99869

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.

Upvotes: 1

jgallant
jgallant

Reputation: 11273

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

Upvotes: 34

Related Questions