Tag 20: Sortieren in Hackerrank, Python

Question

vor kurzem habe ich HackerRank 30 Tage Code-Herausforderung und lösen Sie die Herausforderung mit Python. Aber am Tag 20 (über den Bubble Sort-Algorithmus) kann ich es nicht lösen. Das ist die link zur Aufgabe in Hackerrank und unten ist mein Code.

import sys 

n = int(raw_input().strip()) 
a = map(int, raw_input().strip().split(' ')) 
numSwap = 0 

for first in a: 
    b = a[a.index(first)+1:] 
    for second in b: 
     if first > second: 
      a[a.index(first)] = second 
      a[a.index(second)] = first 
      numSwap += 1 

firstElement = a[0] 
lastElement = a[len(a)-1] 
print "Array is sorted in %d swaps\nFirst Element: %s\nLast Element: %d " %(numSwap, firstElement, lastElement) 

Der Eingang für diesen Code ist:

Das Ergebnis des Codes ist:

Array is sorted in 3 swaps 
First Element: 3 
Last Element: 1 

Das erwartete Ergebnis:

Array is sorted in 3 swaps. 
First Element: 1 
Last Element: 3 

die Frage ist, warum es nicht wie erwartet funktioniert hat? Welcher Teil des Codes ist falsch? Vielen Dank.

Answer 1

Das Problem mit Ihrem Code und der Grund, warum es nicht wie erwartet funktioniert, weil:

for first in a: 
b = a[a.index(first)+1:] 
for second in b: 
    if first > second: 
     a[a.index(first)] = second 
     a[a.index(second)] = first 
     numSwap += 1 

Sie die Elemente in der ersten Anordnung tauschen, a, aber aktualisieren nicht die gleiche in das zweite Array, b.

Hier ist eine Lösung, die einwandfrei funktionieren soll:

import sys 

n = int(raw_input().strip()) 
a = map(int, raw_input().strip().split(' ')) 
# Write Your Code Here 
numberOfSwaps = 0 
for i in xrange(n): 
    for j in xrange(n-1): 
     if a[j] > a[j+1]: 
      a[j], a[j+1] = a[j+1], a[j] 
      numberOfSwaps += 1 
    if not numberOfSwaps: 
     break 


print "Array is sorted in", numberOfSwaps, "swaps." 
print "First Element:", a[0] 
print "Last Element:", a[n-1] 

Prost :)

Answer 2

ich endlich wissen, was der Fehler in meinem Code.

for first in a: 
    b = a[a.index(first)+1:] 
    for second in b: 
     if first > second: 
      a[a.index(first)] = second 
      a[a.index(second)] = first 
      numSwap += 1 

so unter diesem Code Vertauschen der Elemente an ihren ursprünglichen Platz zurück:

a[a.index(first)] = second 
a[a.index(second)] = first 

sollte eine Variable erstellt hat eines der Elemente enthalten.

smaller = a.index(first) 
bigger = a.index(second) 
a[smaller] = second 
a[bigger] = big 

und mein zweiter Fehler ist die erste for den Algorithmus von der neu aktualisierte Liste wodurch die 2 als das erste Element nicht wiederholen.

der korrekte Code ist wie von TheDarkKnight geschrieben.

Hier ist eine Lösung, die einwandfrei funktionieren sollte:

import sys das fehlerhafte Teil

n = int(raw_input().strip()) 
a = map(int, raw_input().strip().split(' ')) 
# Write Your Code Here 
numberOfSwaps = 0 
for i in xrange(n): 
    for j in xrange(n-1): 
     if a[j] > a[j+1]: 
      a[j], a[j+1] = a[j+1], a[j] 
      numberOfSwaps += 1 
    if not numberOfSwaps: 
     break 


print "Array is sorted in", numberOfSwaps, "swaps." 
print "First Element:", a[0] 
print "Last Element:", a[n-1] 

Prost :)