Quicksort i Heapsort jak pokazać że są niestabilne?

Question

Mam za zadanie aby stworzyć strukturę przechowująca książki (tytuł, autor, rok wydania, cena), później posortować dane algorytmem quicksort oraz heapsort (alfabetycznie po tytułach), a następnie tak dobrać dane, aby pokazać, że są one niestabilne. Podpowie mi ktoś w jaki sposób mogę to zrobić?

Answer 1

Stabilny algorytm sortowania oznacza, że jeśli mamy dwa równe elementy to ich kolejność nie zmieni się po sortowaniu. Czyli jeśli mamy 3 2 2 1 to stabilny algorytm gwarantuje ze nie zamieni tych dwójek (pierwszą z drugą), które tutaj są nierozróżnialne więc to bez znaczenia, ale jeśli sortujesz np struktury i miałbyś dwie książki o tym samym tytule, ale innych autorach to wtedy elementy równe dla algorytmu sortującego są rozróżnialne po posortowaniu i możemy zweryfikować czy pozostały one w takiej samej kolejności jak były przed sortowaniem. Czyli mając gdzieś w tablicy ksiazek do posortowania dwa takie elementy: { tytuł:"abc", autor:"andrzej duda"; tytuł:"abc", autor:"janusz korwin mikke"} algorytm stabilny nie może zmienić ich kolejności mimo, że według kryterium porównawczego (po tytule) są one równe. Wiec musimy dostać: kawalek posortowanej tablicy, abc andrzeja, abc janusza, reszta posortowanej tablicy

Comments

Ok, dzięki jak nie wiem co ;)