Sortowanie listy przez łączenie naturalne Mariusz: https://pastebin.com/1ZcN5jku Rozdzielanie listy wydaję się działać dobrze Na innym forum jeden próbował mi przedstawić algorytm łączenia naturalnego Podał nawet pseudokod ale gdy spróbowałem na podstawie jego pseudokodu napisać listową wersję tego algorytmu to dostałem błąd segmentation fault

Pytający: Znalazłem taki mój stary kod: https://ideone.com/pb7FXG Co prawda C++, ale pisany w stylu C, więc wystarczyłoby pozmieniać referencje do wskaźników na podwójne wskaźniki, odpowiednie wywołania funkcji, konstruktory struktur na funkcje itp., i będzie C. Niby jest tam MergeSort, ale chyba bardziej to sortowanie przez łączenie naturalne (zwał jak zwał): • lista wejściowa jest rozdzielana na już posortowane listy, te posortowane fragmenty (listy) są umieszczone w cyklicznej liście (nodeQ to węzły tejże listy) − to robi funkcja Split, • następnie dopóki w ów cyklicznej liście jest więcej niż jeden posortowany fragment (while (qhead−>next != qhead)), bierzemy 2 posortowane fragmenty (listy) z brzegu i je łączymy (funkcja Merge), wrzucamy powstałą listę do jednego z węzłów (nodeQ), drugi jest zbędny więc go usuwamy i przesuwamy głowę (qhead) tej cyklicznej listy do następnego elementu, coby mieć do czynienia z potencjalnie krótszymi fragmentami (a nie tym dopiero co połączonym, ten trafia na "koniec") • na koniec nadpisujemy wskaźniki do pierwotnej listy, a ostatni węzeł listy cyklicznej można usunąć. Kolejne kroki są wypisywane, więc da radę ogarnąć co się dzieje. A co do Twojego kodu, coś za długie wydają się te funkcje rozdzielająca i łącząca, aż czytać ich się nie chce. Pewnie znacznie mógłbyś je uprościć dopisując jakieś funkcje pomocnicze (przykładowo u mnie w kodzie funkcja ShiftToEnd(node*& head1, node*& head, node*& tail) jest wywoływana w tych funkcjach, a przenosi ona po prostu głowę jakiejś listy (head1) na koniec jakiejś listy określonej przez argumenty head, tail (oczywiście zakładając poprawność danych wejściowych). A segmentation fault może być skutkiem np. próby wyłuskania wartości z nulla (dereferencji): int* p = NULL; *p = 1; https://stackoverflow.com/a/2346849

