[PYTHON] Was ist Eimersortierung? Meridem und Codebeispiel

Was ist Eimersortierung?

Eine Sortiermethode, die die Nummer jedes Elements zählt, die Array-Nummer angibt, in die das Element eingefügt werden soll, und diese der Reihe nach einfügt.

Es sind zwei Sequenzen vorzubereiten.

** (1) Zählerarray ** Zählen Sie, wie viele jedes Element enthält.

** (2) Array zum Setzen des Sortierergebnisses ** Bereiten Sie ein Array mit der gleichen Anzahl von Elementen vor wie das Array, das Sie sortieren möchten, und fügen Sie die in (1) angegebene Anzahl von Elementen ein.

Bereiten Sie 1,2,3 Behälter (Eimer) vor, legen Sie jedes Element hinein und zählen Sie die Anzahl. (Beispiel: 1 ist 3, 2 ist 2, 3 ist 1)

Ordnen Sie die Elemente der Reihe nach an.

[Referenz: 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)

Eimersortiermeridem

·verdienen

Intuitiv und leicht zu verstehen. Der schnellste rechnerische Sortieralgorithmus.

Effiziente Sortierung, wenn der Maximalwert klein ist und dieselbe Zahl viele Male dupliziert wird.

· Fehler

Wenn der Maximalwert des ursprünglichen Arrays groß ist, müssen Sie einen Bucket für diesen Maximalwert vorbereiten.

Es kann unter den folgenden Bedingungen nicht verwendet werden. ・ Nicht ganzzahlig (einschließlich Dezimalpunkt) ┗Weil der Eimer nicht vorbereitet werden kann

・ Maximalwert ist zu groß ┗Weil die Speichernutzung des Zählerarrays sehr groß wird

Beim Sortieren der Liste = [1,2,1,10] Es gibt keine 3-9, aber dafür müssen Sie einen Eimer vorbereiten.

Je kleiner der Maximalwert ist, desto schneller ist die Sortierung, aber ** je größer der Maximalwert, desto mehr Eimer müssen vorbereitet werden **.

python

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

  #Erstellen eines Zählerarrays. 0 Start. 0 ist immer 0
  for i in arr:
    arrc[i] += 1

  #Bereiten Sie ein Array vor, um das Sortierergebnis zu platzieren
  ans=[]

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

Verwenden Sie verlängern, um Arrays hinzuzufügen.

• Anhängen wird als einzelnes Element hinzugefügt, daher kann es hier nicht verwendet werden.

Bestätigung

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)

  #Erstellen eines Zählerarrays. 0 Start. 0 ist immer 0
  for i in arr:
    arrc[i] += 1

  #Bereiten Sie ein Array vor, um das Sortierergebnis zu platzieren
  ans=[]

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

Da jeder Eimer die gleiche Tiefe hat, fügen Sie ihn einfach hinzu.

Bestätigung

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

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

Wenn Sie von rechts einfügen, betrachten Sie den Fall, in dem das Element dupliziert wird, und setzen Sie die Stelle, an der das Element eingefügt wird, auf -1.

python

def bucket_sort3(arr):
  #Erstellen Sie ein Array mit so vielen Elementen wie die maximale Anzahl im Array.
  #Bei der Berechnung der kumulierten Summe-Zähle von 0, um auf das Element 1 zu verweisen.
  arrc = [0] *(max(arr)+1)

  #Zählen Sie die Anzahl der Elemente im Array
  #Fügen Sie der angegebenen Sequenznummer 1 hinzu
  for i in arr:
    arrc[i] += 1

  #Konvertieren Sie die Zählung in eine kumulative Summe.
  #Fügen Sie das vorherige Element zum aktuellen Element hinzu und ersetzen Sie es
  for j in range(1, len(arrc)) :
    arrc[j] = arrc[j] + arrc[j-1]
  
  #Erstellen Sie ein Array, um die Sortierergebnisse zu speichern. Die Anzahl der Elemente im Array entspricht der Anzahl des ursprünglichen Arrays
  arrs = [0]*len(arr)
  
  #Nehmen Sie die Elemente des ursprünglichen Arrays nacheinander heraus, finden Sie heraus, in welcher Nummer sie sich befinden, und fügen Sie sie ein.
  for i in arr:

    #Finden Sie heraus, welche Nummer ich einfügen soll. Da 0 für das sortierte Array nicht erforderlich ist,-1 Einsetzen
    #Wenn es mehrere gleiche Zahlen gibt, füllen Sie sie von ganz rechts nach links.
    arrs[arrc[i]-1] =i
   
    #In Anbetracht des Falls, in dem es mehrere gleiche Elemente gibt, reduzieren Sie die Anzahl Ihrer eigenen i-Elemente um eins aus der kumulierten Summe.
    arrc[i] -= 1

  return arrs

Bestätigung

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

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

Da im Lehrmaterial die Verwendung der kumulativen Summe vorgestellt wurde, habe ich versucht, den Prozess zu enträtseln, aber ehrlich gesagt ist es schwierig, ihn intuitiv zu verstehen.