[PYTHON] Détails du tri rapide et exemples de code

Qu'est-ce que le tri rapide?

Faites pivoter (référencez) les éléments et placez les éléments restants d'avant en arrière selon qu'ils sont plus grands ou plus petits que le pivot.

Le travail de décision du pivot et d'agencement des éléments disposés avant et après celui-ci est répété.

Confirmez quand les éléments deviennent un.

** ▼ Lors du réglage du premier élément à pivoter ** 

Flux de tri rapide

1. Déterminez le pivot et triez-le d'avant en arrière selon qu'il est plus grand ou plus petit que cette valeur. La valeur et l'emplacement du pivot sont fixes.
2. Exécutez à nouveau le processus 1 pour la baie précédente.
3. Exécutez à nouveau le processus 1 pour la baie arrière.
4. Le pivot est de plus en plus fixe dans les processus de 2 et 3, et finalement tous les éléments sont fixes.

## Lorsque l'extrême gauche est pivot

python

##Spécifiez pivot et gauche + pivot+Une fonction (rapide) qui crée un tableau trié sur le côté droit_sort）
def quick_sort(arr):
  #Le tri se termine lorsqu'il n'y a qu'un seul élément (le tri n'est pas nécessaire s'il y a moins de deux éléments)
  if len(arr) <= 1 :
    return arr
  #Spécifiez la valeur de pivot
  p = arr[0]

  #Effectue le processus de division basé sur le pivot. fonction div
  arr1, arr2 = div(p, arr[1:])

  #Combinez les tableaux divisés en référence au pivot.
  #Rapide sur le tableau divisé lui-même_Effectuez un tri.
  return quick_sort(arr1) + [p] + quick_sort(arr2)



##Une fonction qui crée des tableaux de gauche et de droite basés sur le pivot(div)
def div(p, arr):
  #Définissez une variable pour placer les tableaux de pivot gauche et droit
  left, right=[], []

  for i in arr:
    #Stocker à gauche si plus petit que le pivot
    if i < p:
      left.append(i)
    #S'il est au-dessus du pivot, rangez-le sur le côté droit
    else:
      right.append(i)

  #Sortir respectivement les tableaux gauche et droit
  return left, right

Il est plus intuitif et facile à comprendre que le tri par fusion.

• Attention Si la valeur la plus à gauche est définie sur pivot, la quantité de calcul augmentera si les valeurs sont déjà disposées par ordre décroissant.

Pour cette raison, il est recommandé de déterminer le pivot de manière aléatoire.

## Tri rapide lorsque le pivot est déterminé aléatoirement Utilisez le choix aléatoire de numpy (tableau).

Modifiez le pivot de la fonction quick_sort ci-dessus comme suit.

python

import numpy as np
  p = random.choice(arr)

quick_sort

import numpy as np

def quick_sort2(arr):
  #Le tri se termine lorsqu'il n'y a qu'un seul élément (le tri n'est pas nécessaire s'il y a moins de deux éléments)
  if len(arr) <= 1 :
    return arr

  #Spécifiez la valeur de pivot
  p = random.choice(arr)

  #Effectue le processus de division basé sur le pivot. fonction div
  arr1, arr2 = div(p, arr[1:])

  #Combinez les tableaux divisés en référence au pivot.
  #Rapide sur le tableau divisé lui-même_Effectuez un tri.
  return quick_sort(arr1) + [p] + quick_sort(arr2)