C++ Wytłumaczenie sortowania przez scalanie

adrian.lodz · 23 Listopad 2016 15:42

Tak jak w temacie prosiłbym o wytłumaczenie mi sortowania przez scalanie.

Ogólnie zasadę znam, że najpierw trzeba dzielić aż będą pojedyncze elementy, a później wszystko połączyć.

Ale kod mi nie wychodzi.

Dzielenie tablicy jest, i scalanie również a liczby nie są posortowane.

#include <iostream>

#include "../moje_biblioteki/wypelnianie_i_wypisywanie_tablicy.cpp"

using namespace std;

void scal(uint *tab,uint *t,uint pocz,uint srodek,uint size)

{

    uint i=pocz,j=srodek,q=pocz;

    for(;i<srodek&&j<size;)

    {

        if(tab[i]<tab[j])t[q++]=tab[i++];

        else t[q++]=tab[j++];

    }

    t[q++]=tab[i++];

}

void sortowanie(uint *tab,uint *t,uint pocz,uint size)

{

    //cout<<"\nw funkcji sortowanie\n";

    if(pocz<size)

    {

        uint srodek=(size+pocz)/2;

        //cout<<endl<<pocz<<" "<<srodek<<" "<<size<<endl;

        sortowanie(tab,t,pocz,srodek);

        sortowanie(tab,t,srodek+1,size);

        scal(tab,t,pocz,srodek,size);

    }

}

int main()

{

    uint n;

    cout<<"Podaj rozmiar tablicy: ";

    cin>>n;

    uint tab[n];

    uint t[n];

    wypelnij_tablice(tab,n);

    wypisz_tablice(tab,n);

    sortowanie(tab,t,0,n);

    wypisz_tablice(t,n);

    return 0;

}

Fizyda · 23 Listopad 2016 17:08

Nie wiem co za algorytm zaimplementowałeś, ale to nie ten. W ogóle tu nie ma sortowania.

Poza tym z jakiegoś powodu próbujesz zapisać teoretycznie posortowaną tablicę tab do nowej tablicy t, a wyświetlasz za każdym razem pierwszą nieposortowaną, więc ciężko nawet stwierdzić jak bardzo źle sortuje Twój algorytm.

adrian.lodz · 24 Listopad 2016 14:53

Wyświetlanie tablicy t poprawione. Chciałem żeby posortowane liczby wędrowały do tablicy t, a potem tablica t żeby była wypisana. Ale nie rozumiem kompletnie jak ten algorytm ma sortować liczby. Jak patrzyłem w necie, to sortowanie przez scalanie piszą dla dwóch posortowanych tablic, żeby je połączyć. A jak to zrobić dla jednej tablicy nie posortowanej? Kompletnie nie rozumiem algorytmu sortowania przez scalanie. Najpierw dzieli na pojedyncze liczby a później jakoś łączy, ale jak?

Podejrzewam że problem tkwi w funkcji scal.

drobok · 24 Listopad 2016 15:10

https://en.wikipedia.org/wiki/Merge_sort łopatologiczny obrazek

adrian.lodz · 24 Listopad 2016 15:45

Dzielenie na pewno działa u mnie. Ale jak po rozdzieleniu scalić to?

Fizyda · 24 Listopad 2016 16:13

Szczerze mówiąc to wcale nie musisz “fizycznie” dzielić tej tablicy, możesz ją zostawić a tylko ograniczać w kolejnym etapie sortowania zakres sortowania do mniejszej liczby elementów.

Dopóki nie zrozumiesz zasady działania algorytmu to go nie zaimplementujesz.

adrian.lodz · 24 Listopad 2016 18:15

I chyba nie zrozumiem zasady działania tego algorytmu

kostek135 · 24 Listopad 2016 19:36

http://simplestcodings.blogspot.com/2010/08/merge-sort-implementation-in-c.html

Na oko brakuje ci obsługi przypadku, gdy przesuwanie głowicy na jednym z podciągów skończy się wcześniej, a w szczególnym przypadku, co jeżeli wszystkie elementy powiedzmy lewego podciągu są mniejsze od dowolnego elementu z prawego podciągu?

Jaki jest cel ostatniej linijki w funkcji scal?

adrian.lodz · 29 Listopad 2016 08:57

Dobra. Obecnie mam coś takiego:

void scal(int *tab,int *t,int pocz,int srodek,int size)

{

    int i=pocz,j=srodek,q=pocz;

    for(;i<srodek && j<size;)

    {

        if(tab[i]<tab[j])t[q++]=tab[i++];

        else t[q++]=tab[j++];

    }

    if(i<srodek)

    {

        while(i<srodek)

        t[q++]=tab[i++];

    }

    else if(j<size)

    {

        while(j<size)

        t[q++]=tab[j++];

    }

}

