CODEWITHSUNDEEP
pythonalgorithmpython-3.xbubble-sort
Chandan Nayak
Chandan Nayak

Reputation: 10887

Bubble sort - variations (Performace time) - python

I have 3 variations of bubble sort method in python, Link for the code - github

I was testing the performance for them by using this

From the output:

Time taken[bubbleSort]: list size 1000 --> 0.0876331 seconds
Time taken[bubbleSort1]: list size 1000 --> 0.0575149 seconds
Time taken[bubbleSort2]: list size 1000 --> 0.000144 seconds 

Time taken[bubbleSort]: list size 3000 --> 0.8421631 seconds
Time taken[bubbleSort1]: list size 3000 --> 0.605628 seconds
Time taken[bubbleSort2]: list size 3000 --> 0.000545 seconds 

Time taken[bubbleSort]: list size 5000 --> 2.421416 seconds
Time taken[bubbleSort1]: list size 5000 --> 1.6900301 seconds
Time taken[bubbleSort2]: list size 5000 --> 0.000668 seconds

I think, in bubbleSort1() i am not stopping the loop by checking if swapped, which is done in bubbleSort2() which might be the reason for the time difference. Not sure about bubbleSort().

Need a clear picture on what is the exact reason of time differences in 3 methods here. Thanks !

Upvotes: 1

Views: 862

Answers (2)

pepr
pepr

Reputation: 20760

As Pola wrote, with sorting (and other) algorithms, there are always the worst case, the best case, and something in between. For the bubble sort, the best case is when it is already sorted, the worst case is when the sequence is reversed.

There is a term named time complexity -- marked as big O, that roughly says the quality of the algorithm based on the size of the solved problem (here number of sorted elements). It is based on the assumption that you can think that some trivial operation(s) take a constant time to be done. Then you think in terms of how much of such steps must be done to solve the problem.

When having the array of n elements, then the most naive approach to bubble sort needs n times n steps (not considering that the part of the array is already sorted). When sorting only the rest of the file, you need about (n*n)/2 steps. This is only when you consider the worst case.

When you add detection for stopping when nothing was swapped (that is, everything already sorted), you get much better results in some cases -- here is when you get the best cases. The minimum number of steps is n for the sorted sequence.

Not going into details, the time complexity of the bubble sort is O(n^2), and it says that bubble sort is one of the worst sorting algorithms that you can use. The best sorting algorithms (in memory, single processor) have the time complexity O(n log(n)).

Read here https://en.wikipedia.org/wiki/Time_complexity and here http://bigocheatsheet.com/

Upvotes: 0

sair
sair

Reputation: 832

Comparing Bubblesort1() and Bubblesort2()

maximum passes can be n-1 , but consider a case in which after 2 passes 
the array is sorted . so bubblesort1() will waste cpu time on other n-1-2 passes
but bubblesort2() will stop the loop and hence it is efficient.

Upvotes: 1

Related Questions