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

Zadanie - Algorytm QuickSort

Fiszki IT
Fiszki IT
0 głosów
120 wizyt
pytanie zadane 6 stycznia 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 przez tmar1212 Obywatel (1,760 p.)
A po co to kopiowanie?

1 odpowiedź

+1 głos
odpowiedź 6 stycznia przez adrian17 Ekspert (297,380 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 przez adrian17 Ekspert (297,380 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 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 przez adrian17 Ekspert (297,380 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 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 przez adrian17 Ekspert (297,380 p.)

No... na oko, po prostu to?

copy_I = quicksort(copy_I, start, j)

 

komentarz 6 stycznia przez adrian17 Ekspert (297,380 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ź 153 wizyt
pytanie zadane 23 kwietnia 2020 w C i C++ przez Rrafał98 Nowicjusz (240 p.)
0 głosów
1 odpowiedź 4,211 wizyt
+1 głos
1 odpowiedź 103 wizyt
pytanie zadane 27 czerwca 2020 w C i C++ przez Marcinuq Początkujący (480 p.)
Porady nie od parady
Możesz ukryć, zamknąć lub zmodyfikować swoje pytanie, za pomocą przycisków znajdujących się pod nim. Nie krępuj się poprawić pochopnie opublikowanego pytania czy zamknąć go po uzyskaniu satysfakcjonującej odpowiedzi. Umożliwi to zachowanie porządku na forum.Przyciski pytania

84,702 zapytań

133,503 odpowiedzi

295,887 komentarzy

55,979 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...