Question

Redo the insertionsort algorithm so that the values are inserted into a linked list rather than an array. This eliminates the need to move other values when a new value is inserted, since your algorithm can simply insert a new node where the new value should go. Analyze your algo- rithm to obtain a big-O expression of the worst-case running time. Code your algorithm to produce a complete C++ program that reads in a list of 10 in- tegers, sorts the integers, and then writes out the sorted list. Your program should allow the user to repeat the process and sort another list until the user says he or she wants to exit the program. code in c++

Answer 1

//C++ program

#include<iostream>
using namespace std;

class LinkedList{
   private:
       typedef struct node{
           int data;
           struct node*next;
       }node;
       node *head;
      
   public:
       LinkedList(){
           head = NULL;
       }
       ~LinkedList(){
           node*temp = head;
           node*next;
           while(temp){
               next = temp->next;
               delete(temp);
               temp = next;
           }
           head = NULL;
       }
       void append(int data){
           node *newNode = new node;
           newNode->data = data;
           newNode->next = NULL;
          
           if(head==NULL){
               head = newNode;
               return;
           }
           node* temp = head;
          
           while(temp->next){
               temp = temp->next;
           }
           temp->next = newNode;
       }
      
       void print(){
           node*temp = head;
           while(temp){
               cout<<temp->data<<" ";
               temp = temp->next;
           }
           cout<<"\n\n";
       }
      
       void sortedInsert(node** head_ref, node* new_node)
       {
       node* current;
       if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
       {
       new_node->next = *head_ref;
       *head_ref = new_node;
       }
   else
   {
   current = *head_ref;
   while (current->next!=NULL && current->next->data < new_node->data)
       current = current->next;

   new_node->next = current->next;
   current->next = new_node;
   }
   }
      
       void insertionSort()
       {
   node *sorted = NULL;
       node *current = head;
       while (current != NULL)
       {
       node *next = current->next;
       sortedInsert(&sorted, current);
  
       current = next;
       }
       head = sorted;
       }
      
       void deleteList()
       {
           node* current = head;
           node* next;
  
           while (current != NULL)
           {
           next = current->next;
           delete(current);
           current = next;
           }
           head = NULL;
       }
      
};

int main(){
   LinkedList ll;
   int num,data;
   char choice;
   do{
       cout<<"Enter number of elements want to enter : ";
       cin>>num;
       while(num--){
           cout<<"Enter element : ";
           cin>>data;
           ll.append(data);
          
       }
       cout<<"Your unsorted Linked List\n";
       ll.print();
       ll.insertionSort();
       cout<<"Sorted Linked List\n";
       ll.print();
       ll.deleteList();
       cout<<"want to continue(y/n) : ";
       cin>>choice;
   }while(choice=='y'||choice=='Y');
   return 0;
}

//sample output