Strony: [1] 2
  Drukuj  
Autor Wątek: algorytmy sortujące  (Przeczytany 3471 razy)
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« : Marca 14, 2015, 10:19:46 »

Temat mówi sam za siebie.
Dajemy dane i mówimy jak je sortować (jakimi metodami i jak metody działają)
Proponuje na start dać bąbelkowe i przez dzielenie
wejście > nieposortowane dane
odpowiedź < posortowane dane

1. Opisać bubblesort
2. Opisać merge sort

1. Dać niewielką ilość danych do bubblesorta
2. Dać olbrzymią ilość danych do megesorta (tak żeby bubblesort działał znacząco wolniej)


Opcjonalnie dać QuickSorta ale nie wiem czy nie za trudne.
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #1 : Marca 15, 2015, 12:20:34 »

Jak sprawdzisz, czy ktoś sobie nie zrobił sorted(list) w pythonie?
Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #2 : Marca 15, 2015, 12:35:19 »

jak sprawdzisz czy ktoś nie zerżnie zadania z jakiegoś forum gdzie będą rozwiązania?
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #3 : Marca 15, 2015, 12:50:47 »

Pilnując, żeby nigdzie tego nie było, a w przyszłości - generując losowe dane. Poza tym, co innego szukać nie wiadomo gdzie "pirackich" rozwiązań, a co innego skorzystać z gotowego, najprostszego rozwiązania.

Generalnie sortowanie to ważny i fajny temat, ale bardziej na artykuł/część programistycznego tutoriala niż zadanie, imho.
Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #4 : Marca 15, 2015, 07:20:03 »

Zawsze można dać listę jakichś obiektów i kazać po jakimś paramerze sortować
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #5 : Marca 15, 2015, 02:49:14 »

Wtedy algorytm rozwiązania wygląda tak:
prosty parser
sorted()

Generalnie myślałem o sortowaniu jak zastanawiałem się nad zadaniem "optymalizacyjnym", ale z przyczyn, które wymieniłem odrzuciłem tą myśl. Ciężko jest ułożyć tego typu zadanie tak, żeby sorted() nie było najprostszym rozwiązaniem, ale być może jest to możliwe.
Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #6 : Marca 15, 2015, 03:35:25 »

to jak ktoś napisze parser to też dobrze no nie Język ?
Można do sortowania wprowadzić modyfikację że w bubblesort można przesunąć k w przód maksymalnie (co da nam nie do końca posortowaną listę)
a w megesort hmm...
łejeaminyt
można dać wagi poszczególnych "modułów" że np. ten którego odchylenie standardowe jest mniejsze jest mniejszy a jeśli równe to dopiero się dzieli na mniejsze a jak długość "modułu" jest 1 to wtedy porównuje wartości. To też da nam nieposortowaną listę.
no w każdym razie bezpieczne zadanie typu sortowanie czy struktury danych jest bardzo ciężko sprawdzać w szczególności jeśli inputem do sprawdzania może być jedynie jakiś ciąg znaków..
Quicksorta od ręki "zaburzyć" nie potrafię bo musiał bym powtórzyć sobie ten algorytm.
Można też dać sortowanie w przestrzeni n-wymiarowej gdzie łatwiej napisać od 0 (jakimś algorytmem o złożoności długość_listy^(wymiar+1))
Ale to są zadania z puli tych "ciekawszych" i sami najpierw musieli byśmy porządnie przeanalizować jak te algorytmy sensownie modyfikować.
Zabawa jest Chichot
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #7 : Marca 15, 2015, 05:32:40 »

Nadal te modyfikacje sprowadzają się do:
(parser)
sorted()
(parser)

Zadań na parsowanie już trochę jest, więc moje zdanie pozostaje niezmienione - darowałbym sobie to.

Aczkolwiek to sortowanie w n-wymiarach brzmi bardzo fajnie i jakbyś to jakoś rozwinął to mogłoby wyjść coś naprawdę ciekawego i niestandardowego - to jak najbardziej popieram!
Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #8 : Marca 15, 2015, 05:56:34 »

nope, parser tego nie załatwi. A jak załatwi to będzie koniec końców robił rzeczywiście sortowanie takie na jakim nam zależy :E przeanalizuj to sobie to zrozumiesz.
A sortowanie w kilku wymiarach sprowadza się do posortowania kilka razy lub z wagami więc jest znacząco prostsze od zaburzonego sortowania Język
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #9 : Marca 15, 2015, 06:19:25 »

Zdefiniuj dokładnie te "zaburzenia", bo nie jestem w stanie przeanalizować => zrozumieć tego co napisałeś. Tak z interpunkcją i takimi tam...  Mrugnięcie

Co do sortowania w n-wymiarach: zdefiniuj jaką macierz (póki co w (edit: 2d i) 3d uznajemy za posortowaną), bo to też nie musi być proste.
« Ostatnia zmiana: Marca 15, 2015, 06:26:13 wysłane przez pjankowski » Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #10 : Marca 15, 2015, 07:20:50 »

ok dam przykład bubble sorta:

