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


** ▼ Image de tri Bucket ** Pour la séquence [1,3,2,1,2,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.

image.png

[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


** ▼ Exemples d'inconvénients ** (comprenez explicitement que des seaux inutiles se produiront)

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.

seau: 1 2 3 4 5 6 7 8 9 10
Nombre d'éléments: 2 1 0 0 0 0 0 0 0 1

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 **.


## Exemple de code de tri de bucket

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.

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]

### Comment ne pas utiliser extend

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]

### Comment déterminer la position d'insertion à partir de la somme cumulée Convertit le tableau de compteurs en une somme cumulée et trouve un emplacement pour insérer l'élément spécifié.

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.

Recommended Posts

Qu'est-ce que le tri par godets? Merideme et exemple de code
[Python] Python et sécurité-① Qu'est-ce que Python?
[Python] Qu'est-ce que la série pandas et DataFrame?
Quelle est la différence entre «pip» et «conda»?
Que comparez-vous avec Python et ==?
Qu'est-ce que le remboursement égal du principal et des intérêts et le remboursement égal du principal et des intérêts?
Quelle est la différence entre Unix et Linux?
Qu'est-ce que l'espace de noms
Qu'est-ce que copy.copy ()
Qu'est-ce que Django? .. ..
Qu'est-ce que POSIX
Qu'est-ce que Linux
Qu'est-ce que le klass?
Qu'est-ce que SALOME?
Qu'est-ce que Linux?
Qu'est-ce que python
Qu'est-ce que l'hyperopt?
Qu'est-ce que Linux
Qu'est-ce que pyvenv
Qu'est-ce que __call__
Qu'est-ce que Linux
Qu'est-ce que Python
Quelle est la différence entre usleep, nanosleep et clock_nanosleep?
Qu'est-ce que pip et comment l'utilisez vous?
Vérifiez quel est le code de caractère pour tous les fichiers sous le répertoire Python et sortie