Skip to content

Instantly share code, notes, and snippets.

@rishkarajgi

rishkarajgi/insertion.cpp

Created May 26, 2015 21:55
Show Gist options
  • Save rishkarajgi/d74b841735eb6ffda48d to your computer and use it in GitHub Desktop.
Save rishkarajgi/d74b841735eb6ffda48d to your computer and use it in GitHub Desktop.
Download ZIP
Insertion sort in a linked list
Raw
insertion.cpp
#include<iostream>
using namespace std;
struct node
{
int data ;
node * next ;
};
class list
{
private :
node *head ;
public :
list()
{
head = NULL ;
}
void add(int x)
{
node *t = head;
node * temp = new node();
temp -> data = x ;
if(t==NULL)
{
temp->next = NULL;
head = temp ;
}
else
{
while(t->next !=NULL)
{
t = t->next ;
}
temp->next = t->next ;
t->next = temp ;
}
return ;
}
void sort()
{
int a , b , pos=1 , i ;
node *t = head ;
node *p ;
while(1)
{
p = head ;
a = t->data ;
t = t->next ;
if(t==NULL)
break ;
b = t->data ;
if(b<a)
{
i=pos ;
while(p->data < b)
{
p = p->next;
i--;
}
while(i--)
{
a = p->data ;
p->data = b ;
b=a ;
p = p->next ;
}
p->data = b ;
}
pos++ ;
}
}
void print()
{
node * t = head ;
while(t!=NULL)
{
cout << t->data << " " ;
t = t->next;
}
}
};
int main()
{
list l ;
int a ;
char ch = 'y' ;
while(ch=='y')
{
cout << "Enter a number : ";
cin >> a ;
l.add(a);
cout << "Enter another number ? : ";
cin >> ch ;
}
cout << "List is : " ; l.print();
l.sort();
cout << "\nSorted list is : " ; l.print();
return 0 ;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment