20.09.2019 17:49
[#1]
Sortowanie exec list
Czesc,
chcialem dodac sortowanie playlisty wiec pomyslalem , ze zaczne od tylko jednej litery (pierwszej oczywiscie) i z czasem dodam kolejne - czas leci a ja dalej siedze w punkcie wyjscia.
To co jest na zdjeciu, momentalnie zawiesza mi Amige.
Wystarczy jednak ze odkomentuje 2 linike nad ostatnim WEND i Amiga sie nie wiesza no ale wtedy sortowanie ma "dziury" bo zacznie przeskakiwac "nody".
Wg mnie to program ze zdjecia POWINIEN dzialac bez problemu
No niestety jest odwrotnie
Pomocy
chcialem dodac sortowanie playlisty wiec pomyslalem , ze zaczne od tylko jednej litery (pierwszej oczywiscie) i z czasem dodam kolejne - czas leci a ja dalej siedze w punkcie wyjscia.
To co jest na zdjeciu, momentalnie zawiesza mi Amige.
Wystarczy jednak ze odkomentuje 2 linike nad ostatnim WEND i Amiga sie nie wiesza no ale wtedy sortowanie ma "dziury" bo zacznie przeskakiwac "nody".
Wg mnie to program ze zdjecia POWINIEN dzialac bez problemu
No niestety jest odwrotnie Pomocy
20.09.2019 18:12
[#2]
Re: Sortowanie exec list
@peceha, post #1
Zacznijmy od tego, że jeśli lista będzie pusta, to nd będzie zerem. Linia 4 to już błąd w tym momencie.
Zamiast sortować tylko po pierwszej literze, można użyć funkcji utility.library/Stricmp(). Sortowanie według polskich locali (jeżeli ustawione w systemie) w gratisie.
Przy sortowaniu listy najlepsze są algorytmy, gdzie iterowanie listy jest przerywane przed każdą zamianą elementów. Na przykład sortowanie bąbelkowe. Nie jest to może król wydajności, ale daje radę. Iterowanie listy i jednoczesne usuwanie/wstawianie elementów zazwyczaj oznacza kłopoty.
Zamiast sortować tylko po pierwszej literze, można użyć funkcji utility.library/Stricmp(). Sortowanie według polskich locali (jeżeli ustawione w systemie) w gratisie.
Przy sortowaniu listy najlepsze są algorytmy, gdzie iterowanie listy jest przerywane przed każdą zamianą elementów. Na przykład sortowanie bąbelkowe. Nie jest to może król wydajności, ale daje radę. Iterowanie listy i jednoczesne usuwanie/wstawianie elementów zazwyczaj oznacza kłopoty.
20.09.2019 18:22
[#3]
Re: Sortowanie exec list
@Krashan, post #2
Powinienem dodac, ze sprawdzenie list czy jest pusta jest gdzie indziej - tak czy siak, nie dojdzie do wykonania tego jesli bedzie pusta.
Dzieki za informacje o Stricmp() - nie mialem bladego pojecia o jej istnieniu.
Wlasnie doswiadczam tego na wlasnej skorze, he.
Dzieki,
Dzieki za informacje o Stricmp() - nie mialem bladego pojecia o jej istnieniu.
Iterowanie listy i jednoczesne usuwanie/wstawianie elementów zazwyczaj oznacza kłopoty.
Wlasnie doswiadczam tego na wlasnej skorze, he.
Dzieki,
20.09.2019 23:37
[#4]
Re: Sortowanie exec list
@peceha, post #3
Przemyślałem jeszcze kwestię wyboru algorytmu sortowania. Ponieważ w przeciwieństwie do tablicy (a o niej rozwodzą się wszystkie podręczniki rozważające temat sortowania), wstawianie elementu w środek listy jest bardzo proste, po prostu zrób drugą, pustą listę i poprzekładaj elementy z pierwszej do drugiej od razu po kolei.
Nie wiem tylko które podejście będzie lepsze:
1. Iterowanie listy źródłowej w poszukiwaniu elementu najmniejszego i wstawianie go zawsze na koniec listy docelowej.
2. Pobieranie dowolnego (np. zawsze pierwszego) elementu listy źródłowej, następnie iterowanie listy docelowej w celu znalezienia odpowiedniego miejsca i wstawienie.
Oba algorytmy pracują do momentu, gdy lista źródłowa będzie pusta. Potem żeby sobie nie komplikować kodu można nadpisać header listy źródłowej headerem listy wynikowej.
Oba algorytmy będą szybsze niż bąbelkowe sortowanie jednej listy i są proste do napisania.
nieco później
Algorytm 2 powinien być szybszy prawie zawsze. Pierwszy będzie zawsze robił mniej więcej N^2/2 porównań (N to liczba sortowanych elementów). Listę źródłową trzeba zawsze czesać do końca, bo nigdy nie wiemy gdzie będzie ten najmniejszy element. Drugi algorytm w przypadku skrajnie niekorzystnym też wykona N^2/2 porównań (lista źródłowa już posortowana, kolejny element zawsze trafia na koniec docelowej), ale w skrajnie korzystnym tylko N (lista źródłowa posortowana odwrotnie), średnio więc będzie mniej.
Ostatnia aktualizacja: 20.09.2019 23:47:01 przez Krashan
Nie wiem tylko które podejście będzie lepsze:
1. Iterowanie listy źródłowej w poszukiwaniu elementu najmniejszego i wstawianie go zawsze na koniec listy docelowej.
2. Pobieranie dowolnego (np. zawsze pierwszego) elementu listy źródłowej, następnie iterowanie listy docelowej w celu znalezienia odpowiedniego miejsca i wstawienie.
Oba algorytmy pracują do momentu, gdy lista źródłowa będzie pusta. Potem żeby sobie nie komplikować kodu można nadpisać header listy źródłowej headerem listy wynikowej.
Oba algorytmy będą szybsze niż bąbelkowe sortowanie jednej listy i są proste do napisania.
nieco później
Algorytm 2 powinien być szybszy prawie zawsze. Pierwszy będzie zawsze robił mniej więcej N^2/2 porównań (N to liczba sortowanych elementów). Listę źródłową trzeba zawsze czesać do końca, bo nigdy nie wiemy gdzie będzie ten najmniejszy element. Drugi algorytm w przypadku skrajnie niekorzystnym też wykona N^2/2 porównań (lista źródłowa już posortowana, kolejny element zawsze trafia na koniec docelowej), ale w skrajnie korzystnym tylko N (lista źródłowa posortowana odwrotnie), średnio więc będzie mniej.
Ostatnia aktualizacja: 20.09.2019 23:47:01 przez Krashan
21.09.2019 00:13
[#5]
Re: Sortowanie exec list
@Krashan, post #4
@Krashan
@Peceha
Ja polecam do sortowania listy sortowanie Mergesort.
Działa zarówno na tablicy, jak i liście.
Jego idea jest prosta - a efektywność znakomita, bo O(n*log(n)) - koszt liniowo-logarytmiczny.
Mergesort polega na tym, że przechodząc po kolei po liście scalamy pary elementów listy. Najpierw pary składają się z jednoelementowych pod-list, później - dwuelementowych, czteroelementowych itd. Scalanie zaś polega na przebiegnięciu po obu posortowanych już pod-listach na przemian i złączeniu utrzymując porządek, co ma koszt liniowy O(n). Takich scaleń wykonujemy zaś log(n) razy.
Algorytmy i struktury danych to był mój ulubiony przedmiot na studiach, a zagadnienie sortowania to chyba podstawowa rzecz w tym przedmiocie.
Mergesort można zrealizować "w miejscu" - czyli bez potrzeby korzystania z pomocniczych struktur danych. Jest też sortowaniem stabilnym, tj. kolejność elementów o identycznych kluczach się nie zmienia.
Ostatnia aktualizacja: 21.09.2019 00:24:26 przez Hexmage960
@Peceha
Ja polecam do sortowania listy sortowanie Mergesort.
Działa zarówno na tablicy, jak i liście.Jego idea jest prosta - a efektywność znakomita, bo O(n*log(n)) - koszt liniowo-logarytmiczny.
Mergesort polega na tym, że przechodząc po kolei po liście scalamy pary elementów listy. Najpierw pary składają się z jednoelementowych pod-list, później - dwuelementowych, czteroelementowych itd. Scalanie zaś polega na przebiegnięciu po obu posortowanych już pod-listach na przemian i złączeniu utrzymując porządek, co ma koszt liniowy O(n). Takich scaleń wykonujemy zaś log(n) razy.
Algorytmy i struktury danych to był mój ulubiony przedmiot na studiach, a zagadnienie sortowania to chyba podstawowa rzecz w tym przedmiocie.
Mergesort można zrealizować "w miejscu" - czyli bez potrzeby korzystania z pomocniczych struktur danych. Jest też sortowaniem stabilnym, tj. kolejność elementów o identycznych kluczach się nie zmienia.
Ostatnia aktualizacja: 21.09.2019 00:24:26 przez Hexmage960
21.09.2019 02:10
[#6]
Re: Sortowanie exec list
@Krashan, post #4
wg mnie oba te algorytmy mają złożoność O(n^2), taka sama jak bubble sort... Pierwszy wygląda mi na selection sort a drugi na insertion sort.
Jeśli lista nie jest długa, to można spokojnie z nich korzystać, przy dłuższej liscie lepiej pójść w coś O(nlog(n)), jak np. merge sort
Jeśli lista nie jest długa, to można spokojnie z nich korzystać, przy dłuższej liscie lepiej pójść w coś O(nlog(n)), jak np. merge sort
21.09.2019 07:24
[#7]
Re: Sortowanie exec list
@Krashan, post #4
@Krashan
Wczoraj zrobilem babelkowe sortownie na jednej liscie i dziala
Dzis zrobie co zaproponowales w poscie 4 - nie chcialem wczescniej dwoch list ale nie pomyslalem o nadpisaniu naglowka listy wynikowej.
@Hexmage960
@docent
postaram sie zrobic i tak, ciekaw jestem przy jak duzej lisce pokaze swoja wyzszosc nad poprzednimi sortowaniami.
Dzieki
Wczoraj zrobilem babelkowe sortownie na jednej liscie i dziala
Dzis zrobie co zaproponowales w poscie 4 - nie chcialem wczescniej dwoch list ale nie pomyslalem o nadpisaniu naglowka listy wynikowej.
@Hexmage960
@docent
postaram sie zrobic i tak, ciekaw jestem przy jak duzej lisce pokaze swoja wyzszosc nad poprzednimi sortowaniami.
Dzieki