C++ Program to Implement Insertion Sort

Code:

#include   iostream

using namespace std;

// A structure to represent a node.
struct list
{
int data;
list *next;
};

// Function implementing insertion sort.
list* InsertinList(list *head, int n)
{
// Creating newnode and temp node.
list *newnode = new list;
list *temp = new list;

// Using newnode as the node to be inserted in the list.
newnode->data = n;
newnode->next = NULL;

// If head is null then assign new node to head.
if(head == NULL)
{
head = newnode;
return head;
}
else
{
temp = head;

// If newnode->data is lesser than head->data, then insert newnode before head.
if(newnode->data < head->data)
{
newnode->next = head;
head = newnode;
return head;
}

// Traverse the list till we get value more than newnode->data.
while(temp->next != NULL)
{
if(newnode->data < (temp->next)->data)
break;

temp=temp->next;
}

// Insert newnode after temp.
newnode->next = temp->next;
temp->next = newnode;
return head;
}
}

int main()
{
int n, i, num;
// Declaring head of the linked list.
list *head = new list;
head = NULL;

cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

for(i = 0; i < n; i++)
{
cout<<"Enter element "<
cin>>num;
// Inserting num in the list.
head = InsertinList(head, num);
}

// Display the sorted data.
cout<<"\nSorted Data ";
while(head != NULL)
{
cout<<"->"<data;
head = head->next;
}

return 0;
}


Output:

Case 1:(average case)

Enter the number of data element to be sorted: 5
Enter element 1: 998
Enter element 2: 451
Enter element 3: 2
Enter element 4: 35
Enter element 5: 1206

Sorted Data ->2->35->451->998->1206


Case 2:(best case)

Enter the number of data element to be sorted: 5
Enter element 1: 99845
Enter element 2: 564
Enter element 3: 332
Enter element 4: 86
Enter element 5: 1

Sorted Data ->1->86->332->564->99845


case 3: (worst case)

Enter the number of data element to be sorted: 5
Enter element 1: 2
Enter element 2: 332
Enter element 3: 456
Enter element 4: 1024
Enter element 5: 16565

Sorted Data ->2->332->456->1024->16565



More C++ Programs: