Implementation of insertion sorting algorithm
/*
* implementation of insertion sorting algorithm in C
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
enum BOOL {FALSE, TRUE};
typedef int BOOL;
struct NODE;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
typedef int DataType;
struct NODE{ // single link list node
DataType data;
PtrNode next;
};
// vital ones>>>>>>>>>>>>>>>>>>>>>>>>>
PtrNode NewList() // returns the List's header
{
PtrNode tempNode = malloc(sizeof(Node));
tempNode->next = NULL;
return tempNode;
}
Position NewNode() // creates a new node
{
return malloc(sizeof(Node));
}
void Delete(PtrNode node)// deletes the node
{
free(node);
}
BOOL IsLast(List L, Position pos) // checks id the given position is last in the list
{
return (pos->next == NULL);
}
void Insert ( List L, DataType data, Position pos)// inserts a data field in a particular position
{
Position tempPos;
tempPos = NewNode(); // creates and allocates memory space
if(tempPos == NULL)
{
fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
return;
}
tempPos->data = data;
tempPos->next = pos->next;
pos->next = tempPos;
}
Position FindEnd(List L) // finds the end of the list
{
Position tempPos=L;
while(!IsLast(L, tempPos))
tempPos = tempPos->next;
return tempPos;
}
void DisplayElement(DataType element) // displays an individual element
{
printf("%d\n", element);
}
void Display (List L) // this function displays the list's contents linearly
{
Position pos = L->next;
if(pos == NULL)
return;
while (pos != NULL)
{
DisplayElement(pos->data);
pos = pos->next;
}
}
void inseartionSort(List L) //sorts the list
{
if(L->next == NULL || L->next->next == NULL)
return; // if the list contains 0 or 1 element
Position posTop = L->next->next, tempPos, delPos;
Position topPrev = L->next;
DataType data1;
while(posTop != NULL)
{
tempPos = L;
while(tempPos != posTop)
{
data1 = posTop->data;
if(tempPos->next->data < posTop->data )
{
Insert(L, data1, tempPos);
delPos = posTop;
posTop = posTop->next;
Delete(delPos);
topPrev->next = posTop;
break;
}
tempPos = tempPos->next;
}
if(tempPos == posTop)
{
topPrev = topPrev->next;
posTop = posTop->next;
}
}
}
int main()
{
List L = NewList(); // creates a new list
int n, i, data;
Position top = L;
printf("enter size of list");
scanf("%d", &n);
if(n < 2 )
{
fprintf(stderr,"invalid list size. The size cannot be lesser than 2");
getch();
return -1;
}
printf("enter elements: ");
for(i=0; i<n; i++)
{
scanf("%d", &data);
Insert(L, data, top);
top = top->next;
}
inseartionSort(L); // sorts the list
printf("\nsorted list:\n");
Display(L);
getch();
return 0;
}
copyright (c) 2015 K Sreram.
About my blog
No comments:
Post a Comment