Introduction aux 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 par division et conquête. Le tri rapide est un bon exemple d'algorithme qui tire le meilleur parti des caches CPU, en raison de sa nature de division et de conquête. L'algorithme Quicksort est l'un des algorithmes de tri les plus utilisés, en particulier pour trier les grandes listes et la plupart des langages de programmation l'ont implémenté. Dans l'algorithme Quicksort, les données d'origine sont divisées en deux parties qui sont triées individuellement puis fusionnées pour produire des données triées.
Considérons que le tableau (8, 6, 3, 4, 9, 2, 1, 7) doit être trié à l'aide du tri rapide.
Étapes pour implémenter des algorithmes de tri rapide
1. Choisissez un élément appelé pivot dans le tableau. Généralement, l'élément central est choisi comme pivot. Prenons 4 comme pivot.
2. Réorganisez le réseau en deux parties de 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, c'est-à-dire 8, Puisque 4 est le pivot et 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 choisissez 1 pour l'échange avec 8 donc après échange le tableau devient: 1, 6, 3, 4, 9, 2, 8, 7
- Choisissez l'élément suivant à gauche, c'est-à-dire 6, Puisque 4 est le pivot et 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 choisissez 2 pour échanger avec 6 donc après avoir échangé le tableau devient: 1, 2, 3, 4, 9, 6, 8, 7
- Maintenant que 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 terminé 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 pour implémenter des 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));
)
)
Production:
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 de 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 essentiel pour les performances.
- Le tri rapide est parallélisable: une fois l'étape initiale de partitionnement d'un tableau en régions plus petites, tous les sous-réseaux 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 de division et de conquête. Voici son analyse de complexité dans le meilleur, le moyen et le pire des cas:
- Meilleure complexité: si un tableau ou une liste contient n éléments, la première exécution aura besoin de O (n). Maintenant, le tri des deux sous-réseaux 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 du tri rapide est O (n log n).
- Complexité du pire des cas: le choix du premier ou du dernier entraînerait des performances dans le pire des cas pour les données triées ou triées de manière presque inverse. 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.
Articles recommandés
Ceci est un guide des algorithmes de tri rapide en Java. Nous discutons ici des étapes à mettre en œuvre, des avantages et de l'analyse de la complexité d'un algorithme de tri rapide en java avec le programme. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Tri d'insertion en Java
- boucle do-while en Java
- JComponent en Java
- Carrés en Java
- Échange en PHP
- Tri en C #
- Tri en Python
- Algorithme C ++ | Exemples d'algorithme C ++