Algorithmes de tri rapide en Java

Le tri rapide en Java, également connu sous le nom de tri par échange de partition, est un algorithme de tri diviser pour régner. Le tri rapide est un bon exemple d’algorithme qui utilise au mieux les caches du processeur en raison de sa nature de division pour mieux régner. L'algorithme de tri rapide est l'un des algorithmes de tri les plus utilisés, notamment pour trier de grandes listes, et la plupart des langages de programmation l'ont implémenté. L'algorithme Quicksort divise les données originales en deux parties : triées individuellement puis fusionnées pour produire des données triées.

Commencez votre cours de développement de logiciels libres

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

Considérons que le tableau {8, 6, 3, 4, 9, 2, 1, 7} doit être trié à l'aide du tri rapide.

Étapes pour mettre en œuvre des algorithmes de tri rapide

1. Choisissez un élément appelé pivot dans le tableau. Généralement, l'élément médian est choisi comme pivot. Prenons 4 comme pivot.

2. Réorganisez le tableau en deux parties de telle sorte que les éléments inférieurs au pivot viennent avant le pivot et les éléments supérieurs au pivot apparaissent après le pivot. Les étapes suivantes sont suivies :

• Choisissez l'élément le plus à gauche, soit 8 ; puisque 4 est le pivot et que 8 est supérieur à 4, 8 doit être déplacé vers la droite de 4 ; sur le côté droit, nous laissons 7 car il est supérieur à 4 et choisissons 1 pour l'échanger avec 8 donc après avoir échangé le tableau devient : 1,6,3,4,9,2,8,7
• Choisissez l'élément suivant à gauche, soit 6 ; puisque 4 est le pivot et que 6 est supérieur à 4, 6 doit être déplacé vers la droite de 4 ; sur le côté droit, nous laissons 7,8 car ils sont supérieurs à 4 et choisissons 2 pour échanger avec 6 donc après avoir échangé le tableau devient : 1,2,3,4,9,6,8,7
• Maintenant puisque tous les éléments à gauche du pivot sont inférieurs au pivot et que tous les éléments à droite du pivot sont supérieurs au pivot, nous en avons fini avec 4 comme pivot.

3. Appliquez récursivement les étapes 1 et 2 pour le sous-tableau gauche (tableau avec des éléments inférieurs au pivot) et pour le sous-tableau droit (tableau avec des éléments supérieurs au pivot). Si le tableau ne contient qu'un ou zéro élément, alors le tableau est considéré comme assorti.

Programme de mise en œuvre d'algorithmes de tri rapide

Voici un programme Java pour trier un tableau d'entiers à l'aide d'un algorithme de tri rapide.

Code :

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

Sortie :

Avantages des algorithmes de tri rapide

Voici les avantages de l'algorithme de tri rapide :

• Excellente localité de référence : La localité de référence est la capacité d'un processeur à accéder au même emplacement mémoire de manière répétitive sur une courte période de temps. Le tri rapide en Java fournit une excellente localité de référence en raison du très petit nombre d'échecs de cache, ce qui sur les architectures modernes est critique pour les performances.
• Le tri rapide est parallélisable : Une fois l'étape initiale de partitionnement d'un tableau en régions plus petites terminée, tous les sous-tableaux individuels peuvent être triés indépendamment en parallèle. Pour cette raison, le tri rapide fonctionne mieux.

Analyse de complexité du tri rapide

Quicksort est un algorithme rapide et récursif qui fonctionne selon le principe diviser pour mieux régner. Voici son analyse de complexité en Meilleur, Moyen et Pire Cas :

• Complexité dans le meilleur des cas : Si un tableau ou une liste contient n éléments, alors la première exécution nécessitera O (n). Maintenant, le tri des deux sous-tableaux restants prend 2*O (n/2). Ceci conclut la complexité de O (n logn) dans le meilleur des cas.
• Complexité moyenne des cas : Le cas moyen de tri rapide est O (n log n).
• Pire complexité des cas : Choisir le premier ou le dernier entraînerait les pires performances pour les données presque triées ou presque inversées. Le tri rapide effectue O (n ^ 2) dans le pire des cas.

 En Java, Les tableaux. La méthode Sort () utilise un algorithme de tri rapide pour trier un tableau.

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!