Waarom zijn de grenzen van mijn quicksort-implementatie verkeerd?

Ik probeer quicksort in python te implementeren:

def partition(ls):
  if len(ls) == 0:
    return 0
  pivot = ls[0]
  i = 0
  j = 1
  while j < len(ls):
    if ls[j] <= pivot:
      i += 1
      temp = ls[i]
      ls[i] = ls[j]
      ls[j] = temp
    j += 1
  ls[0] = ls[i]
  ls[i] = pivot
  return i

assert(partition([1,2]) == 0)
assert(partition([3,2]) == 1)
assert(partition([3,2,1,4,5]) == 2)
assert(partition([]) == 0)
assert(partition([45]) == 0)

def sort(ls):
  if len(ls) == 0:
    return
  pivotIndex = partition(ls)
  sort(ls[0:pivotIndex])
  sort(ls[(pivotIndex + 1):len(ls)])

ls = [54,1,3,2,4,3,5,4]
sort(ls)
print ls

Op basis van mijn assert-statements weet ik dat mijn partitie-algoritme goed werkt.

Mijn sorteerfunctie retourneert echter foutieve resultaten. Dit codefragment wordt afgedrukt

[4, 1, 3, 2, 4, 3, 5, 54]

Wat moeten de grenzen zijn van de recursieve oproepen om te sorteren? Ik probeer de sublijst links van het draaipunt en de sublijst rechts van het draaipunt te splitsen. Beide bevatten niet het draaipunt zelf.

0
Uw assert-statements tonen alleen aan dat partition het spilelement op de juiste index plaatst, niet dat de partitie correct is. Ook kopieer je de lijsten tijdens het slicen (de ls [start: eind] ) constructie, dat soort mist het punt van het implementeren van een interne quicksort. U moet de begin- en eindindex maken van het bereik waarover u wilt werken als parameters voor sorteer() .
toegevoegd de auteur millimoose, de bron
U kunt ook enkele afdrukken s in uw code plaatsen om te zien wat uw indices doen, waardoor u kunt achterhalen wat ze verkeerd doen.
toegevoegd de auteur BrenBarn, de bron
Vreemdelingen vragen om fouten in uw code te herkennen, is niet productief. Er zijn talloze implementaties van quicksort die er zijn. Ik zou willen voorstellen om door je code te stappen en zijn gedrag te vergelijken met die van een bekende-goede implementatie.
toegevoegd de auteur Oliver Charlesworth, de bron

2 antwoord

sort(ls[0:pivotIndex])
sort(ls[(pivotIndex + 1):len(ls)])

De slicing kopieert een deel van de lijst, dus in de recursieve aanroepen wijzigt u de oorspronkelijke lijst niet. Alleen de eerste partitie wijzigt dus de lijst.

0
toegevoegd

Some known-good sorts in Python with optional Cython, including Quicksort. BTW, check out the performance comparison; you'll likely find that Quicksort isn't as attractive as the built-in Timsort: http://stromberg.dnsalias.org/~strombrg/sort-comparison/

0
toegevoegd