Thread: Sorting a linked list

Hi All,

My task:

For example, existed 2 elements of linkedlist with seven numbers:

• 1 3 5 7
• 23 24 30

inserting "6" and now we must have 3 elements of linkedlist:

• 1 3
• 5 6 7
• 23 24 30

inserting "10" and 3 elements of linkedlist:

• 1 3
• 5 6 7 10
• 23 24 30

So now I have this code

Code:

#include <iostream>
 
struct nodes
{
        
        void sort();
        void push(int value);
        void pop(int* value);
        void show();
        bool is_full();
        
        int* array;
        nodes* prior;
        
        nodes(){array = new int [4];top = 0;}
        ~nodes(){delete[] array;}
        int top; 
};
//============================================================
struct linked_lists
{
 
                void show(); 
                void add(int value);
                                
                linked_lists(){tail = NULL;}
                ~linked_lists();
                nodes* tail;            
};
 
//============================================================
int main()
{
	time_t t;
	srand((unsigned) time(&t));

        linked_lists *a = new linked_lists();
 
        a->show();
        system("pause");

		for(int i=0;i<8;i++) 
		{
			a->add(rand() %50 + 0);
                        a->show();
                        system("pause");
		}
    
        
        system("cls");
        a->show();       
        system("pause");
        delete a;
        system("pause");
        return 0;
}
 
//============================================================
void nodes::push(int value)
{
        if (top>9) return; 
        array[top++]=value;
}
 
void nodes::pop(int* out)
{
        if (!top) return; 
        
        *out = array[--top];
}
 
void nodes::show()
{
        for(int i=0;i<top;i++) std::cout<<"  "<<array[i];
}
 
void nodes::sort()                                     
{ 
        int tmp, i, j;
        for ( i=0; i < top; i++)
        {  
            tmp = array[i];   
        for ( j=i-1; j>=0 && array[j] > tmp; j--)
                array[j+1] = array[j];
        array[j+1] = tmp;
        }
}
bool nodes::is_full()
{
        return (top==4);
}
 
 
// =====================================================================
void linked_lists::add(int value)
{
        if (tail==NULL) { tail = new nodes(); tail->prior=NULL;}
 
 
        if(!tail->is_full())
        {
                tail->push(value);
                tail->sort();
        }
        else 
 
        {
                nodes* node = new nodes();
                node->prior = tail;
                
                int tmp;
                for(int i=1;i<=2;i++)
                {
                        tail->pop(&tmp);
                        node->push(tmp);
                }
                tail->pop(&tmp);
                if(value<tmp) {tail->push(value);node->push(tmp);}
                else {tail->push(tmp);node->push(value);}
             
            
                
                tail = node;
                tail->sorting();
		tail->prior->sorting();
                
        }
        
}
 
 
void linked_lists::show()
{
        if(tail==NULL) {std::cout<<"\n linked-list is empty now..\n\n";return;}
        nodes* ip = tail;
        while (true)
        {
                std::cout<<ip;
                ip->show();
                std::cout<<"\n";
                if(ip->prior==NULL)     break;
                ip=ip->prior;
        }
 
}
 
linked_lists::~linked_lists()
{
        if(tail==NULL) {std::cout<<"\nmemory is free!!\n";return;}
        
        nodes* ip = tail;
        while (ip->prior!=NULL)
        {
                tail = ip;
                ip=ip->prior;
                delete tail;
        }
        delete ip;
        std::cout<<"\n memory is free!!!";      
        }
 
 
//======================================================================

And result of this is not correct, for example:

• 14 37 46 47
• 16 35
• 3 26

Thanks in advance!