Insertion Sort : Python Code & Linked List implementation

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

Python Code

import random
def InsertionSort():
    N = input("Enter the number of elements in the list:")
    unsortedList = [0 for i in range(N)]
    for i in range(N):
        """ user input can be taken here"""
        unsortedList[i] = int(random.random()*N)
        i = i + 1
    print 'Unsorted list is:',unsortedList
    i = 0
    sortedList = [0 for i in range(N)]
    sortedList[0] = unsortedList[0]
    """ counter holds the number of elements inserted in the sorted list"""
    counter = 1
    for i in range (N-1):
        i = i + 1
        temp = counter
        while unsortedList[i] < sortedList[counter-1] and counter > 0:
            sortedList[counter] = sortedList[counter-1]
            counter = counter - 1
        sortedList[counter] = unsortedList[i]
        temp = temp+1
        counter = temp
    print 'Sorted list is:',sortedList           
InsertionSort()   

Addition of positive numbers using linked list: C code

Addition of large positive integers in C is quite difficult since there will be overflow error once the range of 'int' is crossed. But this problem can be overcome by the use of linked list. Happy addition! 



#include<stdio.h>
#include<stdlib.h>
struct numberList {
    int data;
    struct numberList *nextDigit;
    struct numberList *revDigit;
    };
    typedef struct numberList node;
void inputNumber(node*);
void display(node*,int);   
void addNumber(node*,node*);
int main() {
   
    node *firstNumber,*secondNumber,*sum;
    firstNumber = (node *)malloc(sizeof(node));
    secondNumber = (node *)malloc(sizeof(node));
    printf("\n Enter the first number(one digit at a time) type -1 to terminate the number:");
    printf("\n Enter the digit:");
    scanf("%d",&firstNumber->data);
    inputNumber(firstNumber);
   
    printf("\n Enter the second number(one digit at a time) type -1 to terminate the number:");
    printf("\n Enter the digit:");
    scanf("%d",&secondNumber->data);
    inputNumber(secondNumber);
   
    display(firstNumber,1);
    display(secondNumber,2);
   
    addNumber(firstNumber,secondNumber);   
    return 0;
    }   
void addNumber(node *p,node *q) {
    int len1=0,len2=0,min,i,once=0;
    while (p->nextDigit !=NULL) {
        len1++;
        p = p->nextDigit;
        }
    p = p->revDigit;   
    while (q->nextDigit !=NULL) {
        len2++;
        q = q->nextDigit;
        }
    q = q->revDigit;
    min = len1 <= len2 ? len1:len2;
    node *sum,*tmp,*sum1;   
    sum = (node *)malloc(sizeof(node));
    sum1 = sum;
    sum->revDigit = NULL;
    for ( i = 1; i <= min; i++) {
        sum->data = (p->data+q->data+once)%10;
        tmp = sum;
        once = (p->data+q->data+once)/10;
        p=p->revDigit;
        q=q->revDigit;
        sum->nextDigit = (node *)malloc(sizeof(node));
        sum = sum->nextDigit;
        sum->revDigit=tmp;
        }
    if ( len1 == len2 && once !=0) {
        sum->data = once;
        sum->revDigit=tmp;
        }   
    if (len1 > len2) {
        int t = len1-len2;
        sum = sum->revDigit;
        for ( i = 1; i<=t; i++) {
            tmp = sum;
            sum->nextDigit = (node *)malloc(sizeof(node));
            sum = sum->nextDigit;
            sum->revDigit=tmp;
            sum->data = (p->data+once)%10;
            once = (p->data+once)/10;
            p = p->revDigit;
            } 
        if ( once !=0) {
            tmp = sum;
            sum->nextDigit = (node *)malloc(sizeof(node));
            sum = sum->nextDigit;
            sum->data = once;
            sum->revDigit=tmp;
            }
               
        }   
    if (len1 < len2) {
        sum = sum->revDigit;
        int t = len2-len1;
        for ( i = 1; i<=t; i++) {
            tmp = sum;
            sum->nextDigit = (node *)malloc(sizeof(node));
            sum = sum->nextDigit;
            sum->revDigit=tmp;
            sum->data = (q->data+once)%10;
            once = (q->data+once)/10;
            q = q->revDigit;
            }
        if ( once !=0) {
            tmp = sum;
            sum->nextDigit = (node *)malloc(sizeof(node));
            sum = sum->nextDigit;
            sum->data = once;
            sum->revDigit=tmp;
            }   
        }   
    sum->nextDigit = NULL;   
    printf("\n Sum of the numbers is:");
    while (sum1->nextDigit !=NULL) {
        //printf("\n%d",sum1->data);
        sum1 = sum1->nextDigit;
        }
    //sum1 = sum1->revDigit;   
    while (sum1 !=NULL) {
        printf("%d",sum1->data);
        sum1 = sum1->revDigit;
        }
    printf("\n");   
    }   
