• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie - Algorytm QuickSort

VPS Starter Arubacloud
0 głosów
373 wizyt
pytanie zadane 6 stycznia 2021 w Python przez maciej12 Nowicjusz (120 p.)

Witajcie,

Prosiłbym o pomoc, gdyż męczę się już z tym kupę czasu i nie mogę dojść do winy problemu. Zadanie polega na implementacji algorytmu QuickSort, który zwróci nam posortowaną tablicę, nie zmieniając nic w tabeli wejściowej. Mógłby ktoś spojrzeć i powiedzieć mi gdzie popełniłem błąd? Algorytm w tym przypadku sortuje prawidłowo do pewnego momentu, lecz z niewiadomych mi przyczyn nie przerywa w tym momencie i próbuje jeszcze kilkukrotnie dalej sortować dając na wyjściu zły wynik. O dziwo problem nie występuje, gdy nie próbuję zrobić wewnątrz funkcji kopii listy i operuję na oryginalnej tablicy.

Z góry bardzo dziękuję :) 

from typing import List
Y = [2, 25, 9, 14, 1, 3, 10]  #tablica do posortowania

def quicksort(I: List[int], start: int, stop: int) -> List[int]:
    copy_I = I[:]  #kopia listy na której będę operował
    i = start
    j = stop
    pivot = copy_I[(start + stop) // 2]

    while i <= j:
        while copy_I[i] < pivot:
            i += 1
        while copy_I[j] > pivot:
            j -= 1
        if i <= j:
            copy_I[i], copy_I[j] = copy_I[j], copy_I[i]
            i += 1
            j -= 1

    if start < j:
        quicksort(copy_I, start, j)
    if i < stop:
        quicksort(copy_I, i, stop)
    return copy_I

print(quicksort(Y,0,len(Y)-1))

 

komentarz 6 stycznia 2021 przez tmar1212 Bywalec (2,600 p.)
A po co to kopiowanie?

1 odpowiedź

+1 głos
odpowiedź 6 stycznia 2021 przez adrian17 Ekspert (344,100 p.)
    if start < j:
        quicksort(copy_I, start, j)
    if i < stop:
        quicksort(copy_I, i, stop)

Te funkcje nic nie robią, bo - jak sam napisałeś - quicksort() tworzy kopię i ją zwraca. Musisz uzyć wartość zwracaną przez funkcję.

komentarz 6 stycznia 2021 przez adrian17 Ekspert (344,100 p.)

(jako alternatywa, możesz napisać "prawdziwego" quicksorta edytującego listę bez kopiowania, a następnie napisać zewnętrzną funkcję która jedyne co robi to kopię:

def quicksort_copying(lst):
    copy = lst[:]
    quicksort(copy)
    return copy

)

komentarz 6 stycznia 2021 przez maciej12 Nowicjusz (120 p.)

Czyli krótko mówiąc nie da się zmodyfikować bezpośrednio tak, by wszystko zawierało się w jednej funkcji quicksort pomijając funkcję "pomocniczą"?

Pytam z dwóch względów, ponieważ ostatnio za rozwiązanie właśnie z osobną funkcją kopiującą listę otrzymałem bardzo niską ocenę, gdyż "wyraźnie było napisane, że trzeba to zrobić w jednej funkcji".

Po drugie chciałbym się odnieść do tego co napisałeś na temat quicksortów, które stwierdziłeś, że nie robią nic. Teoretycznie, za każdym razem normalnie kontynuują one sortowanie, co sprawdzałem wyświetlając stany tablicy, przed i po każdym z nich. Dodatkowo nadal nie rozumiem, dlaczego kopiowanie tablicy wewnątrz nadal nie działa. Przecież dokonując kopiowania tablicy  na początku każdego quicksorta, wykonuję jedynie nową kopię argumentu, cały czas operując na odświeżonej tablicy, w której cały czas dokonują się zmiany. Jedynym problemem jest fakt, że sortowanie nie zatrzymuje się nawet po otrzymaniu odpowiednio posortowanej tablicy.

Z góry dziękuję za wyjaśnienia :)

Poniżej stany, skopiowanej tablicy, po każdym wykonaniu dodatkowych quicksortów :)

[1, 2, 3, 9, 10, 14, 25] 
[2, 1, 3, 9, 10, 14, 25]
[2, 1, 3, 9, 10, 14, 25]
[2, 10, 9, 3, 1, 14, 25]
[2, 10, 9, 3, 1, 14, 25]
[2, 10, 9, 3, 1, 14, 25]

 

komentarz 6 stycznia 2021 przez adrian17 Ekspert (344,100 p.)

Czyli krótko mówiąc nie da się zmodyfikować bezpośrednio tak, by wszystko zawierało się w jednej funkcji quicksort pomijając funkcję "pomocniczą"?

Da się, patrz pierwsza odpowiedź - "Musisz uzyć wartość zwracaną przez funkcję.".

Po drugie chciałbym się odnieść do tego co napisałeś na temat quicksortów, które stwierdziłeś, że nie robią nic. 

No bo jeśli masz taką funkcję:

def sortuj(lista):
    copy = lista[:]
    # costam costam
    return copy

lista = [1, 2, 3]
sortuj(lista)

No to musisz przyznać, że to `sortuj(lista)` efektywnie nic nie robi, nie? Bo funkcja zwróciła posortowaną listę, ale nic z nią nie zrobiłeś.

Dokładnie to robisz tutaj.

if start < j:
    quicksort(copy_I, start, j)
if i < stop:
    quicksort(copy_I, i, stop)

A na boku:

Pytam z dwóch względów, ponieważ ostatnio za rozwiązanie właśnie z osobną funkcją kopiującą listę otrzymałem bardzo niską ocenę, gdyż "wyraźnie było napisane, że trzeba to zrobić w jednej funkcji".

To on powinien dostać pałę, bo nie rozumie quicksorta. Quicksort edytuje sortowaną listę, inaczej nie jest quicksortem (ma inne charakterystyki).

komentarz 6 stycznia 2021 przez maciej12 Nowicjusz (120 p.)

Wybacz mi, że sam do tego nie dochodzę, ale już głowa mi paruje, ponieważ męczę się z tym już wiele godzin. 

Musisz użyć wartość zwracaną przez funkcję.

Bardzo Cię proszę powiedz mi jak. Próbuję, kombinuję na wszystkie sposoby, ale nadal nie mogę dojść do tego jak to konkretnie zrobić, żeby wreszcie zadziałało dobrze :(

komentarz 6 stycznia 2021 przez adrian17 Ekspert (344,100 p.)

No... na oko, po prostu to?

copy_I = quicksort(copy_I, start, j)

 

komentarz 6 stycznia 2021 przez adrian17 Ekspert (344,100 p.)

Natomiast tak jak mówię, to nie jest quicksort. Przez to że w każdej iteracji kopiujesz całą tablicę, ma znacznie gorszą złożoność czasową i pamięciową od normalnego quicksorta.

Podobne pytania

0 głosów
1 odpowiedź 477 wizyt
pytanie zadane 23 kwietnia 2020 w C i C++ przez Rrafał98 Nowicjusz (240 p.)
0 głosów
1 odpowiedź 4,708 wizyt
0 głosów
0 odpowiedzi 146 wizyt
pytanie zadane 15 listopada 2022 w C i C++ przez ijoasia Nowicjusz (120 p.)

92,455 zapytań

141,263 odpowiedzi

319,100 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...