W dniu piątek, 12 października 2012 18:26:27 UTC+2 użytkownik identyfikator: 20040501
napisał:
> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w implementacji?
> nie musi być szybki...
Nie wiem dlaczego pytasz. Jesli chesz mozliwie najmniejszym
wysilkiem posortowac dane, to rozejrzyj sie za jakas standardowa
lista/wektorem ktore maja gotowe sortowanie.

A tak w ogole, dla mnie jest najprostszy ten co wybiera maxa i
wstawia na kolejne miejsca... zdaje sie ze to byl insertion sort.

Pozdrawiam

do góry

On 12.10.2012 19:28, bartekltg wrote:
> W dniu 2012-10-12 19:14, Michoo pisze:
>> On 12.10.2012 18:28, Roman W wrote:
>>> W dniu piątek, 12 października 2012 17:26:27 UTC+1 użytkownik
>>> identyfikator: 20040501 napisał:
>>>> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w
>>>> implementacji?
>>>>
>>>> nie musi być szybki...
>>>
>>> Bubble sort?
>> Nie wiem sąd się wziął ten mit - sortowanie przez wybór (selection sort)
>> jest znacznie prostsze w implementacji i bardziej intuicyjne.
>
> Chwytliwa nazwa. Sięgnąłem do ASD Diksa i spółki. Tam
> bąbelki prewencyjnie przemilczają;)
Ale to jest ogólnie całkiem niezła książka. (A przydała mi się więcej
razy niż Cormen.)

Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
projektować algorytmów". A potem licealiści/studenci na pytanie o
najprostszy algorytm sortowania odpowiadają "bąbelki"...


>
> BTW, jakiś mały flejmik selectionsort vs insertionsort? ;>
Tu nie ma o czym dyskutować ;) - selectionsort jest najszybszy w
zapisaniu i najprostszy w wyjaśnieniu a poza przypadkami danych
częściowo (mocno) posortowanych szybszy od insertion.

Insertion jest niezły jako kolejny krok do uczenia algorytmów - można
pokazać, ze coś co teoretycznie jest szybkie w praktyce po uwzględnieniu
kosztu operacji na rzeczywistej pamięci ma ukryty koszt. No i na jego
podstawie powstało sortowanie Shella, które jest naprawdę ciekawym
(aczkolwiek niepraktycznym) rozwiązaniem.

--
Pozdrawiam
Michoo

do góry

On 12.10.2012 20:38, M.M. wrote:
> W dniu piątek, 12 października 2012 18:26:27 UTC+2 użytkownik identyfikator:
20040501 napisał:
>> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w implementacji?
>> nie musi być szybki...
> Nie wiem dlaczego pytasz. Jesli chesz mozliwie najmniejszym
> wysilkiem posortowac dane, to rozejrzyj sie za jakas standardowa
> lista/wektorem ktore maja gotowe sortowanie.
>
> A tak w ogole, dla mnie jest najprostszy ten co wybiera maxa i
> wstawia na kolejne miejsca... zdaje sie ze to byl insertion sort.
Selection sort. Insertion sort bierze kolejny element i wstawia go na
właściwe miejsce w już posortowanych. Musi więc "rozepchać" te
posortowane co się kiepsko robi z tablicą, ale np. z heapem już całkiem
dobrze ;)

--
Pozdrawiam
Michoo

do góry

W dniu 2012-10-12 20:38, M.M. pisze:
> W dniu piątek, 12 października 2012 18:26:27 UTC+2 użytkownik identyfikator:
20040501 napisał:
>> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w implementacji?
>> nie musi być szybki...
> Nie wiem dlaczego pytasz.

Wrzuć jego nick w google to się dowiesz.
Karmicie trolla. Śmieci głównie na pl.praca.dyskusje, na grupach
programistycznych i czasem innych, łapiąc jeleni, którzy odpowiadają na
infantylne pytania. To jego stały numer. Jak widzi odzew to po chwili
"jedzie" po PO i UE. Tutaj też już śmiecił i aż dziw bierze, że macie
taką krótką pamięć.

Pozdrawiam
Piotr

do góry

W dniu 2012-10-12 21:08, Michoo pisze:
> On 12.10.2012 19:28, bartekltg wrote:
>> W dniu 2012-10-12 19:14, Michoo pisze:
>>> On 12.10.2012 18:28, Roman W wrote:
>>>> W dniu piątek, 12 października 2012 17:26:27 UTC+1 użytkownik
>>>> identyfikator: 20040501 napisał:
>>>>> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w
>>>>> implementacji?
>>>>>
>>>>> nie musi być szybki...
>>>>
>>>> Bubble sort?
>>> Nie wiem sąd się wziął ten mit - sortowanie przez wybór (selection sort)
>>> jest znacznie prostsze w implementacji i bardziej intuicyjne.
>>
>> Chwytliwa nazwa. Sięgnąłem do ASD Diksa i spółki. Tam
>> bąbelki prewencyjnie przemilczają;)
> Ale to jest ogólnie całkiem niezła książka. (A przydała mi się więcej
> razy niż Cormen.)

