Insertion sorting

Q. write a c program to implies the insertion sorting method.


Ans.


/* c program for insertion sorting method */
#include<stdio.h>
#include<conio.h>
int main()
{
 int arr[30];
 int i,j,size,tmp;
 printf("\n\t------ Insertion sorting method ---------\n\n");
 printf("Enter total no. of elements : ");
 scanf("%d", &size);
 for(i=0; i<size; i++)
 {
   printf("Enter %d element : ",i+1);
   scanf("%d", &arr[i]);

 }
 for(i=0; i<size; i++)
 {
  for(j=i-1; j>=0; j--)
  {
   if(arr[j]>arr[j+1])
   {
     tmp=arr[j];
     arr[j]=arr[j+1];
     arr[j+1]=tmp;
   }
   else
     break;
  }
 }
 printf("\n\t------- Insertion sorted elements -------\n\n");
 for(i=0; i<size; i++)
    printf(" %d",arr[i]);
 getch();
 return 0;
}


/************** OUTPUT ***************/

Insertion sorting method output

Related programs:

1. Heap sorting method and algorithm
2. Heap sorting
3. Bubble sorting
4. Selection Sorting
5. Insertion sorting using function
6. Shell sorting
7. Quick sorting
8. Merge sorting
9. Radix sorting
10. Liner sorting

Quick sorting

Quick sort is a divide and conquer algorithm. Its divided large list in mainly three parts:

1.     Elements less than pivot element.

2.     Pivot element.

3.     Elements greater than pivot element.

Where pivot as middle element of large list. Let’s understand through example:

List : 3 7 8 5 2 1 9 5 4

In above list assume 4 is pivot element so rewrite list as:

 3 1 2 4 5 8 9 5 7

Here, I want to say that we set the pivot element(4) which has in left side elements are less than and right hand side elements are greater than. Now you think, how’s arrange the less than and greater than elements? Be patient, you get answer soon.

Now let’s start understand the concept of quick sort. The steps are:

1.    Pick a pivot element.

2.    Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

3.    Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted

Example of quick sort process:

Steps of quick sorting

/*c program for quick sorting*/

#include<stdio.h>

#include<conio.h>

void qsort(int arr[20], int fst, int last);

int main()

{

 int arr[30];

 int i,size;

 printf("Enter total no. of the elements : ");

 scanf("%d",&size);

 printf("Enter total %d elements : \n",size);

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

    scanf("%d",&arr[i]);

 qsort(arr,0,size-1);

 printf("Quick sorted elements are as  : \n");

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

    printf("%d\t",arr[i]);
 getch();

 return 0;

}

void qsort(int arr[20], int fst, int last)

{

 int i,j,pivot,tmp;

 if(fst<last)

 {

   pivot=fst;

   i=fst;

   j=last;

   while(i<j)

   {

     while(arr[i]<=arr[pivot] && i<last)

        i++;

     while(arr[j]>arr[pivot])

        j--;

     if(i<j)

     {

        tmp=arr[i];

        arr[i]=arr[j];

        arr[j]=tmp; 

     }

   }

   tmp=arr[pivot];

   arr[pivot]=arr[j];

   arr[j]=tmp;

   qsort(arr,fst,j-1);

   qsort(arr,j+1,last);

 }

}

/********* OUTPUT **********/

Screen-shot of quick sorting C program

Related programs:

1. Heap sorting method and algorithm
2. Heap sorting
3. Bubble sorting
4. Selection Sorting
5. Insertion sorting
6. Insertion sorting using function
7. Shell sorting
8. Merge sorting
9. Radix sorting
10. Liner sorting

Shell sorting

Q. Write a c program that sort 10 numbers using shell sorting method.


Ans.


Shell sorting was first introduced by Donald Shell.
It generalized as exchanging sort, such as bubble or insertion sorting, by allowing the comparison and exchange of elements that lie far apart. The running time of Shell sort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

Steps for solution of shell sorting:

step.1:
Set up a inc number. inc number is set according to given elements in the list.

step.2:
mark each elements which is comes in inc element.
For example, if list contains 10 elements then and we assume inc is 3 then, marking of elements such as next marking element, add last element +3 to get next element and so on. Then marking element would be 1st element, 4th element(add 3), 7th element(add 3), 10th element.

89  46  99  12  33  14  69  41  33  28

1    2    3    4    5    6   7    8   9   10 [index number]

step.3:
sort marking elements such as smallest to greater is set as left to right and not change remain element.
For example, we apply this step in above example:

12  46  99  28  33  14  69  41  33  89

step.4:
reduce inc number to one i.e. if inc number is earlier is 3 then now it would be 3-1 = 2.

step.5:
Repeat step 2,3 and 4 till all the elements not sorted.

Let's understand shell sorting using example:

35 12 14 9 15 45 32 95 40 5
//assume inc=3
//Now marking 1st element, 1+3=4th element, //4+3=7th element, 7+3=10th element

35  12  14  9  15  45  32 95  40  5
//step-3 i.e. sorting of marked elements

5  12  14  9  15  45  32  95  40  35
//now inc=3-1=2
//new marking is 1st element, 1+2=3th element, //3+2=5 element, 5+2=7th element, 7+2=9th //element

5  12  14  9  15  45  32  95  40  35
//now sorting of marked elements

5  12  14  9  15  45  32  95  40  35
//Now inc=2-1=1
//Now every elements all marked because inc=1

5   12  14  9  15  45  32  95  40 35
//sorting of marked elements

5  9  12  14  15  32  35  40  45  95

/*c program for sorting array using shell sorting method*/
#include<stdio.h>
#include<conio.h>
int main()
{
 int arr[30];
 int i,j,k,tmp,num;
 printf("Enter total no. of elements : ");
 scanf("%d", &num);
 for(k=0; k<num; k++)
 {
   printf("\nEnter %d number : ",k+1);
   scanf("%d",&arr[k]);
 }
 for(i=num/2; i>0; i=i/2)
 {
   for(j=i; j<num; j++)
   {
     for(k=j-i; k>=0; k=k-i)
     {
        if(arr[k+i]>=arr[k])
            break;
        else
        {
            tmp=arr[k];
            arr[k]=arr[k+i];
            arr[k+i]=tmp;
        }
     }
   }
 }
 printf("\t**** Shell Sorting ****\n");
 for(k=0; k<num; k++)
     printf("%d\t",arr[k]);
 getch();
 return 0;
}


/*****************OUTPUT*****************
Enter total no. of elements : 7
Enter 1 number : 8
Enter 2 number : 3
Enter 3 number : 7
Enter 4 number : 9
Enter 5 number : 1
Enter 6 number : 24
Enter 7 number : 2
     **** Shell Sorting ****
1  2  3  7  8  9  24 
*****************************************/



Related programs:

1. Heap sorting method and algorithm
2. Heap sorting
3. Bubble sorting
4. Selection Sorting
5. Insertion sorting
6. Insertion sorting using function
7. Quick sorting
8. Merge sorting
9. Radix sorting
10. Liner sorting

Tricky c questions and answers

Tricky c
programs question for interview and answers with explanation. These questions
are for experienced persons.





C advanced interview questions and
answers



(1) What will be output if you will compile and execute the following c code?




struct marks{

  int p:3;

  int c:3;

  int m:2;

};

void main(){

  struct marks s={2,-6,5};

  printf("%d %d %d",s.p,s.c,s.m);

C programming online test

C
programming online test questions answers and explanation for freshers