Selection sort a linked list

[warkmich]

Hello,
I am trying to programm a linked list with some extra methods, which are "sum", which adds up all the numbers in the linked list(isEmpty is implemented). The second function returns the size of the list (list_size) and the typical at function, which is most likely used for strings (list_at) to return a specific position out of the list. I want the last function to sort the list with a selection sort algorithm, which is my biggest problem right now, because I am new to pointers. Can you look at my implementation and give me some feedback/corrections?

int sum(const LinkedList& list){
    int i,sum = 0;
    if(list.isEmpty())
        return 0;
    else
        while(list_at(i)!=nullptr){
            sum += list_at(i);
            i++;
        }
    return sum;
}

int LinkedList::list_size(struct LinkedList* head) const{
    if (head == NULL)
        return 0;
    return 1 + list_size(head->next);
}

int LinkedList::list_at(int i) const{
    int counter = 0;
    ListElement* p=head;
        while ( i != counter){
            p=p->next;
            counter++;
        }
    return p;
}

struct node
{
 int data;
 struct node *next;
};

struct node *head,*head1;

void Selection_sort()
 {
  struct node *t,*t1,*t2,*t3;
  t1 = head;
  head1 = head;
  if(head == NULL)
    cout << "The list is empty" ;
  else
  {
    while( (t2 = t1 -> next)  !=  NULL)
    {
      while(t2 != NULL)
      {
        t3 = t2 -> next;
        if( t1 -> data   >   t2 -> data)
        {
          t2 -> next = t1;
          for(t = t1; t -> next != t2;t = t -> next);
          t -> next = t3;
          t1 = t2; 
          t2 = t3; 
        } 
        else
        {
          t2 = t3;
        }
      } 

      if(head == head1) 
      {               
       head = t1;
       head1 = t1 -> next;
      }  
      else
      {
        for(t = head;t -> next != head1; t = t -> next);
        t -> next = t1;
        head1 = t1 -> next;
      } 
      t1 = t1 -> next;
    } 
  }
}  

[jonnin]

first, feedback.
assuming you already have 2 functions in your class somewhere : 1 that inserts a new node, and one that deletes a node. Is this correct?
if so, one way to do it is
*find the smallest value in the list*
*delete it from the list using existing debugged code*
*insert at top using existing debugged code*
repeat, but ignore the first value, second iteration, ignore first and second value, ... when searching for the smallest.

or similar, make a new list.
find largest value in old list.
delete it using debugged existing routine.
insert at top of new list.

for either one you can get fancy and avoid new/delete pairs by careful reuse of the node pointers but that is an advanced enhancement to it.

this will minimize the hands-on pointer stuff inside the sort, and make it a lot easier to debug.

second: someone new to pointers (and possibly everyone) should probably not be doing this:
while( (t2 = t1 -> next) != NULL)
Its fine, if you understand it, ok. But its a little cryptic and at least intermediate level stuff -- if this were the problem can you debug it and fix it?

[warkmich]

Yea, that's true, so maybe something like this? :)

  void selection_sort(struct Node*temp){
  struct Node*sort_node=NULL,*help=NULL;
  int sort_value; 
  while (temp){
    sort_node=temp;
    help=temp->next;
    //find smallest element
    while(help){
    if(help->data<sort_node->data){
      sort_node=help;
     }
      help=help->next;
    }
    if(sort_node!=temp){
      //interchange node data
      sort_value=sort_node->data;
      sort_node->data=temp->data
      temp->data=sort_value;
    }
    //next node
    temp=temp->next;
  }
}

[jonnin]

does it work now? Its a bit of trouble to run on my end. It looks OK but looks can be off.

[warkmich]

Yea, now it does! Thank your for the help and have nice easter days!

[jonnin]

I did nothing but muse at you (literally inspired you to get to work), you did it yourself. Great job! Happy easter!