[PYTHON] Qu'est-ce que le tri par godets? Merideme et exemple de code

Qu'est-ce que le tri par godets?

Une méthode de tri qui compte le nombre de chaque élément, spécifie le numéro de tableau dans lequel placer l'élément et les insère dans l'ordre.

Il y a deux séquences à préparer.

** (1) Réseau de compteurs ** Comptez le nombre de chaque élément.

** (2) Array pour mettre le résultat du tri ** Préparez un tableau avec le même nombre d'éléments que le tableau que vous souhaitez trier et insérez le nombre d'éléments spécifié dans (1).

Préparez 1,2,3 conteneurs (seaux), mettez-y chaque élément et comptez le nombre. (Exemple: 1 est 3, 2 est 2, 3 est 1)

Disposez les éléments dans l'ordre.

[Référence: wikipedia](https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD% E3% 83% BC% E3% 83% 88)

Godet tri méridème

·mérite

Intuitif et facile à comprendre. L'algorithme de tri le plus rapide sur une base informatique.

Tri efficace lorsque la valeur maximale est petite et que le même nombre est dupliqué plusieurs fois.

·Démérite

Si la valeur maximale du tableau d'origine est élevée, vous devez préparer un compartiment pour cette valeur maximale.

Il ne peut pas être utilisé dans les conditions suivantes. ・ Non-entier (y compris la virgule décimale) ┗Parce que le seau ne peut pas être préparé

・ La valeur maximale est trop grande ┗Parce que l'utilisation de la mémoire du tableau de compteurs devient énorme

Lors du tri de la liste = [1,2,1,10] Il n'y a pas de 3-9, mais vous devez préparer un seau pour cela.

Plus la valeur maximale est petite, plus le tri est rapide, mais ** plus la valeur maximale est élevée, plus il y a de seaux à préparer **.

python

def bucket_sort(arr):
  arrc = [0]*(max(arr)+1)

  #Création d'un tableau de compteurs. 0 début. 0e est toujours 0
  for i in arr:
    arrc[i] += 1

  #Préparez un tableau pour mettre le résultat du tri
  ans=[]

  for j in range(1, len(arrc)):
    ans.extend([j]*arrc[j])
  
  return ans 

Utilisez extend pour ajouter des tableaux.

• Append est ajouté en tant qu'élément unique, il ne peut donc pas être utilisé ici.

Vérification

list=[8,3,1,2,3,3,10,7,6,7]
bucket_sort(list)

#[1, 2, 3, 3, 3, 6, 7, 7, 8, 10]

python

def bucket_sort2(arr):
  arrc = [0]*(max(arr)+1)

  #Création d'un tableau de compteurs. 0 début. 0e est toujours 0
  for i in arr:
    arrc[i] += 1

  #Préparez un tableau pour mettre le résultat du tri
  ans=[]

  for j in range(1, len(arrc)):
    ans = ans+[j]*arrc[j]
  
  return ans

Puisque chaque seau a la même profondeur, ajoutez-les simplement.

Vérification

list=[8,3,1,2,3,3,10,7,6,7]
bucket_sort2(list)

#[1, 2, 3, 3, 3, 6, 7, 7, 8, 10]

Si vous insérez à partir de la droite, considérez le cas où l'élément est dupliqué et définissez l'endroit où l'élément est inséré par -1.

python

def bucket_sort3(arr):
  #Créez un tableau avec autant d'éléments que le nombre maximum dans le tableau.
  #Lors du calcul de la somme cumulée-Comptez à partir de 0 pour faire référence à l'élément de 1.
  arrc = [0] *(max(arr)+1)

  #Compter le nombre d'éléments dans le tableau
  #Ajouter 1 au numéro de séquence spécifié
  for i in arr:
    arrc[i] += 1

  #Convertissez le nombre en une somme cumulée.
  #Ajouter l'élément précédent à l'élément actuel et le remplacer
  for j in range(1, len(arrc)) :
    arrc[j] = arrc[j] + arrc[j-1]
  
  #Créez un tableau pour stocker les résultats du tri. Le nombre d'éléments dans le tableau est le même que le tableau d'origine
  arrs = [0]*len(arr)
  
  #Retirez les éléments du tableau d'origine un par un, recherchez le numéro dans lequel ils se trouvent et insérez-les.
  for i in arr:

    #Découvrez quel numéro i insérer. Puisque 0 n'est pas requis pour le tableau trié,-1 Insérer en place
    #S'il y a plusieurs numéros identiques, remplissez-les du côté le plus à droite vers le côté gauche.
    arrs[arrc[i]-1] =i
   
    #Considérant le cas où il y a plusieurs éléments identiques, réduisez le nombre d'éléments de votre propre i par un à partir de la somme cumulée.
    arrc[i] -= 1

  return arrs

Vérification

list=[8,3,1,2,3,3,10,7,6,7]
bucket_sort3(list)

#[1, 2, 3, 3, 3, 6, 7, 7, 8, 10]

Depuis que le matériel pédagogique a présenté comment utiliser la somme cumulative, j'ai essayé de démêler le processus, mais honnêtement, il est difficile à comprendre intuitivement.