Write a program to sort a list using insertion sort.
/*
* Node of list
*/
struct node {
int data;
struct node* next;
};
typedef struct node* nodeptr;
int data;
struct node* next;
};
typedef struct node* nodeptr;
/*
* Insert a node into its sorted position
*/
void SortedInsert(nodeptr* head, nodeptr newNode)
{
nodeptr currentNode = *head;
nodeptr prevNode = NULL;
while(currentNode != NULL && currentNode->data < newNode->data) {
prevNode = currentNode;
currentNode = currentNode->next;
}
newNode->next = currentNode;
if(prevNode == NULL)
*head = newNode;
else
prevNode->next = newNode;
}
* Insert a node into its sorted position
*/
void SortedInsert(nodeptr* head, nodeptr newNode)
{
nodeptr currentNode = *head;
nodeptr prevNode = NULL;
while(currentNode != NULL && currentNode->data < newNode->data) {
prevNode = currentNode;
currentNode = currentNode->next;
}
newNode->next = currentNode;
if(prevNode == NULL)
*head = newNode;
else
prevNode->next = newNode;
}
/*
* Insert Sort List
*/
void InsertSort(nodeptr* head)
{
nodeptr current = *head;
nodeptr list = NULL;
nodeptr next = NULL;
while(current!= NULL)
{
next = current->next;
SortedInsert(&list,current);
current = next;
}
*head = list;
}
No comments:
Post a Comment