Implementacja sortowania listy jednokierunkowej c++

Witam, przeczytałem już na tym forum mnóstwo tematów o sortowaniu listy jednokierunkowej i co dziwne w żadnym nie znalazłem choćby jednego dobrego normalnego przykładu z tym własnie zagadnieniem. Sam próbuje się z nim zmierzyć i napotkałem problem, zamieszczam swój kod poniżej. Sądzę że jednym z problemów może być to że odwołuje się niejako do obiektów a nie do wskaźników na te obiekty.

Za wszelkie porady , przykłady będę bardzo wdzięczny .

Z góry dzięki i pozdrawiam .

void lista :: sort_list()
{
    element *tmp = pfirst;
    int size_list = 0;
    while(tmp!=NULL)
    {
        size_list++;
        tmp = tmp->pnext;
    }
    element *wsk_previus = pfirst;
    element *wsk_actual = pfirst->pnext;

    bool zmiana ;
    while(true)
    {
        zmiana =false;
        for(int i =0;i<size_list-1;i++)
        {
            if(wsk_previus->wartosc > wsk_actual->wartosc)
            {
                zmiana = true;
                element *temp = wsk_previus;
                wsk_previus = wsk_actual ;
                wsk_actual = temp;
            }
            wsk_previus = wsk_previus->pnext;
            wsk_actual = wsk_actual->pnext;
        }
        if(!zmiana)break;
    }

}
 

if (wsk_previus->wartosc > wsk_actual->wartosc) 
{
    zmiana = true;
    element* temp = wsk_previus;
    wsk_previus = wsk_actual;
    wsk_actual = temp;
}
wsk_previus = wsk_previus->pnext;
wsk_actual = wsk_actual->pnext;

Są tutaj 2 problemy:

1. W ogóle nie modyfikujesz listy. Jedyne co robisz to robisz zamianę zawartości 2 tymczasowych wskaźników. Masz 2 wyjścia:
   a) prostsze - zamiana wartości węzłów: swap(wsk_previus->wartosc, wsk_actual->wartosc) powinno wystarczyć
   b) "prawdziwsze" - zamienić węzły co jest de facto modyfikacją pnext w 3 węzłach: przedpoprzednim, poprzednim i aktualnym
2. Jako, że zamieniłeś wsk_previus i wsk_actual ze sobą, to po wyjściu z for() one już nie wskazują na to co myślisz, że wskazują.

void lista::sort()
  {
   for(element *end=0,*stop=pfirst,*i,*p=pfirst;(p)&&(stop);p=p->pnext,end=stop)
      for(i=pfirst,stop=0;i->pnext!=end;i=i->pnext)
         if(i->wartosc<i->pnext->wartosc)
            swap(i->wartosc,(stop=(i->pnext))->wartosc);
  }

Rozbij to sobie na odrębne metody prywatne;

element *wsk_previus = pfirst;
element *wsk_actual = pfirst->pnext;
element *wsk_next = pfirst->pnext->pnext;
/*wskazniki*/
if(wsk_actual->wartosc > wsk_next->wartosc)
            {
                zmiana = true;
                element *help =wsk_next->pnext;
                wsk_previus->pnext = wsk_next;
                wsk_next->pnext =wsk_actual;
                wsk_actual->pnext = help;
            }
            wsk_previus = wsk_previus->pnext;
            wsk_actual = wsk_actual->pnext;
            wsk_next = wsk_next->pnext;
 

Wypociłem coś takiego ale nie działa, co więcej od razu widzę że tak napisany kod nie sprawdza 1 z 2 elementem w liście. Jak to można ugryźć?

spróbuj posługiwać się podwójnymi wskaźnikami element **x, zwykle to znacznie upraszcza operacje na liście jednokierunkowej.

wsk_previus = wsk_previus->pnext;
wsk_actual = wsk_actual->pnext;
wsk_next = wsk_next->pnext;

Te elementy już nie są w takiej kolejności jak myślisz, w sensie już nie jest prawdą, że prev --> actual --> next.