Przecież chwalę. Patrząc na tę dyskusję brak bąbelków
można uznać jedynie za zaletę;)
Sam kupilem tą książkę jeszcze przed studiami,
trochę przez przypadek, a potem byłem z tego powodu
bardzo szczęśliwy;)


> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
> poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
> projektować algorytmów". A potem licealiści/studenci na pytanie o
> najprostszy algorytm sortowania odpowiadają "bąbelki"...

Przytargane z wiki:
http://www.cs.duke.edu/~ola/papers/bubble.pdf

>>
>> BTW, jakiś mały flejmik selectionsort vs insertionsort? ;>
> Tu nie ma o czym dyskutować ;) - selectionsort jest najszybszy w
> zapisaniu i najprostszy w wyjaśnieniu a poza przypadkami danych
> częściowo (mocno) posortowanych szybszy od insertion.

>
> Insertion jest niezły jako kolejny krok do uczenia algorytmów - można
> pokazać, ze coś co teoretycznie jest szybkie w praktyce po uwzględnieniu
> kosztu operacji na rzeczywistej pamięci ma ukryty koszt.

No i widzisz, już mamy pole do posprzeczania się:)

Insertionsort jest w oczywisty sposób szybszy w sensie
oczekiwanej liczby porównań (w select wyszukujemy maks
wśród tablic długości n, n-1, n-2...4,3,2, w insert
wkładamy zadany element w tablice długości 1,2..n-1,
a średnio włożymy w połowę długości.

Jeśli więc porównanie jest znacznie kosztowniejsze od
przesunięcia, wolimy mieć dwa razy mniej porównań,
nawet kosztem dodatkowych ~n^2 przesunięć.

Jeśli sortowalibyśmy listę, problem w ogóle znika.

A czasem o wyborze może zadecydować stabilność sortowania.

Tak więc ja bym nie był tak pewny odpowiedzi:)

A poważnie, z tą pamięcią to ciekawy problem.
Jeśli już mamy całość w cache (nie rozważamy
przecież na serio sortowania dużych tablic)
ale jednocześnie porównanie jest tanie (inty).
Żeby nie był to problem czysto akademicki,
niech to będzie 'końcówka qsorta'. Wtedy wywoływany
obszar i tak już najpewniej jest pod ręką.

Heh, możnaby jakimś studentom zadać;)


> No i na jego
> podstawie powstało sortowanie Shella, które jest naprawdę ciekawym
> (aczkolwiek niepraktycznym) rozwiązaniem.

Wyścigi, kto znajdzie lepszą sekwencję długości skoków chyba
nadal trwają;)

pzdr
bartekltg

do góry

Dnia 12.10.2012 Kviat <kviat@NIE_DLA_SPAMUneostrada.pl> napisał/a:
> W dniu 2012-10-12 20:38, M.M. pisze:
>> W dniu piątek, 12 października 2012 18:26:27 UTC+2 użytkownik identyfikator:
20040501 napisał:
>>> sory za lameriadę, jaki algorytm sotrujący jest najprostszy w implementacji?
>>> nie musi być szybki...
>> Nie wiem dlaczego pytasz.
>
> Wrzuć jego nick w google to się dowiesz.
> Karmicie trolla. Śmieci głównie na pl.praca.dyskusje, na grupach
> programistycznych i czasem innych, łapiąc jeleni, którzy odpowiadają na
> infantylne pytania. To jego stały numer. Jak widzi odzew to po chwili
> "jedzie" po PO i UE. Tutaj też już śmiecił i aż dziw bierze, że macie
> taką krótką pamięć.

Nie było mnie na tej grupie około 10 lat, "za moich czasów" były inne
trole :D

do góry

Baranosiu <r...@w...pl> wrote:

> Nie ważne jakie dane, ważne jaka struktura w programie:D

On sam nie wie, jaka struktura w programie. To przygłup i troll gorszego
gatunku, niż fir.

--
Gof
http://www.chmurka.net/

do góry

Dnia Fri, 12 Oct 2012 21:08:36 +0200, Michoo napisal:

> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
> poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
> projektować algorytmów". A potem licealiści/studenci na pytanie o
> najprostszy algorytm sortowania odpowiadają "bąbelki"...

Nie wiedzieć czemu w edukacji stosuje się sortowanie do nauczania
algorytmów. Poza złożonością obliczeniową sortowanie nie nadaje się
na przykład czegokolwiek.

--
Edek

do góry

