Quicksort Python Sortier Probleme

Question

def quicksort(mas): 
    if mas: 
     mid = mas[0] 
     menshe = [i for i in mas[1:] if i < mid] 
     bolshe = [i for i in mas[1:] if i >= mid] 
     return quicksort(menshe) + [mid] + quicksort(bolshe) 
    else: 
     return mas 

n = int(input()) 
mas = input().split() 
print(*quicksort(mas)) 

es auf einigen Tests nicht besteht, zum Beispiel

input: 
3 
8 21 22 
output: 
21 22 8 

wie Sie den Code zu verbessern?

Answer 1

Ihr Code kann sehr gut funktionieren. Ich muss es noch testen. (aber jetzt, wo ich es scheint scheint)

Ihr Fehler ist, dass Sie Ihre erste Eingabe verwerfen. Also sollten Sie Ihren eigenen Code wie folgt verwenden:

mas = input().split() 
print(*quicksort(mas)) 

Sie benötigen nur einen Eingang.

Auch Sie sortieren Strings, die nicht unbedingt Zahlen, so dass Sie möchten, dies zu tun:

mas = input().split() 
print(*quicksort([int(item) for item in mas])) 

Answer 2

Ihre Quicksort-Implementierung scheint korrekt zu sein, aber Sie haben vergessen, Ihre Eingabe in Ganzzahlen zu konvertieren. Sie sortieren Strings.

Als eine Randnotiz: Vergessen Sie nicht, dass Pivot-Auswahl-Strategie ist sehr wichtig in QuickSort-Algorithmus. Ihr Schema "erstes Element als Drehpunkt" ähnelt Lomuto partition scheme, das für geordnete oder fast geordnete Sequenzen leicht zu O(n^2) degradiert.