Lista jednokierunkowa, selection sort

Question

Dzień Dobry,

Otóż na ćwiczeniach z asd ostatnio zimplementowaliśmy selection sorta do listy jednokierunkowej. Mam parę pytań do was odnośnie tego kodu ponieważ teraz gdy odświeżam notatki nie bardzo przekonują mnie do poprawności tego algo

struct Node {
   Node *next;
   int value;
};
void sort ( Node *list ) {
   Node sorted; // nie powinna zostac przydzielona pamiec ?
   sorted.next = NULL;
   while ( list ->next != NULL) {
      int max = list -> next -> value;
      Node *previter = list;
      Node *iter = list -> next;
      while ( iter -> next != NULL ) {
         if ( iter -> next -> value > max ) {
            previter = iter;
            int MAX = iter -> next -> value;
         }
         iter = iter -> next;
      }
      Node * helper;
      helper = sorted.next;
      sorted.next = previter -> next;
      previter -> next = previter -> next -> next;
      sorted.next -> next = helper;
      // tych  5 linijek nie rozumiem, helper przechowuje wskaznik na NULL ?
   }
   list -> next = sorted.next; // kompletnie nie wiem
}

Jezeli na poczatku iter wskazuje na 1 element listy to a co wskazuje wtedy previter ? na liste ?

 

Answer 1

Sam w sobie kod na pewno nie działa, chociażby dla takich danych:



A dlaczego postaram się za raz sprawdzić.... 

Swoją drogą, jesteś pewien, że to CountingSort, a nie jakiś SelectionSort? Bo zliczania wystąpień to ja w tym nie widze...

Comments

A nie tak tak selesction juz zmieniam nazwe moj wielki blad :) chociaz tyle, ze cos w nim musi siedziec nie tak. Najbardziej nurtuje mnie to wskazanie na element przed gdy iter jest jako pierwszy.