algorytmy sortujące

[Behoston]

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.

[pjankowski]

Jak sprawdzisz, czy ktoś sobie nie zrobił sorted(list) w pythonie?

[Behoston]

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

[pjankowski]

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.

[Behoston]

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

[pjankowski]

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.

[Behoston]

to jak ktoś napisze parser to też dobrze no nie ?
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

[pjankowski]

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!

[Behoston]

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

[pjankowski]

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

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.

[Behoston]

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"

[pjankowski]

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
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...

[Behoston]

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)

[pjankowski]

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

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ą.

[Behoston]

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
Jak nie było by dyskusji to od czego byśmy tu byli?

proszę

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)