Introduction
QuickSort est un algorithme de tri Diviser-pour-Régner. Il fonctionne en sélectionnant un élément « pivot » dans le tableau et en partitionnant les autres éléments en deux sous-tableaux, selon qu'ils sont inférieurs ou supérieurs au pivot. Les sous-tableaux sont ensuite triés de manière récursive. La complexité moyenne de QuickSort est O(n log n). Il est important de noter que QuickSort n'est pas un tri stable, c'est-à-dire que les positions relatives des éléments de tri égaux ne sont pas nécessairement conservées.
Importer la classe Arrays
Dans cette étape, vous devez importer la classe java.util.Arrays. Cette classe contient plusieurs méthodes pour manipuler les tableaux qui seront utilisées pour convertir les tableaux int en String.
import java.util.Arrays;
Définir la méthode partition()
Définissez une méthode d'aide appelée partition(). La méthode partition() prendra un tableau arr, un index de début low et un index de fin high en entrée. La méthode partition() sélectionnera un élément comme pivot et partitionnera les éléments de sorte que tous les éléments inférieurs à l'élément pivot soient à gauche du pivot et que tous les éléments supérieurs au pivot soient à droite du pivot. L'élément pivot sera placé à sa position correcte.
La méthode partition() retournera l'index de l'élément partitionné. L'élément partitionné est la position où l'élément pivot est placé.
public static int partition(int[] arr, int low, int high) {
// Sélectionnez l'élément pivot
int pivot = arr[high];
int i = (low - 1); // Index de l'élément plus petit et indique la bonne position du pivot trouvé jusqu'à présent
for (int j = low; j <= high - 1; j++) {
// Si l'élément actuel est plus petit ou égal au pivot
if (arr[j] <= pivot) {
i++; // Incrémentez l'index de l'élément plus petit
// Échangez arr[i] et arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Échangez arr[i + 1] et arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Retournez l'index de partition
}
Définir la méthode quicksort()
Définissez une méthode de tri nommée quicksort(). La méthode quicksort() prendra un tableau arr, un index de début low et un index de fin high en entrée. La méthode quicksort() triera de manière récursive le tableau arr[].
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi est l'index de partitionnement, arr[p] est maintenant
// à la bonne place
int pi = partition(arr, low, high);
// Triez de manière récursive les éléments avant
// la partition et après la partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Créer et assigner un tableau d'entiers
Créez et affectez des tableaux d'entiers à trier au champ arr.
int[] arr = {7, 9, 1, 2, 10, 15, 6};
Implémenter le tri rapide (QuickSort)
Appelez la méthode quickSort() avec le champ arr en tant que paramètre d'entrée, ainsi que l'index initial et final du tableau. Triez et affichez le tableau à l'aide de la méthode Arrays.toString(arr).
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
Tester avec plusieurs tableaux
Testez votre implémentation de tri rapide en utilisant des tableaux présentant diverses caractéristiques.
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
Sélectionner aléatoirement le pivot
Dans cette étape, nous devons sélectionner aléatoirement le pivot à chaque itération pour éviter le pire cas. Pour ce faire, nous modifierons la méthode partition() et remplacerons la ligne suivante :
int pivot = arr[high];
par cette ligne :
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
Tester avec un élément pivot aléatoire
Testez votre implémentation de tri rapide en utilisant des éléments pivot aléatoires.
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
Gérer les cas limites
Dans cette étape, nous allons aborder les cas limites que le tri rapide peut gérer. Décrivez ces cas limites sous forme de tableaux d'entiers.
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
Code complet
Le code complet du tri rapide en Java Lab est donné ci-dessous.
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Implémentation du tri rapide en Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}
Résumé
Ce laboratoire a fourni un guide étape par étape pour implémenter l'algorithme de tri rapide en Java. Nous avons appris que le pivot est une étape cruciale dans le tri rapide et que différentes techniques de sélection d'un pivot peuvent affecter les performances de l'algorithme. Le tri rapide est le mieux adapté pour trier de grandes quantités de données. La complexité temporelle dans le pire des cas du tri rapide est O(N^2), tandis que sa complexité temporelle moyenne et dans le meilleur des cas est O(NLogN).
