Auswahlsortierungsalgorithmus

Was ist Auswahlsortierung?

Der Selection Sort-Algorithmus unterteilt das Array in zwei Teile: den sortierten Teil und den unsortierten Teil. Der sortierte Teil ist zunächst leer und der unsortierte Teil enthält alle Elemente. Der Algorithmus funktioniert, indem er das kleinste (oder größte, abhängig von der Sortierreihenfolge) Element aus dem unsortierten Teil findet und es durch das erste Element des unsortierten Teils austauscht. Dieser Vorgang wird fortgesetzt, bis das gesamte Array sortiert ist.

Algorithmusschritte

1. Beginnen Sie mit dem ersten Element im Array und gehen Sie davon aus, dass es das kleinste ist.
2. Vergleichen Sie dieses Element mit den anderen Elementen im Array.
3. Wenn Sie ein kleineres Element finden, tauschen Sie es mit dem ersten Element aus.
4. Gehen Sie zum nächsten Element im Array und wiederholen Sie den Vorgang für die verbleibenden unsortierten Elemente.
5. Setzen Sie diesen Vorgang fort, bis das gesamte Array sortiert ist.

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

Durchgang 1:

• Das kleinste Element zwischen Index 0 und dem Rest des Arrays ist 11.
• Wir tauschen 64 gegen 11.

Array nach dem ersten Durchgang: [11, 25, 12, 22, 64]

Durchgang 2:

• Konzentrieren Sie sich nun auf das Subarray, beginnend mit Index 1. Das kleinste Element zwischen 25, 12, 22, 64 ist 12.
• Wir tauschen 25 gegen 12.

Array nach dem zweiten Durchgang: [11, 12, 25, 22, 64]

Durchgang 3:

• Das kleinste Element zwischen 25, 22, 64 ist 22.
• Wir tauschen 25 gegen 22.

Array nach dem dritten Durchgang: [11, 12, 22, 25, 64]

Durchgang 4:

• Das Subarray enthält jetzt 25, 64. Da sie bereits in Ordnung sind, ist kein Austausch erforderlich.

Endgültiges sortiertes Array: [11, 12, 22, 25, 64]

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted part
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

Sortiertes Array: [11, 12, 22, 25, 64]

Zeitliche Komplexität der Auswahlsortierung:

• Bester Fall: O(n²)

• Durchschnittlicher Fall: O(n²)

• Worst Case: O(n²)

Auch wenn die Auswahlsortierung bei kleinen Datensätzen eine gute Leistung erbringt, ist sie für größere Arrays nicht ideal, da ihre zeitliche Komplexität O(n²) beträgt. Es ist jedoch einfach zu implementieren und kann in Fällen nützlich sein, in denen der Speicher ein Problem darstellt, da die Auswahlsortierung direkt erfolgt (kein zusätzlicher Speicher erforderlich).

Vor- und Nachteile

Vorteile:

• Einfach zu verstehen und umzusetzen.

• Leicht gut bei kleinen Listen.

• Benötigt keinen zusätzlichen Speicher, da das Array an Ort und Stelle sortiert wird.

Nachteile:

• Ineffizient für große Datensätze aufgrund seiner O(n²) zeitlichen Komplexität.

• Es handelt sich nicht um einen stabilen Sortieralgorithmus, was bedeutet, dass gleiche Elemente möglicherweise ihre Reihenfolge relativ zueinander nicht beibehalten.

Das obige ist der detaillierte Inhalt vonAuswahlsortierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!