void display(node *p,int tx) {
    if (tx==1)
        printf("\nFirst Number\n");
    else
        printf("\nSecond Number\n");
    while (p->nextDigit !=NULL) {
        printf("%d",p->data);
        p = p->nextDigit;
        }
    p = p->revDigit;   
    /*while (p !=NULL) {
        //printf("%d",p->data);
        p = p->revDigit;
        }*/   
    }   
void inputNumber(node *p) {
    node *q;
    p->revDigit = NULL;
    while (1) {
        q = p;
        p->nextDigit = (node *)malloc(sizeof(node));
        p = p->nextDigit;
        printf("\n Enter the digit:");
        scanf("%d",&p->data);
        p->revDigit = q;
        if (p->data == -1)
            break;
        }
    p->nextDigit = NULL;
    }     

C Program #15

/*Dynamic Implementation of Stack With Basic operations!*/

#include<stdio.h>

#include<malloc.h>

#define TRUE 1

#define FALSE 0

struct stack

                        {

                        int item;

                        struct stack *right;

                        };

typedef struct stack node;

node *push(node *);

node *push1(node *,int);

void display(node *);

int Isempty(node *);

void top2bottomu(node *);

void top2bottom(node *);

void pop(node *);

int pop1(node *);

void duplicate(node *);

void filestack(node *, FILE *fp);

void stack2(node *);

int Isequal(node *,node *);

int length(node*);

int main()

{

int choice;

FILE *fp;

fp=fopen("data.txt","w");

node *root,*data,*root1,*data1,*root2,*data2;

root=(node *)malloc(sizeof(node));

root->right=NULL;

data=root;

root1=(node *)malloc(sizeof(node));

root1->right=NULL;

data1=root1;

root2=(node *)malloc(sizeof(node));

root2->right=NULL;

data2=root2;

            do

            {

                        printf("\n Press 1 to push a element:");

                        printf("\n Press 2 for bottom to top:");

                        printf("\n Press 3 to check for empty:");

                        printf("\n Press 4 to print elements from top to bottom,stack becoming empty:");

                        printf("\n Press 5 to pop:");

                        printf("\n Press 6 to print elements from top to bottom,stack unchanged:");

                        printf("\n Press 7 to duplicate the top element of the stack:");

                        printf("\n Press 8 to read from a file and print in reverse order:");

                        printf("\n Press 9 to push element in second stack:");

                        printf("\n Press 10 to display second stack:");

                        printf("\n Press 11 to check if two stacks are equal:");

                        printf("\n Enter choice:");

                        printf("\n Type 12 to exit:");

                        scanf("%d",&choice);

                        switch(choice)

                                    {

                                                case 1:

                                                data=push(data);

                                                data->right=NULL;

                                                break;

                                                case 2:

                                                display(root);

                                                break;

                                                case 3:

                                                if(Isempty(root))

                                                            printf("\n Stack is empty:\n");

                                                else

                                                            printf("\n Stack is not empty:\n");

                                                break;

                                                case 4:

                                                top2bottom(root);

                                                data=root;

                                                break;

                                                case 5:

                                                pop(root);

                                                data=root;

                                                break;

                                                case 6:

                                                top2bottomu(root);

                                                break;

                                                case 7:

                                                duplicate(root);

                                                break;

                                                case 8:

                                                filestack(root1,fp);

                                                break;

                                                case 9:

                                                data2=push(data2);

                                                data2->right=NULL;

                                                break;

                                                case 10:

                                                display(root2);

                                                break;

                                                case 11:

                                                if(Isequal(root,root2))

                                                            printf("\n Stack are equal:\n");

                                                else

                                                            printf("\n Stack are not equal:\n");

                                                break;

                                                default:

                                                break;

                                    }

                        }

                        while(1<=choice && choice<=11);

            return 0;

 }

