There is some difference between these two ways of Bubble Sort°

Asked

Viewed 72 times

0

Is there any difference between these codes?

that:

    void bubble_sort(int array[], int n) 
    {
    int count = -1;
    while (count != 0)
    {
        count = 0;
        int aux;
        for(int i = 0; i < n - 1; i++)
        {
            if(array[i] > array[i + 1])
            {
                aux = array[j];
                array[j] = array[j + 1];
                array[j + 1] = aux;
                count++;
            }
        }
        n--;
    }
    }

and that:


     void bubbleSort(int array[], int n) 
       { 
       int i, j, aux; 
       for (i = 0; i < n-1; i++) 
       { 
           for (j = 0; j < n-i-1; j++) 
           { 
               if (arr[j] > arr[j+1]) 
               {
                 aux = array[i];
                 array[i] = array[i + 1];
                 array[i + 1] = aux;
               } 
           }
       }

*mainly in a matter of time

c bubblesort
  • 1

    The best case complexity in the first code is O(n), while in the second code it is O(n 2). This means that, in an already ordered vector, the first program will only run once through the list, while the second will run n times through sublists of size 1 to n.

  • Grateful, you have removed my doubts

2 answers

0

In some cases the first version, with while, may end with fewer iterations than the second.

The second version is with some errors, how to use the i instead of j when switching positions in the array.

  • Grateful for the response, I will make the appropriate corrections.

  • But there is doubt.... in this case it is preferable to the first? For ending with fewer iterations

  • Yes. The algorithm is the same. It’s just kind of silly to iterate over and over again without seeing if it’s already ordered. Imagine a sample with half a million items, and by chance almost all in order... And reversing the direction of the loops would be more in agreement, starting from the bottom and rising as the bubbles generally do

0


There are authors who call the first version "optimized". But one might call the latter "dumb" or at least "naive" --- to be politically correct.

If you’re going to be sorting the giant vector there for hours and there comes a time when during a loop you don’t change anyone from place means that the vector is already in order and you’ll never change anyone from place. And so you continue on the loop down and comparing and comparing will no longer change anything: is just wasting time until you reach the end, no more bubbles --- Bubbles

Because these common implementations of Bubblesort() use indexes from the beginning and memory has increasing addresses so this should be Anchorsort since the elements sink as an anchor instead of rising as in general bubbles do. :)

Browser other questions tagged c bubblesort

You are not signed in. Login or sign up in order to post.