Podobne trochę do rozwiązania ze strony merge-sort-implementation

W każdym razie na początku. Ale i tak nie rozumiem reszty funkcji merge.

Nie wiem. Jakieś niezrozumiałe to dla mnie

kostek135 · 29 Listopad 2016 18:20

Ale to czego nie masz to już tylko for.

To co robią instrukcje które masz, to scalają z użyciem dodatkowej pamięci. T jest tablicą pomocniczą. Oczywiście da się scalić w miejscu, ale zrobienie tego efektywnie nie jest trywialne jakby się mogło wydawać Jeśli robisz to z pomocniczą pamięcią to na koniec musisz z tej pomocniczej tablicy t nanieść wynik na tab.

EDIT
Zobacz też, że w main w linku wypisywana jest tablica a, czyli twoja tab, a nie t. T jest tylko pomocnicze. Aby mieć gdzie zrzucać elementy w k-tym kroku scalania.

adrian.lodz · 2 Grudzień 2016 09:26

Dodałem fora, ale to nic nie dało.

I tak ciąg liczb nie jest posortowany.

A kod całkowicie wygląda tak (żeby nie trzeba było przewijać strony do góry):

#include <iostream>

#include "../moje_biblioteki/wypelnianie_i_wypisywanie_tablicy.h"

using namespace std;

void scal(int *tab,int *t,int pocz,int srodek,int size)

{

    int i=pocz,j=srodek,q=pocz;

    for(;i<srodek && j<size;)

    {

        if(tab[i]<tab[j])t[q++]=tab[i++];

        else t[q++]=tab[j++];

    }

    if(i<srodek)

    {

        while(i<srodek)

        t[q++]=tab[i++];

    }

    else if(j<size)

    {

        while(j<size)

        t[q++]=tab[j++];

    }

    for(uint i=pocz;i<size;i++)

    {

        tab[i]=t[i];

    }

}

void sortowanie(int *tab,int *t,int pocz,int size)

{

    //cout<<"sortowanie pocz: "<<pocz<<" size: "<<size<<endl;

    int srodek;

    if(pocz<size)

    {

        srodek=(size+pocz)/2;

        sortowanie(tab,t,pocz,srodek);

        sortowanie(tab,t,srodek+1,size);

        scal(tab,t,pocz,srodek,size);

    }

}

int main()

{

    int n;

    cout<<"Podaj rozmiar tablicy: ";

    cin>>n;

    int tab[n];

    int t[n];

    wypelnij_tablice(tab,n);

    wypisz_tablice(tab,n);

    sortowanie(tab,t,0,n);

    wypisz_tablice(tab,n);

    return 0;

}

Fizyda · 2 Grudzień 2016 09:54

Opisz swoimi słowami na czym polega algorytm bo moim zdaniem nie rozumiesz jego działania.

adrian.lodz · 2 Grudzień 2016 10:03

Najpierw dzieli cały ciąg na pojedyncze ciągi-liczby, a później jakoś je łączy. Fakt. Nie rozumiem jak to działa. Sortowanie przez wstawianie ledwo zrobiłem, a z tym się męczę już drugi tydzień jak nie dłużej.

Jakoś dzieli to na pojedyncze liczby a później porównuje dwie liczby do siebie, następne dwie liczby i tak do zakończenia liczb, później te ciągi składające się z dwóch liczb, są porównywane do siebie, wychodzą z tego ciągi po cztery, potem te ciągi znowu są do siebie porównywane itd.

Fizyda · 2 Grudzień 2016 10:38

A znasz pojęcie funkcji rekurencyjnej? Bo bez tego tego zadania nie zrobisz, a przynajmniej będzie bardzo trudno.

Twój opis jest nie do końca dobry. Sortowanie przez scalanie odbywa się w następujący sposób:

dzielisz ciąg o długości X, na N podciągów, najczęściej wystarczają 2 i na tym można się skupić
na każdym podciągu wykonujesz rekurencyjnie wszystkie punkty do momentu aż ciąg będzie już niepodzielny czyli będzie miał 1 wartość, w tedy zwracasz jednoelementowy ciąg
zwrócone ciągi łączysz porównując kolejno wartości pierwszy element z pierwszego ciągu z pierwszym elementem drugiego ciągu i wstawiasz najmniejszy, większą wartość porównujesz z kolejnym elementem ciągu którego element był najmniejszy, za każdym razem wstawiasz do nowego ciągu najmniejszy element
zwracasz utworzony w pkt. 3 ciąg