Mariusz: "(zwał jak zwał)" Są różne wersje sortowania przez scalanie więc odpowiednie nazewnictwo pozwala rozpoznać o jaką wersję nam chodzi Wersja rekurencyjna (nazywana czasem sortowaniem w dół) Wersja iteracyjna Łączenie proste (nazywana czasem sortowaniem w górę) Tutaj zakładamy że przed sortowaniem posortowane podciągi są długości 1 Każde scalenie podwaja długość posortowanych podciągów Wprowadzenie liczników byłoby przydatne ale spowodowałoby błąd przepełnienia zakresu typu int i możliwe błędne działanie Łączenie naturalne Załóżmy że klucze węzłów listy tworzą ciąg Przed sortowaniem występują w tym ciągu posortowane podciągi (nie muszą być one długości jeden) Podciągi te są rozdzielane na przemian między dwie pomocnicze listy Jeśli po etapie rozdzielania druga lista będzie pusta to możemy zakończyć algorytm Podczas scalania łączone są te posortowane podciągi i po jednorazowym wywołaniu procedury scalającej nie mamy posortowanej listy tylko na liście występują dłuższe podciągi Koniec podciągu możemy wykryć np gdy * osiągneliśmy koniec listy * prevNode−>key > currNode−>key To tak z grubsza co udało mi się przeczytać Jeśli chodzi o rekurencyjne sortowanie przez scalanie to mam wersję tablicową a jeśli chodzi o wersję listową to chętnie bym zobaczył funkcje splitBefore oraz splitAfter bo byłyby przydatne po znalezieniu węzła przed/za którym chcielibyśmy uciąć listę Jeżeli chodzi o łączenie proste to wersję tablicową powinienem mieć gdzieś na starym dysku (ostatnio skrobnąłem też dla tablic indeksowanych od jedynki) Jeśli chodzi o iteracyjne sortowanie listy to wolałbym jednak łączenie naturalne bo do rozdzielania i łączenia wykorzystuje się relacje porównania zamiast liczników które to mogą przepełnić zakres typu int Chciałem aby funkcja realizowała konkretne zadanie Można byłoby wydzielić kilka dodatkowych funkcji jak np dla quicksorta void quickSort(struct Node **head,struct Node **tail) { if((*head) != (*tail)) { pivot = Select(head,tail); curr = (*head) while(curr != NULL) { y=delHead(&curr,tail); if(y−>data < pivot−>data) tailins(y,&lowf,&lowl); else if(y−>data == pivot−>data) tailins(y,&midf,&midl); else tailins(y,&highf,&highl); } quickSort(&lowf,&lowl); quickSort(&highf,&highl); concat(&lowf,&lowl,midf,midl); concat(&lowf,&lowl,highf,highl); (*head) = lowf; (*tail) = lowl; } } I tutaj mamy sporo funkcji wykorzystywanych tylko przez jedną konkretną procedurę sortującą Koleś na innym forum podrzucił mi następujący pseudokod na którym się wzorowałem pisząc funkcję scalającą string rekordZtmp1 string rekordZtmp2 string poprzedniRekordZtmp1 = cosOdCzegoKazdyStringBedzieWiekszy string poprzedniRekordZtmp2 = cosOdCzegoKazdyStringBedzieWiekszy int koniecSeriiWtmp1 = 0 int koniecSeriiWtmp2 = 0 rekordZtmp1 = pobierzLinie( tmp1 ); rekordZtmp2 = pobierzLinie( tmp2 ); while( tmp1 != EOF || tmp2 != EOF ) while(!koniecSeriiWtmp1 && !koniecSeriiWtmp2) if ( rekordZtmp1 > rekordZtmp2 ) wpiszLinie( plikDocelowy, rekordZtmp1 ); poprzedniRekordZtmp1 = rekordZtmp1; rekordZtmp1 = pobierzLinie( tmp1 ); if ( poprzedniRekordZtmp1 > rekordZtmp1) koniecSeriiWtmp1 = 1; else wpiszLinie( plikDocelowy, rekordZtmp2 ); poprzedniRekordZtmp2 = rekordZtmp2; rekordZtmp2 = pobierzLinie( tmp2 ); if ( poprzedniRekordZtmp2 > rekordZtmp2 ) koniecSeriiWtmp2 = 2; while(!koniecSeriiWtmp1) wpiszLinie( plikDocelowy, rekordZtmp1 ); oprzedniRekordZtmp1 = rekordZtmp1; rekordZtmp1 = pobierzLinie( tmp1 ); if ( poprzedniRekordZtmp1 > rekordZtmp1) koniecSeriiWtmp1 = 1; while(!koniecSeriiWtmp2) wpiszLinie( plikDocelowy, rekordZtmp2 ); poprzedniRekordZtmp2 = rekordZtmp2; rekordZtmp2 = pobierzLinie( tmp2 ); if ( poprzedniRekordZtmp2 > rekordZtmp2 ) koniecSeriiWtmp2 = 2; koniecSeriiWtmp1 = koniecSeriiWtmp2 = 0; string poprzedniRekordZtmp1 = cosOdCzegoKazdyStringBedzieWiekszy string poprzedniRekordZtmp2 = cosOdCzegoKazdyStringBedzieWiekszy

Mariusz: A co do Twojego kodu, coś za długie wydają się te funkcje rozdzielająca i łącząca, aż czytać ich się nie chce. Pewnie znacznie mógłbyś je uprościć dopisując jakieś funkcje pomocnicze https://pastebin.com/YuCPhiYv Dopisanie tych funkcji niezbyt dużo skróciło ten kod Teraz lepiej się czyta ?

Mariusz: Wydaję mi się że koleś źle wykrywał koniec serii a także przy porównywaniu nie sprawdzał czy osiągnęliśmy koniec pliku / koniec listy (do if trzeba było dopisać warunki sprawdzające czy nie trafiliśmy na NULLa) i tak jak pisałeś dochodziło do próby wyłuskania wartości z nulla Nadal nie jestem pewny czy algorytm działa dobrze ale już przynajmniej udało mi się usunąć błędy typu segmentation fault

Pytający: "niezbyt dużo skróciło ten kod"? Pierwotnie: • Split − 74 linie, • Merge − 129 linie. Po zmianach: • Split − 37 linie, • Merge − 67 linie. To znaczące uproszczenie. Tak, lepiej się czyta. Oczywiście pozwoliłem sobie na mały refactoring, skoro już bawić się w poprawki: https://ideone.com/UGPNVA Funkcje Split i Merge jako tako skomentowałem, powinny być do ogarnięcia. Nazwy funkcji zmieniłem coby trzymać się jakiejś konwencji. Chyba wszystkie przekazywane argumenty pozmieniałem na wskaźniki, po co kopiować struktury. Zresztą nawet przy wypisywaniu tak czy siak tworzyłeś kopię kopii wskaźnika, choć śmiało mogłeś korzystać z kopii "głowy" przy przekazywaniu przez wartość. Funkcje swap dodałem, coby mieć jedną gałąź kodu zamiast dwóch w odpowiednich funkcjach (mniej kodu, mniejsza szansa na błąd, a i o zmiany/poprawki łatwiej). Asercje coby uwidocznić niezmienniki funkcji − jeśli zakładamy, że jakiś wskaźnik będący argumentem danej funkcji jest niezerowy (różny od nulla), to śmiało można dopisać taką asercję, wtedy jeśli funkcja zostanie wywołana z nullem, to asercja wywoła funkcję abort(), a Ty będziesz mógł przeczytać, że w linii k−tej programu asercja nie została spełniona i wiesz mniej więcej, gdzie szukać błędu (i możliwe, że uprzedzisz Segmentation Fault). Co do Twojego kodu − nawet mi się nie skompilował w Visual Studio, od razu kompilator słusznie zauważył, że w linii 177: if(tmpA−>data > tmpB−>data) może nastąpić dereferancja niezainicjalizowanej zmiennej − zarówno tmpA, jak i tmpB mogło nie być zainicjalizowane w tym miejscu. Więcej błędów nie szukałem − po uproszczeniu/zmienieniu paru rzeczy zdaje się hulać...