Wypociłem coś takiego ale nie działa, co więcej od razu widzę że tak napisany kod nie sprawdza 1 z 2 elementem w liście. Jak to można ugryźć?
Zrób atrapę, która jest przed początkiem.

element* dummy = new element;
dummy->pnext = first;

element* prev = dummy;
element* actual = first;
element* next = first->pnext;

twonek napisał(a):

wsk_previus = wsk_previus->pnext;
wsk_actual = wsk_actual->pnext;
wsk_next = wsk_next->pnext;

Te elementy już nie są w takiej kolejności jak myślisz, w sensie już nie jest prawdą, że prev --> actual --> next.

To w jakiej są? skoro "przesuwam" ja co obieg ?

Wypociłem coś takiego ale nie działa, co więcej od razu widzę że tak napisany kod nie sprawdza 1 z 2 elementem w liście. Jak to można ugryźć?
Zrób atrapę, która jest przed początkiem.

element* dummy = new element;
dummy->pnext = first;

element* prev = dummy;
element* actual = first;
element* next = first->pnext;

oke ale taki obiekt przechowujący wskaźnik na pierwszy element będę mógł wykorzystać tylko jeśli trzeba będzie zamienić element 1 z 2 , i to również trzeba jakoś specjalnie zaznaczyć w algorytmie, nie mylę
się?

jestem bliski poddania się ~~ oto moje kolejne wypociny niestety nie działają .

void lista :: sort_list()
{
    element *tmp = pfirst;
    int size_list = 0;
    while(tmp!=NULL)
    {
        size_list++;
        tmp = tmp->pnext;
    }
    /*---------------------------*/

    element *dummy = new element;
    dummy->pnext = pfirst;

    element *previus = dummy;
    element *actual = pfirst;
    element *next = pfirst->pnext;

    bool zmiana ;
    while(true)
    {
        zmiana = false;
        for(int i =0;i<size_list-1;i++)
        {
            if(actual->wartosc > next->wartosc) // poprzedni obiekt ma mniejsza wartosc od nastepnika
            {
                zmiana = true; // zachodzi zmiana
                element *help = previus->pnext;
                previus->pnext = next;
                actual->pnext = next->pnext;
                next->pnext = help;
            }
            previus = previus->pnext;
            actual = actual->pnext;
            next = next->pnext;
        }
        previus = dummy;
        actual = pfirst;
        next = pfirst->pnext;
        if(!zmiana)break;
    }
}
 

Eh jakieś porady pomysły :)?

Po przejściu przez jeden obieg pętli masz prev --> next --> actual, więc w następnej iteracji warunek

if(wsk_actual->wartosc > wsk_next->wartosc)

nie sprawdza tego co chcesz sprawdzać.

Atrapę robisz po to, żeby nie trzeba modyfikować algorytmu, nie rozpatrywać przypadku krańcowego. Przydaje się tylko na początku gdy actual == first.
Jeszcze jedna sprawa: jak lista ma tylko 1 węzeł to wsk_next->wartosc Ci się wysypie, chyba że gdzieś wcześniej zrobiłeś sprawdzenie.

if (actual->wartosc > next->wartosc)
{
    zmiana = true; 

    prev->pnext = next;
    actual->pnext = next->pnext;
    next->pnext = actual;

    actual = prev->pnext;
    next = actual->pnext;
}

Jeszcze jedna sprawa: jak lista ma tylko 1 węzeł to wsk_next->wartosc Ci się wysypie, chyba że gdzieś wcześniej zrobiłeś sprawdzenie.

Wiem zauważyłem ten problem, ale postanowiłem się nim zająć dopiero potem.

Po przejściu przez jeden obieg pętli masz prev --> next --> actual, więc w następnej iteracji warunek
if(wsk_actual->wartosc > wsk_next->wartosc)
nie sprawdza tego co chcesz sprawdzać.

Rzeczywiście nie byłem świadom tego problemu, ale teraz w pełni to rozumie rozrysowałem sobie to ładnie na kartce i faktycznie masz rację!

    actual = prev->pnext;
    next = actual->pnext; 