Jak zaimplementujesz te punkty masz działający algorytm. Jeśli nie rozumiesz zasady działania funkcji rekurencyjnej, albo dalej nie czujesz jak odbywa się sortowanie to nie wiem czy uda Ci się napisać ten algorytm.

EDIT:

Co do samego kodu to nie rozumiem 90% rzeczy po co one się tam znajdują i jakie jest ich zadanie. Możesz opisać co chciałeś zrobić i po co w poszczególnych linijkach?

adrian.lodz · 2 Grudzień 2016 10:59

Pisałem pod wzór z tej strony: merge-sort-implementation-in-c

A rekurencja też u mnie kuleje

Fizyda · 2 Grudzień 2016 12:16

Używasz q tutaj:

if(i<srodek)



    {



        while(i<srodek)



        t[q++]=tab[i++];



    }

gdzie kilka linijek wyżej je iterowałeś i nie zresetowałeś jego wartości, to nie ma prawa zadziałać. Nawet źle przepisałeś działający przykład, pozmieniałeś pętle bezmyślne for na while i odwrotnie i liczysz na to że zadziała. Pozamieniałeś też warunki. Nadal wyświetlasz nieposortowaną tablice, ja nie wiem czego oczekujesz. Cały czas masz te same błędy.

Bez rozumienia rekurencji nie napiszesz tego algorytmu, chyba że w sposób nie rekurencyjny, ale w takim wypadku musisz go pisać zupełnie inaczej. Dodatkowo nie wiem czy ma to jakiś sens bo an podstawie tego i podobny algorytmów uczy się właśnie funkcji rekurencyjnych w szkołach.

kostek135 · 2 Grudzień 2016 19:18

@adrian.lodz
Jest prawie dobrze, użytkownika @Fizyda to bym nie słuchał, bo bzdury gada o niezerowaniu q i wypisywaniu złej tablicy. Zapewne sam w życiu merge sort nie napisał. Zresztą skoro 90% kodu nie rozumie, to chyba wystarczy za autokomentarz… Podsyłam link na ideone, który wskazuje 6 miejsc z błędem + implementuje hipotetycznie twojego include, bo tam też mogłeś mieć jakieś błędy: http://ideone.com/aZmine

stdout będzie się trochę różnił od tego co masz w konsoli lokalnie, bo ideone nie wyświetla danych wejściowych na wyjściu, bo wprowadza je przekierowaniem strumienia. Wynikiem jest ostatnia linia.

adrian.lodz · 3 Grudzień 2016 10:56

Dobra. Dzięki za stronkę ideone.com. Ale i tak ciężko mi załapać ten algorytm. Poczekam może na korki które mam we wtorki. Może na kartce jak ktoś mi rozpisze co i jak to załapię o co chodzi. Bo nie czuję tego.

Fizyda · 3 Grudzień 2016 15:17

Zobacz, to nie jest takie trudne. W sortowaniu przez dzielenie lub scalanie zwał jak zwał, chodzi o to że dzielisz jakiś dany zbiór na mniejsze i je “sortujesz”. Jest to po to że łatwiej (szybciej) posortować mniejszą ilość rzeczy lub scalić już posortowane dwie różne listy. Sortowanie w tym algorytmie odbywa się jakby od góry “stosu” rekurencyjnego. Przykład:

Mamy następującą listę liczb do posortowania:

1: (1, 0, -4, 5, 7, 6, 3)

dzielisz to teraz na dwie mniejsze listy, załóżmy że zaokrąglamy w dół czyli jedna ma 3 elementy druga 4:

2: (1, 0, -4) (5, 7, 6, 3)

teraz z każdą listą robisz dokładnie to samo

3: (1) (0, -4) (5, 7) (6, 3)

gdy mamy jedną liczbę w liście to nic z nią nie robimy a kolejne dzielimy dalej

4: (0) (-4) (5) (7) (6) (3)

teraz mamy sześć list po jednym elemencie i jedną również jednoelementową, ale w poziomie niżej. Niżej ponieważ dół tego drzewka jest jakby szczytem od którego zaczyna się sortowanie, szczytem - górą o której wspominałem wcześniej.

Gdy już mamy taką sytuację to te jednoelementowe listy łączymy ze sobą ustawiając ich elementy w kolejności rosnącej i taką listę zwracamy do poziomu niższego.

W najwyższym (4) poziomie nasze posortowane listy będą wyglądały następująco:

4: (-4, 0) (5, 7) (3, 6)

takie listy zwracamy do poziomu niższego (3) teraz sytuacja na tym etapie wyglądać będzie tak:

3: (1) (-4, 0) (5, 7) (3, 6)

