Wie funktioniert das Austauschen von Elementen in diesem Sortieralgorithmus?

Question

Dies ist ein Python-Sortieralgorithmus, der die aktuelle Indexnummer mit dem aktuellen Element, das den kleinsten Wert enthält, vertauscht.

Meine Frage ist, wenn der Strom wird Element 1 dann würde nicht array[index]=array[1], die natürlich nicht Wert 1, sondern Wert 3 im Array ist.

ich es ausgeführt, und der Code funktioniert und dreht die Indexnummer, die Wert halten 5 und der einen Haltewert 1.

Also, wenn es funktioniert Ich gehe davon aus, dass Python als array[index]=array[2] natürlich lese ich dies nicht tun versteh das, denn und das Element ist 1.

Der Code funktioniert Ich habe es in einem Buch, aber ich versuche es mehr zu verstehen.

def selection_sort(array): 
    for index in range(0,len(array)-1): 
     value=array[index] 
     current=index 
     #Algorithm go's here 
     for element in range(index+1,len(array)): 
      if array[element]<array[current]: 
       current=element 
     array[index]=array[current] 
     array[current]=value 

     print('\tResolving element[',index,'] to',array) 

array=[5,3,1,2,6,4] 
print('Selection Sort...\nArray:',array) 
selection_sort(array) 
print('Array:',array) 

Answer 1

Was redest du da eigentlich selection sort. Der Hauptalgorithmus ist ziemlich einfach:

for i from 1 to n-1 
{ 
    Find smallest element in ith to nth entries. 
    Exchange this element with ith entry. 
} 

So funktioniert die Art und Weise Auswahl Sortieralgorithmus ist durch das nächste kleinste Element auswählen und in der richtigen Position platzieren. Wenn ich den Algorithmus etwas mehr kurz zu erläutern, dann wird es aussehen wie folgt:

• Schritt 1 - Stellen Sie MIN auf Position 0
• Schritt 2 - Suchen Sie das kleinste Element in der Liste
• Schritt 3 - Swap mit dem Wert an der Stelle MIN
• Schritt 4 - MIN Erhöhen zum nächsten Elemente zeigen
• Schritt 5 - Wiederholen, bis die Liste sortiert ist

Also, vorausgesetzt der Code, den Sie arbeitet wie folgt:

def selection_sort(array): 
    # running through each element of the array 
    for index in range(0,len(array)-1): 
     value=array[index] # storing the current element in a variable 
     current=index  # storing the index of the current element 

     # search in the sub-array (from index+1 to end of the array) 
     # for the minimum element 
     for element in range(index+1,len(array)): 
      if array[element]<array[current]: 
       current=element 

     # swap the minimum value found with the value at location index 
     array[index]=array[current] 
     array[current]=value 
     # at the end of each iteration, minimum value is moved to position index 

Blick in die folgende Animation (aus Wikipedia):

Ein kurzes Beispiel: Diese example zeigt Auswahl Art sehr Nun, Sie können über das Beispiel nachdenken.

Answer 2

Ich denke, dass Sie den Algorithmus nicht vollständig verstehen. Der Algorithmus verwendet eine sehr zweideutige Benennung für die Variablen. Sowohl element als auch current beziehen sich auf Indizes im Array.

Ich nehme an, dass dies ein selection sort Algorithmus ist. Die Funktionsweise dieses Algorithmus besteht darin, das nächstkleinste Element auszuwählen und an die entsprechende Position zu setzen.

Die Art, wie sie es implementiert haben, besteht darin, mithilfe der Indizes zu bestimmen, welche Werte im Array ausgetauscht werden sollen. Wie oben erwähnt, war die Verwendung von element als Variablenname auf ihrer Seite nicht großartig, da sie nicht das Element im Array selbst ist, sondern der Index des Elements.

In der für sie einfach bestimmen, welcher Wert im Array bewegt werden soll. Sie tauschen noch nicht aus. Nachdem die for-Schleife abgeschlossen ist, werden die Werte vertauscht.

Hoffe, das hilft.