lista  5,8,6,4,8,3
powiedzmy że możemy jedną liczbę przesunąć tylko 2 razy
5-8 jest ok, 8-6 zamiana, 8-4 zamiana > break bo już 2 zmiany zrobiliśmy
5,6,8,4,8,3
5-6 jest ok, 6-8 jest ok, 8-4 zamiana, 8-8 jest ok, 8-3 zamiana > następny przebieg bo koniec listy
5,6,4,8,3,8
5-6 ok, 6-4 zamiana, 6-8 ok, 8-3 zmiana > break bo 2 zmiany
5,4,6,3,8,8
itd.
na tej liście wyjdzie słabo to zaburzenie ale nie bardzo mam chęć silić się na lepszy przykład.
Lista będzie "niedosortowana"
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #11 : Marca 15, 2015, 07:44:32 »

Po 1: strasznie udziwniamy algorytm, co odwraca uwagę od meritum (i złożoności obliczeniowej)
Po 2: przecież na końcu ta lista będzie posortowana (jak każda inna)

kolejne trzy kroki:
5-4 zamiana, 5-6 ok, 6-3 zamiana > break
4,5,3,6,8,8
4-5 ok, 5-3 zamiana, okokokokok > następny przebieg
4,3,5,6,8,8
4-3 zamiana okokokokokok > następny przebieg
3,4,5,6,8,8
Co?Co?Co?Co?Co? chyba, że czegoś nadal nie rozumiem

EDIT:
Czekaj, czekaj, czekaj... Mam pomysł!
Możemy dać listę na start i poprosić o wpisanie listy po np. 100 obrotach pętli bubble-sorta. Z tym, że ciężko coś analogicznego wymyślić dla algorytmów rekurencyjnych...
« Ostatnia zmiana: Marca 15, 2015, 08:02:20 wysłane przez pjankowski » Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #12 : Marca 15, 2015, 08:03:06 »

czyli sądzisz że robiąc tylko 2 zmiany w każdym przebiegu listy polegające na zamianie sąsiadujących wartości jesteśmy w stanie przesortować całą listę? Szykujmy się na nobla z matematyki :E
Wiem że udziwniamy ale nie zrobisz nic lepszego jak koniecznie chcesz mieć pewność, że ktoś nie użyje gotowej funkcji (moim zdaniem martwienie się o to jest głupotą ale jak kto uważa)
Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
pjankowski
Student
Full Member
***
Wiadomości: 237



Zobacz profil Email
« Odpowiedz #13 : Marca 15, 2015, 08:27:46 »

Cytuj
czyli sądzisz że robiąc tylko 2 zmiany w każdym przebiegu listy polegające na zamianie sąsiadujących wartości jesteśmy w stanie przesortować całą listę?
Oczywiście, że tak. Każda zmiana (choćby i jedna w każdym przebiegu) zbliża nas do sukcesu. Jeśli to nie jest dla Ciebie oczywiste - zakoduj to w Pythonie i zobacz (5min roboty). Chętnie ujrzę kontrprzykład Mrugnięcie

Zawsze znajdzie się droga, na jakieś czitowanie, ale nie twórzmy zadań, które można rozwiązać w minutę z prośbą o zrobienie tego "na około". Bubblesorta można (prosząc o ten setny krok) pozbawić tej wady, więc te dla których nie da się wymyślić obejścia po prostu sobie darujmy. Do nauki są tutoriale, a czelendże są do czelendżowania. Takie jest moje zdanie. Amen.

P.S. Mógłby się ktoś poza nami wypowiedzieć na ten temat, bo mamy wyraźnie odmienne poglądy. Dobrze byłoby sprawdzić kto jest w tym aspekcie mniejszością.
Zapisane
Behoston
Administrator
Sr. Member
*****
Wiadomości: 374


277797 mati-20
Zobacz profil WWW Email
« Odpowiedz #14 : Marca 15, 2015, 08:51:56 »

xD
zbliża do sukcesu, ale ja mówię o n przebiegach "zewnętrznej" pętli (założyłem, że to oczywiste, że tego nie zmieniamy)

A tak w ogóle to jakie mają  tam być zadania :| jak nie do nauki to do czego? Jak do ciekawszych zadań to takie utrudnienie jest ciekawe  moim zdaniem.
A zakoduję sobie w ramach przerwy w robieniu interfejsu do tworzenia automatycznie dzielonych histogramów w VBA Język
Jak nie było by dyskusji to od czego byśmy tu byli?

proszę Uśmiech
Kod:
from random import randint
l=[]
for i in range(100):
    l.append(randint(0,100))

def bs(l):
    for i in range(len(l)-1):
        zmiana=0
        for j in range(len(l)-i-1):
            if zmiana==2:brak
            if l[i+1]<l[i]:
                zmiana+=1
                pomocnicza=l[i+1]
                l[i+1]=l[i]
                l[i]=pomocnicza
               
    return l
               
print l
print bs(l)
« Ostatnia zmiana: Marca 15, 2015, 09:06:35 wysłane przez Behoston » Zapisane

Ilu bioinformatyków potrzeba do wkręcenia żarówki? Żadnego, bo i tak nie ma prądu.
Strony: [1] 2
  Drukuj  
 
Skocz do:  


SimplePortal 2.3.1 © 2008-2009, SimplePortal