On 12.10.2012 23:20, bartekltg wrote:
> W dniu 2012-10-12 21:08, Michoo pisze:
>> On 12.10.2012 19:28, bartekltg wrote:
>>> W dniu 2012-10-12 19:14, Michoo pisze:

>>> Chwytliwa nazwa. Sięgnąłem do ASD Diksa i spółki. Tam
>>> bąbelki prewencyjnie przemilczają;)
>> Ale to jest ogólnie całkiem niezła książka.
>
> Przecież chwalę.
> Patrząc na tę dyskusję brak bąbelków
> można uznać jedynie za zaletę;)

Chodziło mi właśnie o to, że "nie ma bo to jest dobra książka" ;)

>
>
>> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
>> poczatku, [...]
>
> Przytargane z wiki:
> http://www.cs.duke.edu/~ola/papers/bubble.pdf
Fajne.

>
>>>
>>> BTW, jakiś mały flejmik selectionsort vs insertionsort? ;>
>> Tu nie ma o czym dyskutować ;) - selectionsort jest najszybszy w
>> zapisaniu i najprostszy w wyjaśnieniu a poza przypadkami danych
>> częściowo (mocno) posortowanych szybszy od insertion.
>
>>
>> Insertion jest niezły jako kolejny krok do uczenia algorytmów - można
>> pokazać, ze coś co teoretycznie jest szybkie w praktyce po uwzględnieniu
>> kosztu operacji na rzeczywistej pamięci ma ukryty koszt.
>
> No i widzisz, już mamy pole do posprzeczania się:)
>
> Insertionsort jest w oczywisty sposób szybszy w sensie
> oczekiwanej liczby porównań (w select wyszukujemy maks
> wśród tablic długości n, n-1, n-2...4,3,2, w insert
> wkładamy zadany element w tablice długości 1,2..n-1,
> a średnio włożymy w połowę długości.

Zgadza się.

>
> Jeśli więc porównanie jest znacznie kosztowniejsze od
> przesunięcia, wolimy mieć dwa razy mniej porównań,
> nawet kosztem dodatkowych ~n^2 przesunięć.

Widziałem nawet takie rozważanie gdzie wyszukiwanie w części
posortowanej było robione przeszukiwaniem binarnym, a wstawianie było w
czasie stałym - dostajemy złożoność insertion sort n*log(n) ;)


>
> Jeśli sortowalibyśmy listę, problem w ogóle znika.
Lista musi być na tyle duża, że nie możemy jej skopiować do struktury o
dostępie swobodnym, ale jest to naciągane, bo przy złożoności n^2
prawdopodobnie taniej będzie przenieść listę na pamięć zewnętrzną,
zwolnić, wczytać do tablicy, posortować jakimś q/heap sortem, zapisać na
pamięć zewnętrzną, zwolnić, wczytać do listy ;)

>
> A czasem o wyborze może zadecydować stabilność sortowania.

Jeżeli dobrze widzę to i insertion i selection może być stabilny.

>
> Tak więc ja bym nie był tak pewny odpowiedzi:)
>
> A poważnie, z tą pamięcią to ciekawy problem.
> Jeśli już mamy całość w cache (nie rozważamy
> przecież na serio sortowania dużych tablic)
> ale jednocześnie porównanie jest tanie (inty).

> Żeby nie był to problem czysto akademicki,
> niech to będzie 'końcówka qsorta'. Wtedy wywoływany
> obszar i tak już najpewniej jest pod ręką.

Ale w takiej sytuacji jest heapsort działający zawsze w n*log(n) ;)

>
> Heh, możnaby jakimś studentom zadać;)

Wygrzebałem stare sprawozdanie na "algorytmy i struktury danych".
Najszybszym algorytmem dla losowych danych był wtedy heapsort napisany w
assemblerze (ale miałem na jego optymalizację dobre 3 godziny podczas
jazdy pociągiem). Największym zaskoczeniem był Shell:
http://grota.be/~michoo/smieci/algo_sort.png


--
Pozdrawiam
Michoo

do góry

On 13.10.2012 11:27, Edek Pienkowski wrote:
> Dnia Fri, 12 Oct 2012 21:08:36 +0200, Michoo napisal:
>
>> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
>> poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
>> projektować algorytmów". A potem licealiści/studenci na pytanie o
>> najprostszy algorytm sortowania odpowiadają "bąbelki"...
>
> Nie wiedzieć czemu w edukacji stosuje się sortowanie do nauczania
> algorytmów. Poza złożonością obliczeniową sortowanie nie nadaje się
> na przykład czegokolwiek.
>
Dlaczego? Mamy dane wejściowe, mamy predykat do spełnienia na wyjściu,
mamy opis operacji, czyli algorytm. Łatwe do zrozumienia, łatwe do
prezentacji, łatwe do sprawdzenia poprawności.

Co Ty byś proponował do nauki algorytmów?

--
Pozdrawiam
Michoo

do góry