Pytający: I byłbym zapomniał, jeśli masz wskaźnik p, to do pola jakieśPole chyba prościej odwołać się: p−>jakieśPole niż: (*p).jakieśPole // takich odowołań było u Ciebie mnóstwo, też pozmieniałem (acz może tak wolisz i to było umyślne, kto wie)

Mariusz: Ja próbowałem sam bawić się kodem i oto do czego doszedłem https://ideone.com/9blNrM Dopisałem kilka rzeczy które mogłbyby zapobiec dereferencji NULLa Przeczytam twój kod i w miarę moich możliwości spróbuję porównać to co otrzymałem

Mariusz: Co do odwołania (*p).jakieśPole to chciałem zaznaczyć że używam tutaj wskaźnika zamiast referencji której w C jeszcze nie ma

Mariusz: 24 mar 20:43 Tutaj bawiłem się kodem jeszcze przed tym jak wysłałeś swoje rozwiązanie Starałem się wyeliminować przypadki gdy następuje dereferencja NULLa i jakichś niezainicjalizowanych wskaźników Pytający w swoim kodzie zgubiłeś jeden węzeł ?

Pytający: Faktycznie, zgubiłem. W tym przypadku 1 węzeł, ale ogólnie tamten kod może zgubić całą "resztę" serii, bo nie zamieniłem referencji do list (sam oszukałem się komentarzem − oto przykład na to, że komentarze nie zawsze pomagają ). Poprawione: https://ideone.com/5cSdal // patrz linia 203 Co do "p−>x" to jest to właśnie skrócony zapis "(*p).x" i służy właśnie do dereferencji. Widząc takową strzałkę wiesz, że masz do czynienia ze wskaźnikiem (mowa o C). W działaniu to jedno i to samo. // https://stackoverflow.com/a/2575050

Mariusz: Moja wcześniejsza poprawka tego kodu też czasami gubi węzły https://ideone.com/9blNrM

Pytający: linie 186, 206 // warunek "poprzedniZtmpA == NULL" jest zbędny, poprzedniZtmpA nie może w tym miejscu być nullem, przecież parę linijek wyżej to na co wskazuje dorzucasz do listy L linie 196, 216 // jw. (ten sam kod tylko dla B) Warunki zbędne, ale nijak szkodliwe. Błąd jest w warunku w linii 176 − to, że listy są puste nie znaczy, że nie został węzeł w tmpA lub w tmpB.

Mariusz: Błąd jest w warunku w linii 176 Jak się dalej pobawiłem tym kodem to też do tego doszedłem Wiesz co mnie naprowadziło na ten błąd ? Przypadki brzegowe np lista z jednym węzłem W kodach źródłowych jakie widziałem często pomijano poprawność przypadków brzegowych itp poprzedniZtmpA == NULL Jeszcze w tym samym warunku wyłuskuje dane z adresu i to było po to aby upewnić się że nie będziemy wyłuskiwać danych z nulla aczkolwiek masz rację że jest zbędny

Mariusz: A jest jeszcze taka dość ważna umiejętność jak czytanie kodu często pomijana w tych tutorialach itp Gdy zacząłem czytać kod tej funkcji scalającej od początku to zauważyłem że dla przypadków brzegowych węzły nie zostaną wstawione do listy wynikowej

Mariusz: Tak sobie pomyślałem że w przypadku listy dwukierunkowej każdy węzeł zawiera wskaźnik na poprzednika więc wydaje się że zmienne lokalne wskazujące na poprzednika można by usunąć wyodrębniając jakiś przypadek brzegowy Jeśli chodzi o uogólnianie to w C mamy możliwość zmiany typu danych z int na void * oraz podania funkcji porównującej jako argument funkcji sortujących W C++ mielibyśmy referencję, szablony, a z przeciążaniem operatorów byłbym ostrożny bo jak widzieliśmy w przypadku otoczki tam funkcja porównująca pobierała trzy argumenty