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