Rozumie również ,że to przywraca pożądany przeze mnie porządek we wskaźnikach do sortowania, niestety mimo to mój kod po modyfikacji dalej nie działa program się zwyczajnie wysypuje.

Załączam najnowszą wersje metody.

 
void lista :: sort_list()
{
    element *tmp = pfirst;
    int size_list = 0;
    while(tmp!=NULL)
    {
        size_list++;
        tmp = tmp->pnext;
    }
    /*---------------------------*/

    element *dummy = new element;
    dummy->pnext = pfirst;

    element *previus = dummy;
    element *actual = pfirst;
    element *next = pfirst->pnext;

    bool zmiana ;
    while(true)
    {
        zmiana = false;
        for(int i =0;i<size_list-1;i++)
        {
            if (actual->wartosc > next->wartosc)
            {
            zmiana = true;

            previus->pnext = next;
            actual->pnext = next->pnext;
            next->pnext = actual;

            actual = previus->pnext;
            next = actual->pnext;
            }

            previus = previus->pnext;
            actual = actual->pnext;
            next = next->pnext;
        }
        previus = dummy;
        actual = pfirst;
        next = pfirst->pnext;
        if(!zmiana)break;
    }
    delete dummy;
}

dummy usuwasz raz na samym końcu funkcji. Skoro próbujesz w pętli to usuwać to jasne, że za drugą próbą delete to się wysypie.
Albo zrób to jak pokazał @_13th_Dragon i nie musisz się bawić w usuwanie:

element dummyobj,*dummy=&dummyobj; 

void lista :: sort_list()
{
    for (element **a=&pfirst; *a; a=&((*a)->pnext)) {
         for (element **b=&((*a)->pnext); *b; b=&((*b)->pnext)) {
              if ((*a)->wartosc>(*b)->wartosc) {
                   std::swap((*a)->pnext, (*b)->pnext);
                   std::swap(*a, *b);
              }
          }
    }
}

Na głupa więc złożoność jest o(n²).

Albo bez głupa na pojedynczych:

   void sort()
     {
      node head(0,first);
      for(node *i,*end=0,*stop=first;stop;end=stop)
        {
         for(stop=0,i=&head;i->next->next!=end;i=i->next)
           {
            if(i->next->value>i->next->next->value)
              {
               stop=i->next;
               i->next=stop->next;
               stop->next=i->next->next;
               i->next->next=stop;
              }
           }
        }
      first=head.next;
     }

twonek napisał(a):

dummy usuwasz raz na samym końcu funkcji. Skoro próbujesz w pętli to usuwać to jasne, że za drugą próbą delete to się wysypie.
Albo zrób to jak pokazał @_13th_Dragon i nie musisz się bawić w usuwanie:

element dummyobj,*dummy=&dummyobj; 

dummy nie jest usuwane w pętli jest poza whilem, wiec nie jest to powodem wysypania programu :/ jakieś inne pomysły ?

maniek910 napisał(a):

jakieś inne pomysły ?

Dostałeś trzy działające wersje.
Przeanalizuj i popraw swój bajzel, lub weź odpal debuger i znajdź problem.
Nie rozumiem czego jeszcze oczekujesz?

Generalnie nie zależało mi na tym by ktoś napisał mi swoje gotowe działające rozwiązanie a właśnie pomóc znaleźć błąd w moim.

To napisz swój kod jeszcze raz, bazując na działających rozwiązaniach.

maniek910 napisał(a):

dummy nie jest usuwane w pętli jest poza whilem, wiec nie jest to powodem wysypania programu :/ jakieś inne pomysły ?

Mea culpa, źle popatrzyłem. Jeśli next jest nullem to się wysypie. A to się dzieje w ostatnim obiegu pętli, gdy i == size_list - 2.

hyy to chyba dość spory problem do ominięcia ;/ bo jeśli tak po prostu zrobię sobie że for ma się wykonywać do momentu next!=NULL to nie posortuje mi całej listy, nie mylę się prawda ?

Dlaczego nie? To jest jakieś rozwiązanie. A jeszcze prostsza jest drobna modyfikacja warunku na i < size_list - 2.