Tri bulle à l'aide d'un tableau dynamique

Introduction

Dans ce laboratoire, nous allons apprendre à écrire un algorithme pour implémenter la technique de tri bulle en C++. Le tri bulle est l'une des techniques de tri les plus populaires et simples, où nous comparons deux éléments adjacents dans un tableau et échangeons leurs positions s'ils ne sont pas correctement organisés.

Déclarez les variables et les fichiers d'en-tête requis

Nous allons créer un nouveau fichier nommé main.cpp dans le répertoire ~/projet en utilisant la commande suivante :

touch ~/projet/main.cpp

Nous commençons tout d'abord par déclarer les variables et les fichiers d'en-tête nécessaires au programme. Dans cette étape, nous inclurons le fichier d'en-tête iostream et définirons l'espace de noms std.

#include<iostream>
using namespace std;

Déclarez une fonction pour implémenter l'algorithme de tri bulle général

Ici, nous allons déclarer une fonction "bubble_sort" dans le programme C++ qui accepte le tableau à trier et la taille du tableau. La fonction contiendra l'implémentation de la technique de tri bulle à l'aide de boucles for, d'échanges et d'instructions if/else.

int bubble_sort(int n,int array[]){
    int temp;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j--){
            if(array[j]>array[j+1]){
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
            }
        }
    }
return 0;
}

Déclarez une fonction pour implémenter l'algorithme de tri bulle optimisé

Dans le tri bulle optimisé, nous vérifierons à chaque passage si des éléments ont été échangés ou non. Si aucun échange n'est intervenu lors du dernier passage, cela signifie que nous avons trié le tableau. Dans cette étape, nous allons implémenter la fonction "bubble_sort" pour implémenter un algorithme de tri bulle optimisé. La fonction accepte le tableau à trier et la taille du tableau.

int bubble_sort(int n,int array[]){
    int temp, flag;
    for(int i=0;i<n-1;i++){
        flag = 0;
        for(int j=0;j<n-i-1;j++){
            if(array[j]>array[j+1]){
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                flag=1;
            }
        }
        if(flag==0){
            break;
        }
    }
    return 0;
}

Définissez la fonction principale

Ici, nous allons définir la fonction principale dans laquelle nous déclarerons le tableau à trier et sa taille. Dans cette étape, nous appellerons également la fonction "bubble_sort" pour trier le tableau par ordre croissant.

int main(){

    int arr[]={5,6,9,2,3};
    int n = sizeof(arr)/(sizeof(arr[0]));
    bubble_sort(n,arr);
    cout<<"Elements after sorting of the array:- "<<endl;
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

Compiler et exécuter le code

Dans cette étape, nous allons compiler et exécuter le code dans le terminal du système Ubuntu. Pour compiler le code, tapez la commande suivante :

g++ ~/projet/main.cpp -o main

Pour exécuter le code, tapez la commande suivante :

./main

Résumé

Dans ce laboratoire, nous avons appris avec succès à implémenter le tri bulle à l'aide d'un tableau dynamique en C++. Nous avons également appris une technique de tri bulle optimisée qui fonctionne efficacement pour certains tableaux sélectionnés mais efficaces. En suivant le tutoriel ci-dessus, vous pouvez implémenter la technique de tri bulle pour trier un tableau par ordre croissant ou décroissant à l'aide d'un tableau dynamique en C++.