Quick sort

Quick sorting is an important algorithm as it uses divide and conquer approach and here in this algorithm we divide the array into two arrays where in one array all elements smaller than pivot will be stored and in second all the elements greater than pivot will store. 
After getting two arrays we will again apply the same procedure and in last we will be getting the sorted array 

the idea is this 
and the program is 

#include<stdio.h>
#define first 0
void main()
{
    int A[]={23,6,5,17,54,2,4,9,76,24,84,286};
    int size= sizeof A/sizeof A[0];
    quick_sort(A,first,size-1);
    output(A,size);

}
void quick_sort(int *A,int p,int r)
{
    if(p<r)
    {
        int pivot=A[r];
        int i=p-1,j;
        for(j=p;j<r;j++)
        {
            if(A[j]<pivot)
            {
            i++;
            swap(&A[i],&A[j]);
            }
        }
        A[r]=A[i+1];    /*change the pivot position to its original position where the boundary between                                         two arrays(smaller than pivot and larger than pivot) will exist*/
        A[i+1]=pivot;
        quick_sort(A,p,i); 
                                 /* as the pivot element that we choose is now on i+1 position see above line */
        quick_sort(A,i+2,r);  
                          /*we are not  passing the pivot(i.e. i+1position) as it is already on its right position*/
    }
}

void swap(int *m, int *n)
{
    int temp = *m;
    *m=*n;
    *n=temp;
}

void output(int *A,int size)
{
    int i=0;
    for(i=0;i<size;i++)
    {
        printf("%d\n",A[i]);

    }
}

Bubble Sort

Today we will be discussing about bubble sort . In this sorting the biggest bubble(ie maximum number) will go on the end position after first iteration . 
Then we will move the second largest bubble(ie second largest number) on the second last  position.
and so on . 
So the simple program for bubble sort is 

 #include<stdio.h>
void main()
{
    int A[]={23,76,4,12,76,32,98,54,13,65};
    int size = sizeof A/sizeof A[0];
    bubble_sort(A,size);
    output(A,size);
}

void bubble_sort(int *A,int size)
{
    int i,j;
    for(i=0;i<size-1;i++)
    {
        for(j=0;j<size-i-1;j++)
        {
            if(A[j]>A[j+1])
            {
                swap(&A[j],&A[j+1]); /* swap the number if first number is larger as we are trying to                                                                             move the larger number in end */
            }
        }
    }
}
void swap(int *m, int *n)
{
    int temp = *m;
    *m=*n;
    *n=temp;
}

void output(int *A,int size)
{
    int i=0;
    for(i=0;i<size;i++)
    {
        printf("%d\n",A[i]);

    }
}

Selection sort

Now today i will be discussing about selection sort too . in this sorting we first try to find the maximum element and then we place it in array's first position . 

After this step we find second greatest element and place it in second position of array and so on. 

So the simple program for selection sort is

 #include<stdio.h>

void main()

{

    int array1[]={32,67,8,54,21,43,76,83,12,32},i;

    selection(array1,9);

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

    {

    printf("%d\n",array1[i]);

    }

}

void selection(int *A,int n )

{

    int i,j,temp;

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

    {

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

        {

            if (A[i]>A[j])

                                     /*checking if the element that we are comparing is smaller than our assumption of minimum change it */

            {

                temp = A[j];

                A[j]=A[i];

                A[i]=temp;

            }

        }

    }

}

Insertion sorting

Today we will be talking abut insertion sort . This is a very simple program but an important algorithm for sorting the numbers . The approach is quite similar to sorting of playing cards . when we find a new number we will move that card there and will shift the other cards.
here is the program

       #include<stdio.h>
