linkedlist

[vamsi.rgiit]

help me with this code please.this code is for selection sort using linked list.please check it and give me suggestion.

#include<iostream.h>
#include<conio.h>
void main()
{
  struct mylist{
    mylist * nxt;
    int val;
  };
  int a,b,c,d=1,i,j;mylist * t;
  clrscr();
  cout<<"Enter the no&the total no of numbers";
  cin>>a>>b;
  mylist * head=new mylist;
  head=NULL;
  mylist * newnode=new mylist;
  newnode->val=a;
  newnode->nxt=head;
  head=newnode;
  for(i=1;i<b;i++)
  {
    d=1;
    cout<<"Enter the next number";
    cin>>c;
    mylist * newnode=new mylist;
    newnode->val=c;
    for(j=1;j<=i;j++)
    {
      if(newnode->val<head->val)
      {

        if(d==1)
        {
          newnode->nxt=head;
          head=newnode;
        }
        if(d==b)
        {
          newnode->nxt=NULL;
          t->nxt=newnode;
        }
        if(1<d<b)
        {
          newnode->nxt=head;
          t->nxt=newnode;
        }
      }
      else
      {
        t=head;
        head=head->nxt;
        d=d+1;
      }
    }
  }
  cout<<"the new order is:\n ";
  while(head)
  {
    cout<<head->val<<" ";
    head=head->nxt;
  }
  getch();
}

[Narue]

>please check it and give me suggestion.
Um...no. We're not going to error check your homework for you; that's your job. If you have a specific problem or question, we'll be happy to assist.

[Lerner]

I think your idea of selection sort is off. To me, selection sort means taking an existing container and then sorting it, rather than sorting it while you add items to it---which sounds like insertion sort to me, and appears to be what you are doing with your code. To use selection sort to sort a list I would use two separate sections, one to create the list and one to sort it.

My understanding of the underlying principle of selection sort is to:
1) create a temporary variable to hold the location of the smallest item in the collection
2)assume the first item in the collection is the smallest.
3)compare it with the next item in the collection
4)if the next item is smaller than the current smallest store it in the temporary variable
5)repeat the comparison with every other item in the list so in the end you have the smallest item this time through the list
6)remove the smallest item from where it is and make it the first item.
7)go to the second item in the list and eventually remove the next smallest from where it is and make it the second in the list
8)repeat the process taking the smallest in the remaining unsorted section of the list and adding it to the end of the sorted section until you have the entire list sorted

[vamsi.rgiit]

I think your idea of selection sort is off. To me, selection sort means taking an existing container and then sorting it, rather than sorting it while you add items to it---which sounds like insertion sort to me, and appears to be what you are doing with your code. To use selection sort to sort a list I would use two separate sections, one to create the list and one to sort it.

My understanding of the underlying principle of selection sort is to:
create a temporary variable to hold the location of the smallest item in the collection
assume the first item in the collection is the smallest.
compare it with the next item in the collection
if the next item is smaller than the current smallest store it in the temporary variable
repeat the comparison with every other item in the list so in the end you have the smallest item
exchange the smallest item with the first item.
go to the second item in the list and eventually replace the second smallest with the second in the list
repeat the process until you have the entire list sorted

sorry its mistake to type selection its insertion.

[Lerner]

If you're interested my initial version of pseudocode for implementing an insertion sort algorhythm for a singly linked list would be something like this:

//using input, create a list where each value from head to tail is in ascending order

declare head and current to be pointers to type mylist

declare a new mylist object using dynamic memory
assign member variables of the new mylist object values based on input

if list empty
  assign the new mylist object to head

else  
  if new mylist object->value less than head->value
    //make new mylist object the new head
    assign head to new mylist object->next
    assign new mylist object to head

  else

    //find first value in list that is equal to or greater than value in new mylist object
    while current not last node in list and current->next->value less than value in new mylist object
       assign current->next to current

    if current is last node in list  //then value in new mylist object is larger than anything in list so far
       assign new mylist object to current->next

    else  //insert new mylist object between current and current->next
       assign current->next to new mylist object->next
       assign new mylist object to current->next