Sortowanie przez kopcowanie

Nie wiesz, gdzie umieścić swój post? Pisz tutaj!

Sortowanie przez kopcowanie

Postprzez paula.0120 » Wt mar 24, 2020 11:46 pm

Witam. Ostatnio zainteresował mnie temat kopców oraz sortowania przez kopcowanie.
Przy zastosowaniu HEAPSORT napotkałam się z pewnym problemem. Moja tablica zawiera przypadkowe liczby, przy czym niektóre się powtarzają. Przy budowaniu kopca typu max moja dwójka dzieci znajdująca się bezpośrednio przy korzeniu ma takie same wartości. Czy mógłby mi ktoś powiedzieć jak w takich wypadkach postępować? Dodatkowo HEAPSORT powinno zwracać mi posortowaną tablice, ale również nie wiem jak to powinno wyglądać przy powtarzających się cyfrach. Bardzo proszę o jakieś wskazówki.
OpenOffice 3.1 na Windows
paula.0120
 
Posty: 7
Dołączył(a): Śr mar 18, 2020 11:20 pm

Re: Sortowanie przez kopcowanie

Postprzez Jan_J » Śr mar 25, 2020 1:44 am

A radzisz sobie z prostszymi metodami sortowania?
JJ
LO 6.2 ∙ AOO 4.1.7 ∙ Python (3.8|2.7) ∙ Unicode 12 ∙ LATEX 2ε ∙ XML ∙ Unix tools ∙ Linux (Fedora|CentOS|SUSE)
Jan_J
 
Posty: 4096
Dołączył(a): Pt maja 22, 2009 1:20 pm
Lokalizacja: Wrocław

Re: Sortowanie przez kopcowanie

Postprzez paula.0120 » Śr mar 25, 2020 8:46 am

Tak :) Nie mam z nimi żadnego problemu.
OpenOffice 3.1 na Windows
paula.0120
 
Posty: 7
Dołączył(a): Śr mar 18, 2020 11:20 pm

Re: Sortowanie przez kopcowanie

Postprzez paula.0120 » Śr mar 25, 2020 10:57 am

Wiem, że wszystkie elementy zostaną wywołane w kolejności od największej do najmniejszej. Ale chciałabym wiedzieć, jeżeli moja dwójka dzieci przy korzeniu są takie same, to które z nich (prawe czy lewe) powinno wyskoczyć jako pierwsze na miejsce korzenia? Czy ta kolejność ma jakieś znaczenie? Bo gdybym miała to zrobić to najpierw wzięłabym wyraz po lewej stronie.
OpenOffice 3.1 na Windows
paula.0120
 
Posty: 7
Dołączył(a): Śr mar 18, 2020 11:20 pm

Re: Sortowanie przez kopcowanie

Postprzez Jan_J » Śr mar 25, 2020 11:47 am

W sortowaniu stogowym wartości z nieuporządkowanej części są po kolei wstawiane w kopiec.
Przebudowa kopca spowodować może, że wpisy o tej samej wartości utracą swoją wzajemną pozycję.
To znaczy, ciąg wynikowy będzie uporządkowany, ale bez gwarancji zachowania pierwotnej kolejności elementów równych. O takich metodach sortowania mówi się, że są niestabilne.
JJ
LO 6.2 ∙ AOO 4.1.7 ∙ Python (3.8|2.7) ∙ Unicode 12 ∙ LATEX 2ε ∙ XML ∙ Unix tools ∙ Linux (Fedora|CentOS|SUSE)
Jan_J
 
Posty: 4096
Dołączył(a): Pt maja 22, 2009 1:20 pm
Lokalizacja: Wrocław

Re: Sortowanie przez kopcowanie

Postprzez paula.0120 » Śr mar 25, 2020 9:19 pm

Super. Zrozumiałam kwestię teoretyczną :)
Chciałabym to teraz przełożyć na Pythona.
Po wpisaniu dowolnej listy chciałabym, żeby program sprawdzał mi czy dana lista jest kopcem typu max.
Czy mogłabym poprosić o jakieś wskazówki od czego zacząć?
Oczywiście zdefiniowałam na początek :

def heap_parent(n) :
return (n-1)/2
def heap_left(n) :
return (2*n+1)
def heap_right(n) :
return (2*n+2)
Wiem, że listy w Pythonie indeksowane są od 0. Mam nadzieję, że dobrze zdefiniowałam podane funkcje :)
OpenOffice 3.1 na Windows
paula.0120
 
Posty: 7
Dołączył(a): Śr mar 18, 2020 11:20 pm


Powrót do Forum pierwszego kontaktu

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość