Is there really more efficiency in the Cocktail Sort than in the Bubble Sort?

Question

Is there really more efficiency in the Cocktail Sort than in the Bubble Sort?

Navigation

#1 by (6 votes)

2

I have these two codes the following which represents the bubble sort is the following:

lista = [5, 4, 3, 2, 1]

def bubble_sort(A):
    #Se comienza con el primer elemento
    for i in range(len(A) - 1):
        for j in range(len(A) - 1):
            if A[j+1] < A[j]:
                A[j], A[j+1] = A[j+1], A[j]
    return(A)


print(bubble_sort(lista))

The second one which belongs to the cocktail sort :

lista = [5, 4, 3, 2, 1]

def cocktail_sort(A):
    #Se comienza desde el ultimo elemento
    for k in range(len(A) - 1, 0, -1):
        swapped = False
        for i in range(k, 0, -1):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swapped = True
        #Se comienza con el primer elemento
        for i in range(k):
            if A[i] > A[i+1]:
                A[i], A[i+1] = A[i+1], A[i]
                swapped = True

        if not swapped:
            return A


print(cocktail_sort(lista))

The cocktail sort is supposed to be more efficient than the bubble sort , but at the time of the bubble sort it takes 54 steps while that the other one takes 77 steps, then, Is an improvement really taking place?

python algoritmos

asked by Luis Miguel 16.07.2017 в 05:21

source

1 answer

Obtain individual body tag elements Use order_by in Django

score 6 · Accepted Answer

The cocktail sort algorithm or bidirectional bubble has the same average complexity as the simple bubble method: O (n 2 ).

What is pursued with it is to reduce the number of iterations and the necessary comparisons in relation to one of the typical problems of the simple bubble method known as "hares and turtles":

The efficiency of the bubble method is directly related to the distance and the direction in which an element has to be moved so that it is ordered.
The elements that have to be moved in the same direction on which the method iterates on the array move relatively fast since they benefit from the possibility of making several exchanges per iteration.
The elements that have to be moved in the opposite direction to which the method iterates move very slowly since only one position can be moved for each iteration.

To alleviate the above, the bi-directional bubble method was designed. The idea is simple, for each iteration we go through the array alternately in both directions. This implies that each iteration of the bidirectional bubble method should be taken as two of the simple bubble method. Its usefulness and improvement will only be visible in cases where there are "turtle" elements. Let's take the implementation of the two methods you propose with some improvements like the one proposed by @CodigoFasil:

def bubble_sort(A):
    for i in range(len(A) - 1):
        for j in range(len(A) - i - 1):
            if A[j+1] < A[j]:
                A[j], A[j+1] = A[j+1], A[j]


def cocktail_sort(A):
    for k in range(len(A)//2):
        swapped = False
        for i in range(1+k, len(A)-k):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swapped = True                
        if not swapped:
            break

        swapped = False
        for i in range(len(A)-k-1, k, -1):
            if A[i] < A[i-1]:
                A[i], A[i-1] = A[i-1], A[i]
                swapped = True
        if not swapped:
            break

For your example ( lista = [5, 4, 3, 2, 1] ) using the cocktail method does not seem to be much better because there are no turtle cases (you go through the array from right to left):

Bubble method:

Iterations: 4

Comparisons: 10



Bidirectional bubble method:

Iterations: 2

Comparisons: 12

Now, what happens in the case where turtle elements exist as in lista = [11, 1, 2, 3, 4, 6, 7, 8, 9] where the "11" has to be moved upstream:

Bubble method:

Iterations: 8

Comparisons: 36



Bidirectional bubble method:

Iterations: 1

Comparisons: 16

In this case totally favorable for the bidirectional bubble method if we see important differences.

Between both ends there are many possibilities and it will not always have a better performance than the simple bubble. Its real improvement is quite marginal compared to other methods so it is used for academic purposes almost exclusively in reality.