What’s wrong with the Bubble Sort algorithm?

Question

I’m creating a code with the algorithm Bubble Sort, but when compiling I get errors, which are:

   In function 'int main()': 16 33  
    [Error] cannot convert 'int*' to 'int**' for argument '1' to 'int bubbleSort(int**, int*, int*, int*)' In function 'int bubbleSort(int**, int*, int*, int*)': 23    13  
    [Error] invalid types 'int**[int*]' for array subscript 23  23  
    [Error] invalid types 'int**[int*]' for array subscript 24  16  
    [Error] cannot convert 'int**' to 'int*' for argument '1' to 'void troca(int*, int*)

Just follow my code:

#include <stdio.h>
#include <stdlib.h>

void troca(int *a, int *b);
int bubbleSort(int *vec[5],int *a, int *b,int *qtd);

int main(){
    int vet[5] = {4,7,1,13,5};
    int i, j, qtd;
    printf("[");
    for(int i= 0; i < 5; i++){
        printf(" %d",vet[i]);
    }
    printf(" ]");

    bubbleSort(&vet[5], &i,&j, &qtd);

}

int bubbleSort(int *vec[5],int *a, int *b, int *qtd){
    for(*a = 0; *a < 5; *a++){
        for(*b = *a + 1; *b <= 5; *b++){
            if(*vec[a] > *vec[b]){
                troca(&a,&b);
                qtd++;
            }
        }
    }
    printf("[");
    for(int i = 0; i < 5; i++){
        printf("%d ",vec[i]);
    }
    printf("]");
    printf("Trocas: %d",*qtd);
}

void troca(int *a, int *`insira o código aqui`b){
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

Answer 1

Law attentively what your IDE is telling you:

 In function 'int main()': 16 33  
    [Error] cannot convert 'int*' to 'int**' for argument '1' to 'int bubbleSort(int**, int*, int*, int*)' In function 'int bubbleSort(int**, int*, int*, int*)': 23    13  
    [Error] invalid types 'int**[int*]' for array subscript 23  23  
    [Error] invalid types 'int**[int*]' for array subscript 24  16  
    [Error] cannot convert 'int**' to 'int*' for argument '1' to 'void troca(int*, int*)

Your problem is this:

Invalid conversion problems of a type pointer integer for a pointer pointer of the same type and different types in its function bubbleSort() and in its function troca().

I suggest you stop trying to understand and or make this algorithm and read from the basics the following subjects:

• a) Logical Reasoning
• b) Development with C from basic to advanced

After these readings and actually being aware and knowing what it does, you should read about the following subject in order to be able to understand this algorithm:

• Algorithm Design and Analysis

But to kill your curiosity I will leave the original algorithm of bubbleSort, goes below.

Pseudocode

procedure bubbleSort( A : lista de itens ordenaveis ) defined as:
  do
    trocado := false
    for each i in 0 to length( A ) - 2 do:
      // verificar se os elementos estão na ordem certa
      if A[ i ] > A[ i + 1 ] then
        // trocar elementos de lugar
        trocar( A[ i ], A[ i + 1 ] )
        trocado := true
      end if
    end for
  // enquanto houver elementos sendo reordenados.
  while trocado
end procedure

In C:

void bubble_sort (int vetor[], int n) {
    int k, j, aux;

    for (k = 1; k < n; k++) {
        printf("\n[%d] ", k);

        for (j = 0; j < n - 1; j++) {
            printf("%d, ", j);

            if (vetor[j] > vetor[j + 1]) {
                aux          = vetor[j];
                vetor[j]     = vetor[j + 1];
                vetor[j + 1] = aux;
            }
        }
    }

The above algorithm compiles normally and even returns the expected result (an ordered vector) but it traverses the vector completely even when it has already been ordered. I mean the tie is more internal.

If you ask to print the iteration variables k and j, you will have the following output:

[1] 0, 1, 2, 3, 4, 5, 6,
[2] 0, 1, 2, 3, 4, 5, 6,
[3] 0, 1, 2, 3, 4, 5, 6,
[4] 0, 1, 2, 3, 4, 5, 6,
[5] 0, 1, 2, 3, 4, 5, 6,
[6] 0, 1, 2, 3, 4, 5, 6,
[7] 0, 1, 2, 3, 4, 5, 6,

Sources:

• EXAMPLES OF USE OF BUBBLE_SORTE

Answer 2

Dude, I think you’ve even created enough code to try to do the method. I made one in college, where it shows how the vector is in each sorting step, if you want to use example or "motivation" to fit in your feel free ( I believe you will be able to find where you missed also when analyzing the code ).

Bubble Method:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

main()
{
    int vet[10], i, fim, aux, trocou;

    srand(time(NULL));

    for (i = 0; i < 10; i++)
    {
        vet[i] = rand() % 10 + 1;
        printf("%d  ", vet[i]);
    }
    getchar();

    // ordenação bolha

    for (fim = 8; fim >= 0; fim--) // número de passos (controle do final de cada passo)
    {
        trocou = 0; // não trocou
        for (i = 0; i <= fim; i++) // número de possíveis trocas
        {
            if (vet[i] > vet[i + 1])
            {
                aux = vet[i];
                vet[i] = vet[i + 1];
                vet[i + 1] = aux;
                trocou = 1; // efetuou uma troca
            }
        }

        if (!trocou) // se não trocou, sair.
            break;

        // mostrar o vetor após cada passo
        printf("\n");
        for (i = 0; i < 10; i++)
        {
            printf("%d  ", vet[i]);
        }
        printf("   Passo %d", 9 - fim);
        getchar();
    }

    printf("\n\n\nFim...");
    getchar();
}

Answer 3

It is not worth detailing everything that is wrong, corrected program.

#include <stdio.h>
#include <stdlib.h>

void troca(int *a, int *b);
int bubbleSort(int *vec);

int main(void)
{
  int i;
  int vet[5] = { 4, 7, 1, 13, 5 };

  printf("*\n");
  printf("* antes [");
  for (int i = 0; i < 5; i++)
    printf(" %d",vet[i]);
  printf(" ]\n");

  bubbleSort(vet);

  printf("*\n");
  printf("* depois [");
  for (int i = 0; i < 5; i++)
    printf(" %d",vet[i]);
  printf(" ]\n");

  printf("*\n");
}

int bubbleSort(int* vec)
{
  int i, j, qtd = 0;

  for (i = 0; i < 4; i++)
  {
    for (j = i + 1; j < 5; j++)
    {
      if (vec[i] > vec[j])
      {
        troca(&vec[i], &vec[j]);
        qtd++;
      }
    }
  }

  printf("*\n");
  printf("* trocas: %d\n", qtd);
}

void troca(int* a, int* b)
{
  int aux;
  aux = *a;
  *a = *b;
  *b = aux;
  printf("* trocou %d por %d\n", *b, *a);
}