znów łączymy listy biorąc np. pierwszy element z pierwszej listy i pierwszy z drugiej, porównujemy który jest niższy i zapisujemy go. Ponieważ listy już są posortowane to teraz jest tylko kwestia taka by połączyć te listy, będzie to wyglądało mniej więcej tak:

dla list - (1) oraz (-4, 0):

1 jest większa od -4 więc zapisuję -4 do nowej listy; nowa lista: (-4)

znów 1 porównuję z kolejnym elementem drugiej listy, czyli z 0, jedynka znów większa od zera więc dodaję zero; nowa lista: (-4, 0)

ponieważ nic nie mam w drugiej liście to wszystkie elementy w pierwszej są na pewno posortowane już i większe od wpisanych liczb do nowej listy więc spokojnie mogę ją przepisać, tak uzyskujemy wynik:

(-4, 0, 1)

dla list - (5, 7) oraz (3, 6)

porównujemy 5 i 3, zapisujemy 3; nowa lista: (3)

porównujemy 5 i 6, zapisujemy 5; nowa lista: (3, 5)

porównujemy 7 i 6, zapisujemy 6; nowa lista: (3, 5, 6)

koniec drugiej listy zapisujemy liczby z pierwszej; nowa lista: (3, 5, 6, 7)

zwracamy dwie listy i w poziomie 2 mamy zwrócone takie listy:

2: (-4, 0, 1) (3, 5, 6, 7)

porównujemy -4 i 3, zapisujemy -4; nowa lista (-4)

porównujemy 0 i 3, zapisujemy 0; nowa lista (-4, 0)

porównujemy -1 i 3, zapisujemy -4; nowa lista (-4, 0, 1)

doszliśmy do końca pierwszej listy można zapisać drugą bo jest posortowana; nowa lista (-4, 0, 1, 3, 5, 6, 7)

zwracamy listę, która właściwie jest naszym wynikiem

1: (-4, 0, 1, 3, 5, 6, 7)

Teraz najważniejsze, za każdym razem budując kolejny poziom wywołujemy tą samą funkcję (rekurencyjnie), ale wysyłając do niej mniejsze listy i dopiero gdy uzyskami jednoelementową listę to ją zwracamy, w ten sposób poziom niższy po prostu połączy dwie jednoelementowe listy, czyli sortowanie odbywa się w momencie łączenia listy.

Kolejna uwaga, nie jest nigdzie powiedziane że trzeba wywołać rekurencyjnie funkcję sortującą na jednoelementowej liście, można w tym momencie na podstawie tych elementów stworzyć nową listę. Będzie to wydajniejsze, ale taka implementacja nie pokaże w piękny sposób rekurencji w tym algorytmie, ona nadal będzie, będzie poprawna, lecz nie do końca przejrzysta dla osoby uczącej się.

Tak naprawdę to to co rozpisałem w komputerze tak nie będzie działało. Będzie to wyglądało tak że najpierw zostanie rozwinięta gałąź dla lewej listy a dopiero potem dla prawej, będzie tak dla każdej kolejnej listy.

A na koniec skoro masz już działający algorytm to tutaj masz ode mnie moim zdaniem prościej napisane, uważam że łatwiej będzie Ci zrozumieć na podstawie tego kodu. Oczywiście jest tutaj kilka rzeczy do poprawy, np. wyodrębnienie fragmentu scalania dwóch tablic do osobnej funkcji, nie zrobiłem tego specjalnie byś poczuł o co chodzi, kolejną rzeczą mogłaby być optymalizacja. Zamiast tworzyć nowe tablice i przepisywać do nich wartości lepiej byłoby przekazywać cały czas tą samą, ale z ograniczeniami jakie próbowałeś stosować, czyli początek i koniec, trzeba jednak przy tym pamiętać że inaczej będzie wyglądał algorytm scalania. Nie będzie można bezpośrednio przepisywać wartości do sortowanej tablicy lecz trzeba będzie użyć jakieś dodatkowej zmiennej tymczasowej. Myślę że powinieneś wiedzieć o co chodzi, a jak nie poczytaj o zamianie wartości dwóch zmiennych, gdy masz zmienną a = 3 i b =7 jak zrobić by a = 7 natomiast b = 3.

http://ideone.com/4zc1OT

Co do tego co napisał @kostek135

Polecam uważniejsze czytanie, nie rozumiem po co znajduje się tam 90% rzeczy, ponieważ całość można napisać dużo prościej. Dodatkowo nie jestem fanem dawania rozwiązań zadań szkolnych zwłaszcza takich które czegoś uczą.

Pewne rzeczy które wskazałeś jako błąd nie były błędne. Wszystko zależało od implementacji i akurat wskazałeś błąd który w implementacji autora nie był nim, dopiero gdy wprowadziłeś swoje zmiany stał się błędem.