Tri par compartiment en Java

La technique de tri utilisant laquelle les éléments du tableau donné sont répartis dans plusieurs nombres de compartiments pour trier chacun des compartiments en utilisant différents algorithmes de tri ou en utilisant un algorithme de tri de compartiment de manière récursive est appelée tri par compartiment en Java dont la complexité spatiale est O. (1), la complexité du pire des cas est O (n ^ 2), la complexité du meilleur cas est Omega (n + k) et la complexité moyenne des cas est thêta (n + k) et la technique de tri par compartiment pour trier les éléments donnés du tableau fonctionne à une vitesse plus rapide par rapport à d'autres algorithmes de tri et les éléments du tableau à trier à l'aide de l'algorithme de tri par compartiment doivent être uniformément répartis.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

La fonction permettant d'effectuer un tri par bucket en Java est la suivante :

public static int[] bucketsort(int[] array, int maximum_value)
{
int[] newbucket = new int[maximum_value + 1];
int[] sorted_array = new int[array.length];
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}

où array est le tableau d'entrée à trier à l'aide de l'algorithme de tri par compartiment, maximum_value est la valeur_maximale présente dans le tableau donné et sorted_array est le tableau résultant composé d'éléments triés.

Fonctionnement de l'algorithme de tri par compartiment en Java

Le fonctionnement de l'algorithme de tri Bucket en Java est le suivant :

• La première étape de l'algorithme de tri des buckets consiste à créer un tableau vide qui est considéré comme les buckets.
• La deuxième étape consiste à parcourir l'intégralité du tableau d'entrée dont les éléments doivent être triés et à ajouter chaque élément au bucket.
• La troisième étape consiste à trier chaque élément dans les buckets.
• La quatrième étape consiste à parcourir tous les éléments des buckets et à ajouter chacun d'eux dans l'ordre trié au tableau d'entrée d'origine.

Exemples de tri par buckets en Java

Voici des exemples ci-dessous :

Exemple n°1

Programme Java pour trier les éléments du tableau donné en implémentant un algorithme de tri par compartiment, puis afficher les éléments triés du tableau comme sortie à l'écran :

 Code :

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

Sortie :

Dans le programme ci-dessus, nous créons un tableau vide appelé newbucket qui est considéré comme un tableau de compartiments. Ensuite, nous créons un autre tableau vide appelé sorted_array pour stocker le tableau résultat. Ensuite, nous parcourons le tableau d'entrée pour ajouter chaque élément au tableau de compartiments. Ensuite, nous trions chaque élément du tableau de compartiments et ajoutons chaque élément trié dans l'ordre au tableau d'entrée d'origine. Ensuite, nous définissons une fonction pour trouver la valeur maximale dans le tableau d'entrée afin de trier le tableau donné à l'aide de la technique de tri par compartiment. Ensuite, la fonction principale est appelée dans laquelle nous affichons le tableau résultant. Le résultat est affiché dans l'instantané ci-dessus.

Exemple n°2

Programme Java pour trier les éléments du tableau donné en implémentant un algorithme de tri par compartiment, puis afficher les éléments triés du tableau comme sortie à l'écran :

Code :

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={ 60, 80, 50, 90, 30, 70, 20 };
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

Sortie :

Dans le programme ci-dessus, nous créons un tableau vide appelé nouveau bucket qui est considéré comme un tableau de buckets. Ensuite, nous créons un autre tableau vide appelé sorted_array pour stocker le tableau résultat. Ensuite, nous parcourons le tableau d'entrée pour ajouter chaque élément au tableau de compartiments. Ensuite, nous trions chaque élément du tableau de compartiments et ajoutons chaque élément trié dans l'ordre au tableau d'entrée d'origine. Ensuite, nous définissons une fonction pour trouver la valeur maximale dans le tableau d'entrée afin de trier le tableau donné à l'aide de la technique de tri par compartiment. Ensuite, la fonction principale est appelée dans laquelle nous affichons le tableau résultant. Le résultat est affiché dans l'instantané ci-dessus.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!