Implementation of insertion sorting algorithm

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