Bardzo dziękuję za ten film! Jutro mam kolokwium z algorytmów i struktur danych. Długo nie mogłem zrozumieć QS. Dzięki temu filmowi wszystko stało się jasne :)
Wytłumaczone na chłopski rozum i napewno pomoże zrozumieć osobą które mają problem z tym algo. Ale algorytm działa trochę inaczej. Nie ma czegoś takiego jak bariera jest tylko i wyłącznie SWAP używając elementów low i high. Tak samo jeżeli chodzi o pamięć to minimalna wynosi O(log2 n) jak już powiedziałeś, a max to O(n) a nie O(1) - to wynika z struktury danych.
Tak sobie patrzyłem na zaproponowanie przeze mnie algorytmy sortujące i np do kubełków używają list więc może jeszcze na nie za wcześnie i lepiej zająć się sortowaniem danych w pliku (mało kto to pokazuje) a do algorytmów jak sortowanie przez zliczanie , pozycyjne czy kubełkowe wrócić po poznaniu podstawowych struktur danych jak stos, kolejka czy lista Przez to że wybrałeś Javę nie pokażesz jak zwalniać pamięć po węzłach struktur danych Jeżeli chodzi o sortowanie list to rozważyłbym procedurę wstawiającą w odpowiednie miejsce sortowanie przez scalanie i dla fanów quick sorta sortowanie szybkie dla list jednokierunkowych partycjonowanie Lomuto dla list dwukierunkowych partycjonowanie Hoare
Sortowanie danych w pliku o które mi chodziło dość często nazywają sortowaniem zewnętrznym Co to za sortowanie zewnętrzne gdyby udało się wczytać zawartość pliku do tablicy więc chodzi mi bardziej o przypadek gdy mamy z góry określoną ilość pamięci RAM na ogół mniejszą niż rozmiar sortowanego pliku
Jeśli chodzi o sortowanie tablic to proponuję zająć się tematami takimi jak Sortowanie przez zliczanie (counting sort ) Sortowanie pozycyjne (radix sort) Sortowanie kubełkowe (bucket sort) bo z tych które wymagają tylko porównań kluczy najważniejsze już omówiłeś Czekam też na sortowanie danych w pliku Niedawno chciałem sobie napisać program który sprowadzał się do sortowania jednak miałem zbyt mało pamięci aby wczytać dane to tablicy czy listy Jeżeli chodzi o sortowanie plików to można zrealizować to tak że w pliku tekstowym mamy linie z łańcuchami i chcemy posortować je alfabetycznie Dla testów możemy ściągnąć sobie jakiś wiersz omawiany na polskim Jeśli chodzi o sortowanie danych w pliku to nie miałem na myśli sytuacji gdy możemy wczytać cały plik do tablicy czy listy
Kiedyś mówiłeś o tym że można z algorytmy niestabilnego jakim jest np Quick Sort zrobić algorytm stabilny przy użyciu dodatkowej tablicy Mógłbyś coś więcej o tym nakręcić
Super dzięki! Szukałem nazwy ale Internet tym razem nie był skuteczny :) Dla ciekawych drugi możliwy sposób to partycjonowanie Hoare'a. Tutaj krótkie porównanie: www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/
Ogólnie plus za to że chcesz zająć się algorytmami na poważnie bo na youtube po polsku nikt się jeszcze tym nie zajął Na stronach internetowych trafiają się błędy np u Wałaszka jest ich sporo Z polskich książek do algorytmów to chyba jedynie Diks i Rytter , trochę o algorytmach jest też w Pasji Grębosza chociaż nie jest to typowo książka do algorytmów Z książek które dostępne są w przekładach dość dobrą jest książka Cormena i reszty Wprowadzenie do algorytmów Książkę Wirtha Algorytmy +struktury danych = programy już trochę trudniej się czyta
@@Hubertoom ale gdybyśmy chcieli przenieść ten algorytm na listę to w przypadku listy jednokierunkowej partycjonowanie Lomuto to jedyny wybór w dodatku wybór elementu rozdzielającego (ang pivot) będzie bardzo ograniczony
2: 07 - "jeśli element po prawej stronie granicy będzie mniejszy od pivota musimy zmienić go z pierwszym elementem na prawo od granicy", boże... robisz dobrze, a tłumaczysz źle. Niestety, to typowe dla kiepskich nauczycieli - wiedza co robią, ale nie potrafią tego po polsku powiedzieć.
Dobrze, że znalazłeś, ktoś mniej uważny i równie gorliwy napewno skorzysta. Całe szczęście nauczycielem nie jestem, po tym jak ten zawód niesłusznie został zmieszany z gównem. Pozdrawiam
Szkoda, że już nie nagrywasz bo robiłeś SUPER ROBOTĘ!!
Bardzo dziękuję za ten film! Jutro mam kolokwium z algorytmów i struktur danych. Długo nie mogłem zrozumieć QS. Dzięki temu filmowi wszystko stało się jasne :)
Cześć zdałeś?
@@krowczyk9173 Zdałem :)
Nawet nie wiem, jak bardzo się cieszę, że do dzisiaj pamiętam, jak QS działa.
Przykładowy kod algorytmu (C++) + analiza aż do pierwszego ustawienia pivota (3) na właściwym miejscu zgodnie z tablicą z filmu:
//KOD
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot - ostatnia liczba
int i = (low - 1), temp; // i = low - 1: i to indeks o jeden mniejszy od dolnej granicy, na poczatku 0 (i=-1)
for (int j = low; j temp = arr[0] => temp = 9
arr[i] = arr[j] => arr[0] = arr[1] => arr[0] = 1
arr[j] = temp => arr[1] = temp => arr[1] = 9
1 9 2 4 5 7 8 6 3
trzeci obieg for
i = 0
j = 2
czy 2 < 3: TAK - wykonujemy ifa
i = 1
j = 2
temp = arr[i] => temp = arr[1] => temp = 9
arr[i] = arr[j] => arr[1] = arr[2] => arr[1] = 2
arr[j] = temp => arr[2] = temp => arr[2] = 9
1 2 9 4 5 7 8 6 3
czwarty obieg for
i = 1
j = 3
czy 4 < 3: NIE
piąty obieg for
i = 1
j = 4
czy 5 < 3: NIE
szósty obieg for
i = 1
j = 5
czy 7 < 3: NIE
siódmy obieg for
i = 1
j = 6
czy 8 < 3: NIE
ósmy obieg for
i = 1
j = 6
czy 6 < 3: NIE
1 2 9 4 5 7 8 6 3
KONIEC FORa:
//ustawianie pivota na właściwej pozycji
temp = arr[i + 1]; => temp = arr[1 + 1] => temp = arr[2] => temp = 9
arr[i + 1] = arr[high]; => arr[1 + 1] = arr[8] => arr[2] = 3
arr[high] = temp; => arr[8] = temp => arr[8] = 9
1 2 (3) 4 5 7 8 6 9
//pivot na właściwym miejscu
return (i + 1); => return (1 + 1) => return (2); //pozycja pivota = 2 (trzeci indeks)
Wytłumaczone na chłopski rozum i napewno pomoże zrozumieć osobą które mają problem z tym algo. Ale algorytm działa trochę inaczej. Nie ma czegoś takiego jak bariera jest tylko i wyłącznie SWAP używając elementów low i high. Tak samo jeżeli chodzi o pamięć to minimalna wynosi O(log2 n) jak już powiedziałeś, a max to O(n) a nie O(1) - to wynika z struktury danych.
Genialne ! tak samo jak wszystkie inne filmiki! 100 % props
w 2:15 brakuje informacji dla przypadku jeśli element będzie równy "pivotowi"
masz pomysł co zrobić w takim przypadku?
błagam odpowiedz
@@milosh4851 nadał Ci trzeba?
@@huskyhusky777 już sobie poradziłem ale dzięki
Super wytłumaczone, dzięki bardzo za ten filmik. Przyda się na kolosa ;-)
dawaj salto
Tak sobie patrzyłem na zaproponowanie przeze mnie algorytmy sortujące
i np do kubełków używają list więc może jeszcze na nie za wcześnie
i lepiej zająć się sortowaniem danych w pliku (mało kto to pokazuje)
a do algorytmów jak sortowanie przez zliczanie , pozycyjne czy kubełkowe
wrócić po poznaniu podstawowych struktur danych jak stos, kolejka czy lista
Przez to że wybrałeś Javę nie pokażesz jak zwalniać pamięć po węzłach struktur danych
Jeżeli chodzi o sortowanie list to rozważyłbym
procedurę wstawiającą w odpowiednie miejsce
sortowanie przez scalanie
i dla fanów quick sorta sortowanie szybkie
dla list jednokierunkowych partycjonowanie Lomuto
dla list dwukierunkowych partycjonowanie Hoare
Sortowanie danych w pliku o które mi chodziło dość często nazywają sortowaniem zewnętrznym
Co to za sortowanie zewnętrzne gdyby udało się wczytać zawartość pliku do tablicy
więc chodzi mi bardziej o przypadek gdy mamy z góry określoną ilość pamięci RAM
na ogół mniejszą niż rozmiar sortowanego pliku
Dzięki bardzo, super tłumaczysz
a co jak beda te same cyfry
jak sie zsunie 9 to jest pomiedzy 7 i 8 wiec nie działa sadge://
Świetnie wytłumaczone
Bardzo dobra robota ! tak trzymaj !
dzięki! super wykład
Klasa!!
Jeśli chodzi o sortowanie tablic to proponuję zająć się tematami takimi jak
Sortowanie przez zliczanie (counting sort )
Sortowanie pozycyjne (radix sort)
Sortowanie kubełkowe (bucket sort)
bo z tych które wymagają tylko porównań kluczy najważniejsze już omówiłeś
Czekam też na sortowanie danych w pliku
Niedawno chciałem sobie napisać program który sprowadzał się do sortowania
jednak miałem zbyt mało pamięci aby wczytać dane to tablicy czy listy
Jeżeli chodzi o sortowanie plików to można zrealizować to tak że w pliku tekstowym mamy linie z łańcuchami
i chcemy posortować je alfabetycznie
Dla testów możemy ściągnąć sobie jakiś wiersz omawiany na polskim
Jeśli chodzi o sortowanie danych w pliku to nie miałem na myśli
sytuacji gdy możemy wczytać cały plik do tablicy czy listy
Wszystko super, ale popracuj nad wymową :)
Dziękuję! :D
szkoda że już nie nagrywasz
Kiedyś mówiłeś o tym że można z algorytmy niestabilnego jakim jest np Quick Sort zrobić algorytm stabilny
przy użyciu dodatkowej tablicy Mógłbyś coś więcej o tym nakręcić
Ostatnio faktycznie rzadko wrzucam filmy, postaram się trochę poprawić i nadrobić interesujące was tematy ;)
nie uznała mi tej metody rozpisywania na kolokwium :(
Ja piszę dzisiaj, mam nadzieję ze tego nie da, a jak da to mi zaliczy xd
super
Dzięki.
Dobra robota!
Kozak
No fajne
zna ktoś jakieś poradniki o algorytmach krokowych albo pseudokodzie ? Mogą być po angielsku
TheBestilsPL ALGORYTMY ALMANACH
Nic nie ogarniam
Wygląda na partycjonowanie Lomuto
Super dzięki! Szukałem nazwy ale Internet tym razem nie był skuteczny :)
Dla ciekawych drugi możliwy sposób to partycjonowanie Hoare'a.
Tutaj krótkie porównanie:
www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/
Ogólnie plus za to że chcesz zająć się algorytmami
na poważnie bo na youtube po polsku nikt się jeszcze tym nie zajął
Na stronach internetowych trafiają się błędy np u Wałaszka jest ich sporo
Z polskich książek do algorytmów to chyba jedynie Diks i Rytter ,
trochę o algorytmach jest też w Pasji Grębosza chociaż nie jest to typowo książka do algorytmów
Z książek które dostępne są w przekładach dość dobrą jest książka Cormena i reszty
Wprowadzenie do algorytmów
Książkę Wirtha Algorytmy +struktury danych = programy już trochę trudniej się czyta
Dzięki ;) Z założenia chcę aby filmy były proste, a tematy do zrozumienia. Mam nadzieję, że póki co się udaje :)
Lomuto czyli bardzo kiepskie, bo może doprowadzić łatwo do złożoności O(n2) w prawie posortowanych tablicach.
@@Hubertoom ale gdybyśmy chcieli przenieść ten algorytm na listę to w przypadku listy jednokierunkowej partycjonowanie Lomuto to jedyny wybór w dodatku wybór elementu rozdzielającego (ang pivot) będzie bardzo ograniczony
2: 07 - "jeśli element po prawej stronie granicy będzie mniejszy od pivota musimy zmienić go z pierwszym elementem na prawo od granicy", boże... robisz dobrze, a tłumaczysz źle. Niestety, to typowe dla kiepskich nauczycieli - wiedza co robią, ale nie potrafią tego po polsku powiedzieć.
Dobrze, że znalazłeś, ktoś mniej uważny i równie gorliwy napewno skorzysta. Całe szczęście nauczycielem nie jestem, po tym jak ten zawód niesłusznie został zmieszany z gównem. Pozdrawiam
namieszane strasznie bez sensu nie pozdrawiam