int Isequal(node *data1,node *data2)

            {

            int flag=FALSE,i;

            if(Isempty(data1) || Isempty(data2))

                        {

                        if(Isempty(data1) && Isempty(data2))

                                    return (TRUE);

                        else

                                    return (FALSE);

                        }

            else

                        {

                         if(length(data1)!=length(data2))

                         //         {printf("{%d,%d}\n",length(data1),length(data2));

                                    return (FALSE);//}

                         else

                                    {

                                    for(i=0;i<=length(data1);i++)

                                                {

                                                if(data1->item!=data2->item)

                                                            flag=TRUE;

                                                data1=data1->right;

                                                data2=data2->right;

                                                }

                                    if(flag==FALSE)

                                                return (TRUE);

                                    else

                                                return (FALSE);

                                    }

                         }

            }

int length(node *data)

            {

            int k=0;

            while(data->right!=NULL)

                        {

                        k++;

                        data=data->right;

                        }

            return(k-1);

            }

void filestack(node *data, FILE *fp)

            {

            node *p;

            p=data;

            fclose(fp);

            fp=fopen("data.txt","w");

            int n,i,x;

            printf("\n Enter the number of elements to be entered in file:");

            scanf("%d",&n);

            for(i=1;i<=n;i++)

                        {

                        printf("\n Enter the %d# elemet:",i);

                        scanf("%d",&x);

                        fprintf(fp,"%d ",x);

      }

            fclose(fp);

            fp=fopen("data.txt","r");

            printf("\n Elements in the file:");

            for(i=1;i<=n;i++)

                        {

                        fscanf(fp,"%d",&x);

                        printf("%d ",x);

                        data=push1(data,x);

                        data->right=NULL;

                        }

            fclose(fp);

            printf("\n Elements from the file in reverse order:");

            top2bottomu(p);

            printf("\n");

            }

node *push1(node *data,int x)

            {

  //        node *p;

            while(data->right!=NULL)

                        data=data->right;

            data->item=x;

            data->right=(node *)malloc(sizeof(node));

            data=data->right;

            return(data);

            }

void duplicate(node *data)

            {

            node *p,*q;

            q=(node *)malloc(sizeof(node));

            p=data;

            int x;

            while(p->right->right!=NULL)

                        p=p->right;

            x=p->item;

            p->right->item=x;

            p->right->right=q;

            q->right=NULL;

   }

void top2bottom(node *data)

            {

                        while(!Isempty(data))

                                    {

                                    pop(data);

                                    }

            }

void pop(node *data)

            {

            node *p;

            if(Isempty(data))

                        {

                                    printf("\n Stack is empty, cannot be popped:\n");

                        }

            else

                        {

                                    if(data->right->right==NULL)

                                                {

                                                printf("\nElement popped out is %d \n",data->item);

                                                p=data;

                                                free(data);

                                                p->right=NULL;

                                                }

                                    else

                                                {

                                                while(data->right->right->right!=NULL)

                                                            data=data->right;

                                                            p=data->right;

                                                            printf("\nElement popped out is %d \n",p->item);

                                                            free(p);

                                                            data->right->right=NULL;

                                                }

                        }

            }

void top2bottomu(node *data)

            {

            node *q;

            q=data;

            int k=0,i,*a;

            while(data->right!=NULL)

                        {

                        k++;

                        data=data->right;

                        }

            //printf("%d.....\n",k);

            a=(int*)malloc(k*sizeof(int));

            for(i=0;i<k;i++)

                        {

                        *(a+i)=q->item;

                        q=q->right;

                        }

            for(i=k-1;i>=0;i--)

                        printf("%d ",*(a+i));

   free(a);

            printf("\n");

            }

int Isempty(node *data)

            {

                        if(data->right==NULL)

                                    return (TRUE);

                        else

                                    return (FALSE);

            }

node *push(node *data)

            {

  //        node *p;

            while(data->right!=NULL)

                        data=data->right;

            printf("\n Enter the element to be inserted:");

            scanf("%d",&data->item);

            data->right=(node *)malloc(sizeof(node));

            data=data->right;

            return(data);

            }

void display(node *data)

            {

                        if(Isempty(data))

                                    printf("\n Stack is empty, nothing to display:\n");

            else{    while(data->right!=NULL)

                                    {

                                    printf("%d ",data->item);

                                    data=data->right;

                                    }

                         }

            printf("\n");

            }

int pop1(node *data)

            {

            node *p;

            if(Isempty(data))

                        {

                                    printf("\n Stack is empty, cannot be popped:\n");

                        }

            else

                        {

                                    if(data->right->right==NULL)

                                                {

            p=data;

                                                p->right=NULL;

            return(data->item);

                                                }

                                    else

                                                {

                                                while(data->right->right->right!=NULL)

                                                            data=data->right;

                                                            p=data->right;

                                                            data->right->right=NULL;

                                                            return(p->item);

                                                            }

                        }

            }