Trier à la bulle le nombre total de comparaisons et d'échanges.

Question

J'ai ce code pour le tri à bulles en c++. Tout d'abord, il génère des nombres aléatoires et les place dans un tableau. Ensuite, j'appelle ma fonction bubbleSort, qui effectue le tri. Tout fonctionne bien. Cependant, j'étais curieux de savoir comment trouver le nombre total de comparaisons et de permutations de nombres que le tri à bulles effectue ? J'ai créé un entier CountBubbleSort pour les comparaisons. Cependant, je ne sais pas dans quelle partie de mon code je dois l'incrémenter. Je pensais l'ajouter après la deuxième boucle for, à l'intérieur de la première. J'espère que vous comprenez ce que je veux dire. Est-ce que c'est correct ou non ? Le nombre de comparaisons définit cette formule n*(n-1))/2. Et avec les swaps, c'est 3*(n-1). Mais comment puis-je l'implémenter dans mon code ? Merci pour votre aide.

void swap(double *xp, double *yp)
{
    double temp = *xp;
    *xp = *yp;
    *yp = temp;
}

double *Data;
double* A;
double n, temp;

void generate(int _n, const char *_file);
void read(const char *_file);   
void printArray(double arr[], int n); 
void bubbleSort(double arr[], int n);

int main()
{
    int m;
    int CountBubbleSort = 0;

    srand(time(NULL));
    cout << "Amount of random numbers you want: ";
    cin >> m;
    cout << "Generating random data ..." << endl;
    generate(m, "duom.txt");
    cout << "Reading data" << endl;
    read("duom.txt");
    A = new double[n];

    for (int i = 0; i < n; i++) {
        A[i] = Data[i];
    }

    cout << "Randomly generated array" << endl;
    printArray(A, n);

    // Bubble Sort
    bubbleSort(A, n);

    cout << "Array after bubble sort" << endl;
    printArray(A, n);

    return 0;
}

void bubbleSort(double arr[], int n)
{
    bool swapped;
    for (int i = 0; i < n - 1; i++)
    {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        // Should I add CountBubbleSort += i here or not?
        if (swapped == false)
            break;
    }
}

void printArray(double arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << endl;
    }
}

Answer 1

Il s'agit d'une modification relativement simple :

• Incrémenter le compte de comparaison avant le if déclaration
• Incrémenter le compteur de swap dans le fichier if déclaration

Prends-en deux. int& paramètres pour le comptage, comme ceci :

void bubbleSortCounted(double arr[], int n, int& countComparisons, int& countSwaps);

Le code qui incrémente les compteurs ressemblerait à ceci :

countComparisons++;
if (arr[j] > arr[j + 1])
{
    countSwaps++;
    swap(&arr[j], &arr[j + 1]);
    swapped = true;
}

L'appel de la main() ressemblerait à ceci :

int cmp = 0, swp = 0;
bubbleSort(A, n, cmp, swp);
std::cout << cmp << " comparisons, " << swp << " swaps" << std::endl;

Answer 2

Cependant, j'étais curieux de savoir comment trouver le nombre total de comparaisons et de permutations de chiffres que le tri à bulles effectue ? J'ai créé un entier CountBubbleSort pour les comparaisons. Cependant, je ne sais pas dans quelle partie de mon code je dois l'incrémenter.

Il y a exactement une ligne dans votre bubbleSort() où vous comparez réellement deux éléments dans le tableau, il est donc logique que si vous voulez compter le nombre de fois où vous comparez des éléments, vous devez incrémenter le compteur soit immédiatement avant, soit immédiatement après la comparaison.