Is this bubble sort correct?

2

People are reading C ++'s "Programming principles and practice using c ++ (2nd edition)" book. You have a good exercise at the beginning talking to make a program that orders the given numbers. I did it using BubbleSort, I burned a lot of neurons doing more, I think I did it. I wanted to know if he has any errors or some situation that's wrong, I've done some testing and it seems to work. Thank you.

Code below.

#include <iostream>

using namespace std;

void bubbleSort(int * my_integer_array_pointer /*pointer to original array*/,unsigned int array_size)
{
    int tempChanger = 0;
    unsigned int Swaps = 0;
    unsigned int i = 0;


    for (i = 0; i < (array_size -1); i++) //iterate "my_integer_array_pointer", "array_size-1" times
    {
        if (*(my_integer_array_pointer+i) > *(my_integer_array_pointer+i+1)) // if left number is greater than right number, swapp then
        {
            tempChanger = *(my_integer_array_pointer+i);
            *(my_integer_array_pointer+i) = *(my_integer_array_pointer+i+1);
            *(my_integer_array_pointer+i+1) = tempChanger;
            Swaps++; //count the number of swapped numbers
        }
    }
    if (Swaps > 0) // if swap more than 0 times, need to iterate list again
    {
        bubbleSort(my_integer_array_pointer,array_size);
    }
    /*
    else = list is already sorted, stop function.
    */
}

int main()
{
    cout << "Please type the amount of numbers you want to sort:" << endl;
    int my_integer_array_size;
    cin >> my_integer_array_size;
    int my_integer_array[my_integer_array_size] = {};

    for (int i = 0; i < my_integer_array_size; i++) //iterator used to assign a value to each element of "my_integer_array" with "cin"
    {
       cout << "Please type the " << i+1 << " number" << endl;
       cin >> my_integer_array[i];
    }

    cout << endl;
    bubbleSort(my_integer_array,my_integer_array_size);

    cout << "The ordered array is below :" << endl;
    for (unsigned int i = 0; i < sizeof(my_integer_array) / sizeof(int); i++) //iterator to show the results
    {
        cout << my_integer_array[i] << endl;
    }

    return 0;
}
    
asked by anonymous 09.07.2015 / 19:13

1 answer

1

Your code is correct, implemented bubble sort well, but be very careful in the declaration of the vector, because as you did can lead to a series of errors. Remember that when the binary code (the result of the compilation) is performed the separation of memory for each variable (based on the type of each) is done before data entry or anything else. So pay close attention to this detail because defining the size of the vector by means of a variable that will store the size desired by the user is a very risky practice, since it is not possible to know, before execution, the contents of the reserved memory spaces to my_integer_array_size and this can happen to separate a vector smaller than the size that the user will type.

But for all we have a solution. To use a variable-sized vector, just like you did, you need to use dynamic memory artifacts, it changes little and does not disturb your logic at all:

#include <iostream>

using namespace std;

void bubbleSort(int * my_integer_array_pointer /*pointer to original array*/,unsigned int array_size)
{
    int tempChanger = 0;
    unsigned int Swaps = 0;
    unsigned int i = 0;


    for (i = 0; i < (array_size -1); i++) //iterate "my_integer_array_pointer", "array_size-1" times
    {
        if (*(my_integer_array_pointer+i) > *(my_integer_array_pointer+i+1)) // if left number is greater than right number, swapp then
        {
            tempChanger = *(my_integer_array_pointer+i);
            *(my_integer_array_pointer+i) = *(my_integer_array_pointer+i+1);
            *(my_integer_array_pointer+i+1) = tempChanger;
            Swaps++; //count the number of swapped numbers
        }
    }
    if (Swaps > 0) // if swap more than 0 times, need to iterate list again
    {
        bubbleSort(my_integer_array_pointer,array_size);
    }
    /*
    else = list is already sorted, stop function.
    */
	//return my_integer_array_pointer;
}

int main()
{
    cout << "Please type the amount of numbers you want to sort:" << endl;
    int my_integer_array_size;
    cin >> my_integer_array_size;
    int * my_integer_array;

	my_integer_array= new int [my_integer_array_size]; //ALOCAÇÃO DINÂMICA DE MEMÓRIA PARA SEU VETOR

    for (int i = 0; i < my_integer_array_size; i++) //iterator used to assign a value to each element of "my_integer_array" with "cin"
    {
       cout << "Please type the " << i+1 << " number" << endl;
       cin >> my_integer_array[i];
    }

    cout << endl;
    bubbleSort(my_integer_array,my_integer_array_size);

    cout << "The ordered array is below :" << endl;
	//AGORA COM O TAMANHO CONHECIDO E JÁ DEFINIDO PODE-SE USAR A VARIAVEL COM O TAMANHO ESCOLHIDO PELO USUÁRIO COMO CONDIÇÃO DE PARADA DO for
    for (unsigned int i = 0; i < my_integer_array_size; i++) //iterator to show the results 
    {
        cout << my_integer_array[i] << endl;
    }
	delete [] my_integer_array; //IMPORTANTE!! SEMPRE QUE ALOCAR MEMORIA DINAMICAMENTE LEMBRE-SE DE LIBERAR A MESMA AO FINAL DA EXECUÇÃO DO CÓDIGO
    return 0;
}
    
22.08.2015 / 14:55