[JAVA] Gymnastique algorithmique 9

Quick Sort

La description

Le tri rapide est un algorithme qui utilise le fameux algorithme de tri "Divide and Conquer". C'est tellement célèbre que si vous n'avez pas entendu ce qu'est le tri rapide, ici pour référence.

Solution

Runtime Complexity O(nlogn) Si vous choisissez pivot comme l'extrême gauche du tableau

  1. Le tableau est déjà trié dans le même ordre
  2. Le tableau est déjà trié dans l'ordre inverse
  3. Tous les éléments sont les mêmes À l'exception des trois conditions, c'est O (nlogn), mais si vous rencontrez cette condition, ce sera O (n ^ 2).

Memory Complexity O(logn) Triez le côté droit et le côté gauche séparément du pivot. À ce stade, puisqu'une fonction récursive est utilisée Il est O (logn) car il consomme de la mémoire sur la pile.

Flux d'algorithme approximatif

  1. Sélectionnez un élément pivot dans le tableau. Sélectionnez le premier élément du tableau comme Pivot.
  2. Permutez afin que les valeurs inférieures à Pivot soient sur le côté gauche de Pivot et les valeurs supérieures à Pivot soient sur le côté droit de Pivot.
  3. Vous pouvez réorganiser de manière récursive les sous-tableaux droit et gauche de Pivot.

la mise en oeuvre

quickSort.java


class quickSort{

  public int partition(int[] arr, int low, int high) {

    int pivot_value = arr[low];
    int i = low;
    int j = high;

    while (i < j) {
      while( i <= high && arr[i] <= pivot_value) i++;
      while(arr[j] > pivot_value) j--;

      if (i < j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    
    arr[low] = arr[j];
    arr[j] = pivot_value;

    return j;
  }
  
  public void quick_sort_recursive(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);
      quick_sort_recursive(arr, low, pivot - 1);
      quick_sort_recursive(arr, pivot + 1, high);
    }
  }

  public void quick_sort(int[] arr) {
    quick_sort_recursive(arr, 0, arr.length - 1);
  }
}  

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes