Sorting algorithms more efficient than bubble sort

Question

I have written this algorithm to sort a list using bubble sort. Is this the most efficient way to sort a list?
If not, why?
What makes it less efficient and what are the alternatives present?

def BubbleSort(List):
     for i in range(len(List)-1):
          for Number in range(len(List)-1):
               if List[Number] > List[Number+1]:
                    List[Number], List[Number+1] = List[Number+1], List[Number]

print(BubbleSort([5,2,1,4,3])

Thanks!

Answer 1

In your above algorithm, if the length of your array is 5, it will execute the inner if statement 25 times. In general when you will have a list of n size, it will for sure do n^2 operations excluding the for loop and swapping.

For a list of size 10^6, it will be 10^12 operations atleast. C or C++ do around 10^9 operations per second. So this code of yours will take 10^3 seconds which is more than half an hour. So that's very much inefficient.

There are better sorting algorithms which you can use instead of bubble sort as they are faster than this.

• Merge Sort
• Quick Sort
• Heap Sort

A lot of other techniques are also there but these are most common used.

Apart from that, you don't need to implement these algorithms as one of the most efficient one is already implemented in standard library of mostly each language from C to Rust. You can just use that implementation and even pass you own comparator function if you want.