Vergleichen von Vergleichen mit der Einfügesortierung

Question

Ich habe den Auftrag, die Gesamtvergleiche beim Sortieren eines Arrays zu zählen. Gegeben sei das Integer-Array {8, 2, 1, 4, 3, 5}, ich beginne mit dem zweiten Element von links, vergleiche es mit dem ersten, wechsle sie, vergleiche dann das dritte Element mit den beiden vorherigen und usw., um festzustellen, wo sich jedes Element befinden sollte.

Ich berechne insgesamt 15 Vergleiche, aber die richtige Vergleichszahl ist 10. Ich weiß, dass Sortierung dieses Array durch Auswahl ist 15 Vergleiche, so wie und warum die Anzahl der Vergleiche bei der Verwendung von Insertion sort in dieser unterscheiden Beispiel?

Answer 1

Ihr Verständnis davon, wie die Einfügesortierung funktioniert, ist falsch.

Diese Pseudocode für einen Insertionsort:

mark first element as sorted 
for each unsorted element 
    'extract' the element 
    for i = lastSortedIndex to 0 
    if currentSortedElement > extractedElement 
     move sorted element to the right by 1 
    else: insert extracted element 

Initial-Array: [8, 2, 1, 4, 3, 5]

Vergleich 1: 2 < 8 Array: [2, 8, 1, 4, 3, 5]

Vergleich 2: 1 < 8 Array: [2, 1, 8, 4, 3, 5]

Vergleich 3: 1 < 2 Array: [1, 2, 8, 4, 3, 5]

Vergleich 4: 4 < 8 Array: [1, 2, 4, 8, 3, 5]

Vergleich 5: 4 > 2 Array: [1, 2, 4, 8, 3, 5]

Vergleich 6: 3 < 8 Array: [1, 2, 4, 3, 8, 5]

Vergleich 7: 3 < 4 Array: [1, 2, 3, 4, 8, 5]

Vergleich 8: 3 > 2 Array: [1, 2, 3, 4, 8, 5]

Vergleich 9: 5 < 8 Array: [1, 2, 3, 4, 5, 8]

Vergleich 10: 5 > 4 Array: [1, 2, 3, 4, 5, 8]

Sortieren!