Algorithme de tri rapide Diviser pour régner efficace

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.

Skills Graph

Importez 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éfinissez 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éfinissez 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éez et affectez 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émentez le tri rapide

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));

Testez 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électionnez 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;

Testez 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).