Fehler bei der Auswahl eines mittleren Pivot-Elements in Python schnelle Sortierung

Question

Ich habe eine kurze Sortiercode geschrieben. Es funktioniert gut, außer dass ein Element unsortiert bleibt. Ich habe versucht zu debuggen, aber vergeblich. Könnten Sie mir bitte helfen, den möglichen Fehler zu lokalisieren?

Hier ist der Code.

def qsort(l,start,end): 

    if start >= end : 
     return 
    i,j = start, end 
    pivot = (start + (end - start)/2)  

    while i<=j: 
     while(l[i] < l[pivot]): 
      i+=1 
     while(l[j] > l[pivot]): 
      j-=1 
     if(i<=j): 
      l[i],l[j] = l[j],l[i] 
      i+=1 
      j-=1 

    qsort(l,start,j) 
    qsort(l,i,end) 

    return l 

    a = [67,89,45,23,15,19,1,14,100] 
    print qsort(a,0,len(a)-1) 

Die Ausgabe des obigen Codes ist [1, 14, 15, 23, 19, 45, 67, 89, 100]. Aus irgendeinem Grund sind die Positionen 23 und 19 nicht vertauscht.

Allerdings, wenn ich eine zufällige Dreh mit Pivot = random.randint wählen (fst, lst) Aussage, die ich ein vollständig sortiert bekommen list.Could jemand pls den Grund dafür erklären?

Answer 1

Sie könnten diese Referenzimplementierungen hilfreich finden, während Sie versuchen, Ihre eigenen zu verstehen.

---

Rückkehr eine neue Liste:

def qsort(array): 
    if len(array) < 2: 
     return array 
    head, *tail = array 
    less = qsort([i for i in tail if i < head]) 
    more = qsort([i for i in tail if i >= head]) 
    return less + [head] + more 

---

eine Liste an Ort und Stelle Reihenfolge:

def quicksort(array): 
    _quicksort(array, 0, len(array) - 1) 

def _quicksort(array, start, stop): 
    if stop - start > 0: 
     pivot, left, right = array[start], start, stop 
     while left <= right: 
      while array[left] < pivot: 
       left += 1 
      while array[right] > pivot: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -= 1 
     _quicksort(array, start, right) 
     _quicksort(array, left, stop) 

---

Generierung sortiert Objekte eines iterable:

def qsort(sequence): 
    iterator = iter(sequence) 
    head = next(iterator) 
    try: 
     tail, more = chain(next(iterator), iterator), [] 
     yield from qsort(split(head, tail, more)) 
     yield head 
     yield from qsort(more) 
    except StopIteration: 
     yield head 

def chain(head, iterator): 
    yield head 
    yield from iterator 

def split(head, tail, more): 
    for item in tail: 
     if item < head: 
      yield item 
     else: 
      more.append(item)