void main()
{
    int A[]= {12,65,32,87,98,21,43,14,65,76};
    int size= sizeof(A)/ sizeof(A[0]) ;        /*it will give number of elements*/
    insertion_sort(A,size);
    output(A,size);

}
void insertion_sort(int *A,int size)
{
    int i ,j;
    for (i=1;i<size;i++)                   /*as last index=size-1*/
    {
        int key =A[i];
        j=i-1;
        while (A[j]>key&&j>0)      /* loop will go on and on & swaps until A[j] is smaller than key */
        {
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=key;
    }
}

void output(int *A,int size)
{
    int i=0;
    for(i=0;i<size;i++)
    {
        printf("%d\n",A[i]);

    }
}

program explaining merge sort without saving the random number in left and right array

lot of people are finding difficulty in left[i]= 10000 so here's the solution 
well in my previous blog yesterday the approach that i followed was similar to cormen where they initialize the the next  element after filling the let and right sub array as ∞ which means the element should be higher than all the elements present for sorting but that may not be the case .. as you will never know what a person can enter . 
here some people will say that we can enter the largest that is available for that language for example for c it signed 32467 ( for 32 bit compiler ) and it can also vary from system to system so you can  use this approach 
#include<stdio.h>
#include<conio.h>
void main()
{
     int i,array1[]={1,5,7,84,32,76,41,62,79,13};
     merge(array1,0,9);
    for( i=0;i<=9;i++)
    {
          printf("%d\n",array1[i]);
    }
}

void merge(int *A,int p,int n)
{
  if (p==n)
    {
    return;
    }
  else
   {

    int q=p+(n-p)/2;
    printf("now calling merge(A,%d,%d)\n",p,q);
    merge(A,p,q);
    printf(" now calling merge(A,%d,%d)\n",q+1,n);
    merge(A,q+1,n);
    printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
    combine(A,p,q,n);
   }
}
void combine(int *A,int p,int x,int n)
{
    int i = 0;
    int j=0;
    int n1 = p ;
    int n2 = x;
    int left[10];
    int right[10];
    for( i=0;p<=x;i++,p++)
    {
            left[i] = A[p];
            printf("the element added in left now which is %d",left[i]);

    }


    for(i=0;(x+1)<=n;x++,i++)
    {
        right[i] = A[x+1];
        printf("the element added in right now which is  %d",right[i]);

    }
    printf("\n");
    p=n1; /*now p contains the starting value as we modified the value in first loop */
    for(i=0,j=0;(i<n2-n1+1)&&(j<n-n2);p++) /* as (n2-n1+1) would be giving the number of elements in left array but here in left array we are starting from 0 that's why we didn't use equal to sign*/
    {
        if((i!=n2-n1+1)&&(left[i]<right[j]))
        {
            A[p]=left[i];
            printf("the element added in A[%d] which is %d \n",n1,A[p]);
            i++;
        }
        else
        {

            A[p]= right[j];
            printf("the element added from right \n",A[p]);
            j++;
        }
    }
    if(i == n2-n1+1 ) /*means all the elements of the left array are copied but there can be elements in right */
    {
        for(;j<n2-n1;j++)
        {
            A[p]=right[j];
            p++;
        }

    }
    else /*means all the elements of the right  array are copied but there can be elements in left */
    {
        for(;i<n2-n1+1;i++)
        {
            A[p]=left[i];
            p++;
        }
    }
}

when i am combing the arrays the loop will come out if only the i or j  index have reached boundry conditions and now in if else condition i am checking which index has achieved boundary conditions as if it j then i will simply copy all the elements of left array in A that is the final array or if it was i then i am copying all the remaining elements from left array . 

Here i tried to keep the previous program as it is ..with minimal changes ... so that you can understand the idea .. well other approaches are also possible .. 

as once a great mathematician said " there are infinitely many solutions possible for a single  problem " 

so try to program it and find newer approaches by yourself  

merge sort ( a program that will explain the working of whole merge sort )

well today we are going to learn about merge sort i think it is the very first program written in "analysis of algorithm  by coreman "
i am going to tell you the easiest approach. i want you to copy this program in your compiler and let it run... this program will unfold everything.

#include<stdio.h>
#include<conio.h>
void main()
{
     int i,array1[]={1,5,7,84,32,76,41,62,79,13};
     merge(array1,0,9);
    for( i=0;i<=9;i++)
    {
          printf("%d\n",array1[i]);
    }
}

void merge(int *A,int p,int n)
{
  if (p==n)
    {
    return;
    }
  else
   {

    int q=p+(n-p)/2;
    printf("now calling merge(A,%d,%d)\n",p,q);
    merge(A,p,q);
    printf(" now calling merge(A,%d,%d)\n",q+1,n);
    merge(A,q+1,n);
    printf("now calling combine(A,%d,%d,%d)\n",p,q,n);
    combine(A,p,q,n);
   }
}
void combine(int *A,int p,int x,int n)
{
    int i = 0;
    int j=0;
    int n1 = p ;
    int left[10];
    int right[10];
    for( i=0;p<=x;i++,p++)
    {
            left[i] = A[p];
            printf("the element added in left now which is %d",left[i]);

    }
    left[i]=10000;

    for(i=0;(x+1)<=n;x++,i++)
    {
        right[i] = A[x+1];
        printf("the element added in right now which is  %d",right[i]);

    }
    right[i]=50000;
    printf("\n");
    for(i=0,j=0;n1<=n;n1++)
    {
        if(left[i]<right[j])
        {
            A[n1]=left[i];
            printf("the element added from left in A[%d] which is %d \n",n1,A[n1]);
            i++;
        }
        else
        {

            A[n1]= right[j];
            printf("the element added from right in A[%d] which is \n",A[n1]);
            j++;
        }
    }
}

here is the explanation well it is a method to sort numbers by divide and conquer algorithim

the idea is if you have to solve the smaller problems and somehow combine their results to solve the bigger ones

there are lot of techniques also for example dynamic programming and greedy based algo

and this is one among them

here what i am doing .. in order to sort the numbers

i am breaking the problems into smaller parts

as you can see i wrote merge(A,0,9)

i used array1 here

i think

so when i am calling it first it will enter into merge program

*function

not program

and there a smaller version of it would be called ie merge(A,0,2)

in actual i wrote it as merge (a,p,q )

where p is starting point

and q is the point upto which i should

and when it will enter into it it will again divide the array as now there are three elements .. the program would divide into two and one element

and here recursion come into picture

calling the function itself

and then the program would again try to divide the array which has two elements now in to two arrays of one and one

and as i know i don;t have to sort the single element because it is already sorted i will just return it .. so i rote the base case as you can see where i wrote p==n

return this value now the actual part is to combine two sorted array

and here the combining procedure/function is called

question : What is this left [i]=10000 for?

answer : actually i copied the left array in left[] and right one in right[]

and then while comparing it may be the case that all elements of first array will get copied first and then the i index will be one more than the actual one.

so i used a larger number(any large random number you can use but it should be greater than the elements present in both array ) so that while comparing it...that element won't be copied otherwise there will be some garbage value