Python 3: Einfügung Sort Vergleichszähler

Ich muss einen Zähler für Gesamtvergleiche für meine Insertion Sort-Programm hinzufügen, aber ich weiß nicht, warum ich insgesamt 0 Vergleiche bekomme!Python 3: Einfügung Sort Vergleichszähler

Ich weiß, dass die Vergleiche Ausgabe 15 (für meine spezifischen Array) sollte nicht 0

Dies ist mein Code so weit:

def insertionSort(values): 
    k = 0 
    n = len(values) - 1 
    comparisons = 0 
    while k+1 <= n: 
     i = k 
     while values[i] > values[i+1]: 
      temp = values[i] 
      values[i] = values[i+1] 
      values[i+1] = temp 
      comparisons += 1 #I think this is wrong 
     k = k + 1 
    return comparisons, values

Was mache ich falsch?

Quelle

2016-05-17 a_guy

Ich habe nur Ihren Code überprüft und es dient nicht zum Sortieren [7,5,4,6].

Hier ist eine modifizierte Version -

def insertionSort_mod(values): 
    k = 0 
    n = len(values) - 1 
    comparisons = 0 
    while k+1 <= n: 
     i = k+1 
     curr_val = values[i] 
     comparisons += 1 
     while i>0 and values[i-1] > curr_val: 
      values[i] = values[i-1] 
      i=i-1 
      comparisons += 1 
     values[i] = curr_val 
     k = k + 1 
    return comparisons, values 

print insertionSort_mod([1, 2, 3, 55, 5, 6, 8, 7, 9, 111])

Gibt folgendes:

(15, [1, 2, 3, 5, 6, 7, 8, 9, 55, 111])

In Ihrem Kontext k + 1 sollte der aktuelle Index sein, so sollte ich k + 1 sein und sollte die verglichen werden vorheriger Wert i-1

Quelle

2016-05-17 05:52:07

Ich habe gerade versucht, Ihre modifizierte Version danke, aber wenn ich mit dem Array [1, 2, 3, 55, 5, 6, 8, 7, 9, 111] testen, gibt es mir eine Gesamtvergleiche von '6' sollten 15 sein. –

Die Vergleichsvariable wird nur dann inkrementiert, wenn es einen Swap gibt, also gibt sie nicht genau die Anzahl der Vergleiche an. Um es vollständig zu melden, müssen Sie Ihren Zähler vor der inneren Weile und innerhalb der inneren while-Schleife erhöhen - beide Orte. 'während k + 1 <= n: i = k + 1 curr_val = Werte [i] Vergleiche + = 1 während i> 0 und Werte [i-1]> curr_val: Werte [i] = Werte [i-1] i = i-1 Vergleiche + = 1' Tun Sie diese Änderung, die es tun sollte ... –

gerade meine Antwort bearbeitet bitte überprüfen ... –

Hope this arbeitet

def insertion(a,length): 
    count=0 
    for i in range(1,length): 
     key=a[i] 
     jj=i 
     while(jj>0 and a[jj-1]>key): 
      a[jj]=a[jj-1] 
      jj=jj-1 
      count += 1 
     a[jj]=key 
    print count

Die Nr. Swaps wäre gleich der Anzahl der Elemente, für die Sie die Elemente mit der while-Schleife verschieben. So könnten Sie eine Flag-Variable innerhalb der while-Schleife verwenden, um zu überprüfen, ob die Schleife für jedes Element ausgeführt wird, und die Zählervariable jedes Mal um 1 zu erhöhen, wenn die Flag-Variable Swapping anzeigt.

Quelle

2016-05-17 05:38:32

Python 3: Einfügung Sort Vergleichszähler

Antwort

Verwandte Themen