Category Archives: Algorithm

Bubble Sort

Posted on June 25, 2017 | Leave a comment

This video is good to help:

I have also taken help from DS Made Easy by Karumanchi book to find the algo pesudocode.

Pseudocode:

void bubbleSort(int *arr,int n)
{
    int pass,j;
    for(pass=n-1; pass>=0;  pass--)
    {
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
            }
        }
    }
}

void bubbleSort(int *arr,int n)

{

int pass,j;

for(pass=n-1; pass>=0; pass--)

{

for(j=0; j<=pass-1; j++)

{

if(arr[j]>arr[j+1])

{

swaps(&arr[j],&arr[j+1]);

}

Implementation:

#include<bits/stdc++.h>
using namespace std;
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}
void bubbleSort(int *arr,int n)
{
    int pass,j;
    for(pass=n-1; pass>=0;  pass--)
    {
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
            }
        }
    }
}

void printArray(int *arr,int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
}

int main()
{
    int A[]= {2,7,19,1,5,9};
    int n=sizeof(A)/sizeof(A[0]);
    bubbleSort(A,n);
    printArray(A,n);
}

#include<bits/stdc++.h>

using namespace std;

int swaps(int *p,int *q)

{

int temp=*q;

*q=*p;

*p=temp;

}

void bubbleSort(int *arr,int n)

{

int pass,j;

for(pass=n-1; pass>=0; pass--)

{

for(j=0; j<=pass-1; j++)

{

if(arr[j]>arr[j+1])

{

swaps(&arr[j],&arr[j+1]);

}

void printArray(int *arr,int n)

{

for(int i=0; i<n; i++)

{

cout<<arr[i]<<" ";

}

int main()

{

int A[]= {2,7,19,1,5,9};

int n=sizeof(A)/sizeof(A[0]);

bubbleSort(A,n);

printArray(A,n);

}

I need to improve this algorithm as it is not passing all the sizes of array so there will be some vacant position in array which increases the complexity in the running time so we need to out of the loop when it has nothing to swap, so our improvised algorithm will be:

Pseudocode:

void bubbleSort(int *arr,int n)
{
    int pass,j,flag=0;
    for(pass=n-1; pass>=0;  pass--)
    {
        flag=0;
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
                flag=1;
            }
        }
        if(flag==0)
            break;
    }
}

void bubbleSort(int *arr,int n)

{

int pass,j,flag=0;

for(pass=n-1; pass>=0; pass--)

{

flag=0;

for(j=0; j<=pass-1; j++)

{

if(arr[j]>arr[j+1])

{

swaps(&arr[j],&arr[j+1]);

flag=1;

}

if(flag==0)

break;

}

Implementation:

#include<bits/stdc++.h>
using namespace std;
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}
void bubbleSort(int *arr,int n)
{
    int pass,j,flag=0;
    for(pass=n-1; pass>=0;  pass--)
    {
        flag=0;
        for(j=0; j<=pass-1; j++)
        {
            if(arr[j]>arr[j+1])
            {
                swaps(&arr[j],&arr[j+1]);
                flag=1;
            }
        }
        if(flag==0)
            break;
    }
}

void printArray(int *arr,int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
}

int main()
{
    int A[]= {2,7,19,1,5,9};
    int n=sizeof(A)/sizeof(A[0]);
    bubbleSort(A,n);
    printArray(A,n);
}

#include<bits/stdc++.h>

using namespace std;

int swaps(int *p,int *q)

{

int temp=*q;

*q=*p;

*p=temp;

}

void bubbleSort(int *arr,int n)

{

int pass,j,flag=0;

for(pass=n-1; pass>=0; pass--)

{

flag=0;

for(j=0; j<=pass-1; j++)

{

if(arr[j]>arr[j+1])

{

swaps(&arr[j],&arr[j+1]);

flag=1;

}

if(flag==0)

break;

}

void printArray(int *arr,int n)

{

for(int i=0; i<n; i++)

{

cout<<arr[i]<<" ";

}

int main()

{

int A[]= {2,7,19,1,5,9};

int n=sizeof(A)/sizeof(A[0]);

bubbleSort(A,n);

printArray(A,n);

}

This below video can help for better optimization that implemented in the above code:

Time Complexity in Running Time:

Worst Case: O(n^2)
BEst Case without improve: O(n^2)
Best Case(Improvised): O(n)
Average Case: O(n^2)
Space Complexity: O(1)
Simulation Tried to be drawn by me:

Leave a comment

Posted in Algorithm, Bubble Sort

Selection Sort

Posted on June 25, 2017 | Leave a comment

PSeudoCode:

selectionSort(A,n)
{
    for(i=0 to n-1)
    {
        min=i;
        for(j=i+1 to n){
            if(arr[j]<arr[min]){
                min=j;
            }
        }
        if(min!=i)
        {
            swap(arr[min],arr[i]);
        }
    }

}

selectionSort(A,n)

{

for(i=0 to n-1)

{

min=i;

for(j=i+1 to n){

if(arr[j]<arr[min]){

min=j;

}

if(min!=i)

{

swap(arr[min],arr[i]);

}

Implemented Code:

#include<bits/stdc++.h>
using namespace std;
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}

void selectionSort(int *arr,int n)
{
    int i,j,mins;
    for(i=0; i<n-1; i++)
    {
        mins=i;
        for(j=i+1; j<n; j++)
        {
            if(arr[j]<arr[mins])
            {
                mins=j;
            }
        }
        if(mins!=i){
        swaps(&arr[mins],&arr[i]);
        }
    }
}
printArray(int *arr,int n)
{

    for(int i=0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }

}

int main()
{
    //int A[]= {4,42,23,16,8,15};
    int A[]= {2,7,4,1,5,3};
    int sizes=sizeof(A)/sizeof(A[0]);
    //selectionSort(A,6);
    selectionSort(A,sizes);
    printArray(A,sizes);

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int swaps(int *p,int *q)

{

int temp=*q;

*q=*p;

*p=temp;

}

void selectionSort(int *arr,int n)

{

int i,j,mins;

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

{

mins=i;

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

{

if(arr[j]<arr[mins])

{

mins=j;

}

if(mins!=i){

swaps(&arr[mins],&arr[i]);

}

printArray(int *arr,int n)

{

for(int i=0; i<n; i++)

{

cout<<arr[i]<<" ";

}

int main()

{

//int A[]= {4,42,23,16,8,15};

int A[]= {2,7,4,1,5,3};

int sizes=sizeof(A)/sizeof(A[0]);

//selectionSort(A,6);

selectionSort(A,sizes);

printArray(A,sizes);

return 0;

}

output:

//4 8 15 16 23 42
1 2 3 4 5 7

1 2	//4 8 15 16 23 42 1 2 3 4 5 7

Leave a comment

Posted in Selection Sort, Sorting

QuickSort

Posted on June 23, 2017 | Leave a comment

Youtube Video:

Analaysis though it seems little bit tough to me:

HackerRank video:

MIT video:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-4-quicksort-randomized-algorithms/

Pseudo Code from upper Youtube vid:

QuickSort(A, start, end)
{
if(start<end)
pIndex=Partition(A,start,end);
Quicksort(A,start,index-1);
Quicksort(A,pIndex+1,end);
}

Partition(A,start,end)
{
pivot=A[end];
pIndex=start;
for i=start to end-1
{
if(A[i]<=pivot)
{
swap(A[i],A[pIndex])
pIndex=pIndex+1
}
}
swap(A[pIndex],A[end])
return pIndex
}

QuickSort(A, start, end)

{

if(start<end)

pIndex=Partition(A,start,end);

Quicksort(A,start,index-1);

Quicksort(A,pIndex+1,end);

}

Partition(A,start,end)

{

pivot=A[end];

pIndex=start;

for i=start to end-1

{

if(A[i]<=pivot)

{

swap(A[i],A[pIndex])

pIndex=pIndex+1

}

swap(A[pIndex],A[end])

return pIndex

}

Implementation:

#include<iostream>
using namespace std;
int Partition(int *A,int start,int ends){
    int pivot=A[ends];
    int pIndex=start;
    for(int i=start; i<ends; i++){
        if(A[i]<=pivot)
        {
            //swap(A[i],A[pIndex]);
            int z=A[i];
            A[i]=A[pIndex];
            A[pIndex]=z;
            pIndex=pIndex+1;
        }
    }
    //swap(A[pIndex],A[ends]);
    int k=A[pIndex];
    A[pIndex]=A[ends];
    A[ends]=k;
    return pIndex;
}

void Quicksort(int *A,int start,int ends)
{
    if(start<ends){
       int pIndex=Partition(A,start,ends);
        Quicksort(A,start,pIndex-1);
        Quicksort(A,pIndex+1,ends);
    }
}

int main()
{
int A[]={3,4,1,4,0,9,6,5};
Quicksort(A,0,7);
for(int i=0;i<8;i++)
{
    cout<<A[i]<<" ";
}
return 0;
}

#include<iostream>

using namespace std;

int Partition(int *A,int start,int ends){

int pivot=A[ends];

int pIndex=start;

for(int i=start; i<ends; i++){

if(A[i]<=pivot)

{

//swap(A[i],A[pIndex]);

int z=A[i];

A[i]=A[pIndex];

A[pIndex]=z;

pIndex=pIndex+1;

}

//swap(A[pIndex],A[ends]);

int k=A[pIndex];

A[pIndex]=A[ends];

A[ends]=k;

return pIndex;

}

void Quicksort(int *A,int start,int ends)

{

if(start<ends){

int pIndex=Partition(A,start,ends);

Quicksort(A,start,pIndex-1);

Quicksort(A,pIndex+1,ends);

}

int main()

{

int A[]={3,4,1,4,0,9,6,5};

Quicksort(A,0,7);

for(int i=0;i<8;i++)

{

cout<<A[i]<<" ";

}

return 0;

}

Slightly edited in *A to A[]:

#include<iostream>
using namespace std;
int Partition(int A[],int start,int ends){
    int pivot=A[ends];
    int pIndex=start;
    for(int i=start; i<ends; i++){
        if(A[i]<=pivot)
        {
            //swap(A[i],A[pIndex]);
            int z=A[i];
            A[i]=A[pIndex];
            A[pIndex]=z;
            pIndex=pIndex+1;
        }
    }
    //swap(A[pIndex],A[ends]);
    int k=A[pIndex];
    A[pIndex]=A[ends];
    A[ends]=k;
    return pIndex;
}

void Quicksort(int A[],int start,int ends)
{
    if(start<ends){
       int pIndex=Partition(A,start,ends);
        Quicksort(A,start,pIndex-1);
        Quicksort(A,pIndex+1,ends);
    }
}

int main()
{
int A[]={3,4,1,4,0,9,6,5};
Quicksort(A,0,7);
for(int i=0;i<8;i++)
{
    cout<<A[i]<<" ";
}
return 0;
}

#include<iostream>

using namespace std;

int Partition(int A[],int start,int ends){

int pivot=A[ends];

int pIndex=start;

for(int i=start; i<ends; i++){

if(A[i]<=pivot)

{

//swap(A[i],A[pIndex]);

int z=A[i];

A[i]=A[pIndex];

A[pIndex]=z;

pIndex=pIndex+1;

}

//swap(A[pIndex],A[ends]);

int k=A[pIndex];

A[pIndex]=A[ends];

A[ends]=k;

return pIndex;

}

void Quicksort(int A[],int start,int ends)

{

if(start<ends){

int pIndex=Partition(A,start,ends);

Quicksort(A,start,pIndex-1);

Quicksort(A,pIndex+1,ends);

}

int main()

{

int A[]={3,4,1,4,0,9,6,5};

Quicksort(A,0,7);

for(int i=0;i<8;i++)

{

cout<<A[i]<<" ";

}

return 0;

}

Some change with before and after show:

#include<iostream>
using namespace std;
int Partition(int A[],int start,int ends){
    int pivot=A[ends];
    int pIndex=start;
    for(int i=start; i<ends; i++){
        if(A[i]<=pivot)
        {
            //swap(A[i],A[pIndex]);
            int z=A[i];
            A[i]=A[pIndex];
            A[pIndex]=z;
            pIndex=pIndex+1;
        }
    }
    //swap(A[pIndex],A[ends]);
    int k=A[pIndex];
    A[pIndex]=A[ends];
    A[ends]=k;
    return pIndex;
}

void Quicksort(int A[],int start,int ends)
{
    if(start<ends){
       int pIndex=Partition(A,start,ends);
        Quicksort(A,start,pIndex-1);
        Quicksort(A,pIndex+1,ends);
    }
}

int main()
{
int A[]={3,4,1,4,0,9,6,5};
int sizes=sizeof(A)/sizeof(A[0]);
    cout<<"Before Sorting: ";
    for(int i=0; i<sizes; i++)
    {
        cout<<A[i]<<" ";
    }
Quicksort(A,0,7);
    cout<<endl;
    cout<<"After Sorting: ";
for(int i=0;i<8;i++)
{
    cout<<A[i]<<" ";
}
return 0;
}

#include<iostream>

using namespace std;

int Partition(int A[],int start,int ends){

int pivot=A[ends];

int pIndex=start;

for(int i=start; i<ends; i++){

if(A[i]<=pivot)

{

//swap(A[i],A[pIndex]);

int z=A[i];

A[i]=A[pIndex];

A[pIndex]=z;

pIndex=pIndex+1;

}

//swap(A[pIndex],A[ends]);

int k=A[pIndex];

A[pIndex]=A[ends];

A[ends]=k;

return pIndex;

}

void Quicksort(int A[],int start,int ends)

{

if(start<ends){

int pIndex=Partition(A,start,ends);

Quicksort(A,start,pIndex-1);

Quicksort(A,pIndex+1,ends);

}

int main()

{

int A[]={3,4,1,4,0,9,6,5};

int sizes=sizeof(A)/sizeof(A[0]);

cout<<"Before Sorting: ";

for(int i=0; i<sizes; i++)

{

cout<<A[i]<<" ";

}

Quicksort(A,0,7);

cout<<endl;

cout<<"After Sorting: ";

for(int i=0;i<8;i++)

{

cout<<A[i]<<" ";

}

return 0;

}

Complete Quicksort Implementation and taking user input:

#include<iostream>
using namespace std;
int Partition(int A[],int start,int ends)
{
    int pivot=A[ends];
    int pIndex=start;
    for(int i=start; i<ends; i++)
    {
        if(A[i]<=pivot)
        {
            //swap(A[i],A[pIndex]);
            int z=A[i];
            A[i]=A[pIndex];
            A[pIndex]=z;
            pIndex=pIndex+1;
        }
    }
    //swap(A[pIndex],A[ends]);
    int k=A[pIndex];
    A[pIndex]=A[ends];
    A[ends]=k;
    return pIndex;
}

void Quicksort(int A[],int start,int ends)
{
    if(start<ends)
    {
        int pIndex=Partition(A,start,ends);
        Quicksort(A,start,pIndex-1);
        Quicksort(A,pIndex+1,ends);
    }
}

int main()
{
    int sizes;
    int A[1000];
    cout<<"How many value will you add ? ";
    cin>>sizes;
    for(int k=0; k<=sizes-1; k++)
    {
        cin>>A[k];
    }
//int sizes=sizeof(A)/sizeof(A[0]);
    cout<<"Before Sorting: ";
    for(int i=0; i<=sizes-1; i++)
    {
        cout<<A[i]<<" ";
    }
    Quicksort(A,0,sizes-1);
    cout<<endl;

    cout<<"After Sorting: ";
    for(int i=0; i<=sizes-1; i++)
    {
        cout<<A[i]<<" ";
    }
    return 0;
}

#include<iostream>

using namespace std;

int Partition(int A[],int start,int ends)

{

int pivot=A[ends];

int pIndex=start;

for(int i=start; i<ends; i++)

{

if(A[i]<=pivot)

{

//swap(A[i],A[pIndex]);

int z=A[i];

A[i]=A[pIndex];

A[pIndex]=z;

pIndex=pIndex+1;

}

//swap(A[pIndex],A[ends]);

int k=A[pIndex];

A[pIndex]=A[ends];

A[ends]=k;

return pIndex;

}

void Quicksort(int A[],int start,int ends)

{

if(start<ends)

{

int pIndex=Partition(A,start,ends);

Quicksort(A,start,pIndex-1);

Quicksort(A,pIndex+1,ends);

}

int main()

{

int sizes;

int A[1000];

cout<<"How many value will you add ? ";

cin>>sizes;

for(int k=0; k<=sizes-1; k++)

{

cin>>A[k];

}

//int sizes=sizeof(A)/sizeof(A[0]);

cout<<"Before Sorting: ";

for(int i=0; i<=sizes-1; i++)

{

cout<<A[i]<<" ";

}

Quicksort(A,0,sizes-1);

cout<<endl;

cout<<"After Sorting: ";

for(int i=0; i<=sizes-1; i++)

{

cout<<A[i]<<" ";

}

return 0;

}

Output from the above code:

Geeks for geeks:
http://quiz.geeksforgeeks.org/quick-sort/
http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

From geeks for geeks but may be there might be some problems there

#include<iostream>
using namespace std;
//*arr eitype likha mane arrayta sudhu value/content ta send korbe ekhane pointer diye value tene antese
void swaps(int *a,int *b){
int z=*a;
*b=*a;
*a=z;
}

int partitions(int arr[],int low,int high){
int    pivot=arr[high];
int    i=(low-1);
    for(int j=low;j<=high-1;j++){
        if(arr[j]<=pivot)
        {
            i++;
            swaps(&arr[i],&arr[j]);
        }
    }
    swaps(&arr[i+1],&arr[high]);
    return(i+1);
}

void quicksort(int arr[],int low,int high){
if(low<high){
int    pi=partitions(arr,low,high);
    quicksort(arr,low,pi-1);
    quicksort(arr,pi+1,high);
}
}
void printArray(int arr[],int n){
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
}

int main()
{
//int arr[]={10,7,8,9,1,5};
//int sizes=sizeof(arr)/sizeof(arr[0]);
//cout<<"Unsorted array: ";
//for(int i=0;i<sizes;i++){
//cout<<arr[i]<<" ";
//}
//cout<<endl;
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr, 0, n-1);
    cout<<"Sorted array: ";
    printArray(arr, n);
    return 0;
}

#include<iostream>

using namespace std;

//*arr eitype likha mane arrayta sudhu value/content ta send korbe ekhane pointer diye value tene antese

void swaps(int *a,int *b){

int z=*a;

*b=*a;

*a=z;

}

int partitions(int arr[],int low,int high){

int pivot=arr[high];

int i=(low-1);

for(int j=low;j<=high-1;j++){

if(arr[j]<=pivot)

{

i++;

swaps(&arr[i],&arr[j]);

}

swaps(&arr[i+1],&arr[high]);

return(i+1);

}

void quicksort(int arr[],int low,int high){

if(low<high){

int pi=partitions(arr,low,high);

quicksort(arr,low,pi-1);

quicksort(arr,pi+1,high);

}

void printArray(int arr[],int n){

for(int i=0;i<n;i++){

cout<<arr[i]<<" ";

}

int main()

{

//int arr[]={10,7,8,9,1,5};

//int sizes=sizeof(arr)/sizeof(arr[0]);

//cout<<"Unsorted array: ";

//for(int i=0;i<sizes;i++){

//cout<<arr[i]<<" ";

//}

//cout<<endl;

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr)/sizeof(arr[0]);

quicksort(arr, 0, n-1);

cout<<"Sorted array: ";

printArray(arr, n);

return 0;

}

Another good one for understanding(I think it’s the best one):

Pseudocode available in the above video:

implemented code:

#include<bits/stdc++.h>
using namespace std;
int Partition(int A[],int p,int r)
{
    int x=A[r];
    int i=p-1;
    for(int j=p; j<=r-1; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            //swap(A[i],A[j]);
            //swapping
            int z=A[j];
            A[j]=A[i];
            A[i]=z;
        }
    }
    //swap(A[i+1],A[r]);
    //swapping
    int m=A[r];
    A[r]=A[i+1];
    A[i+1]=m;
    return (i+1); //sending the pivot value to the actual caller function QuickSort
}
int QuickSort(int A[],int p,int r)
{
    if(p<r)
    {
        int q=Partition(A,p,r);
        QuickSort(A,p,q-1);
        QuickSort(A,q+1,r);
    }
}
int main()
{
    //int A[]= {2,1,3,4,10,5,8};
    int A[]={10,5,8,2,4,3,1};
    QuickSort(A,0,6);
    for(int i=0; i<7; i++)
    {
        cout<<A[i]<<" ";
    }


    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int Partition(int A[],int p,int r)

{

int x=A[r];

int i=p-1;

for(int j=p; j<=r-1; j++)

{

if(A[j]<=x)

{

i=i+1;

//swap(A[i],A[j]);

//swapping

int z=A[j];

A[j]=A[i];

A[i]=z;

}

//swap(A[i+1],A[r]);

//swapping

int m=A[r];

A[r]=A[i+1];

A[i+1]=m;

return (i+1); //sending the pivot value to the actual caller function QuickSort

}

int QuickSort(int A[],int p,int r)

{

if(p<r)

{

int q=Partition(A,p,r);

QuickSort(A,p,q-1);

QuickSort(A,q+1,r);

}

int main()

{

//int A[]= {2,1,3,4,10,5,8};

int A[]={10,5,8,2,4,3,1};

QuickSort(A,0,6);

for(int i=0; i<7; i++)

{

cout<<A[i]<<" ";

}

return 0;

}

#include<bits/stdc++.h>
using namespace std;
void swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}
int Partition(int A[],int p,int r)
{
    int x=A[r];
    int i=p-1;
    for(int j=p; j<=r-1; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            //swap(A[i],A[j]);
            //swapping
            swaps(&A[i],&A[j]);
//            int z=A[j];
//            A[j]=A[i];
//            A[i]=z;
        }
    }
    //swap(A[i+1],A[r]);
    //swapping
//    int m=A[r];
//    A[r]=A[i+1];
//    A[i+1]=m;
    swaps(&A[i+1],&A[r]);
    return (i+1); //sending the pivot value to the actual caller function QuickSort
}
int QuickSort(int A[],int p,int r)
{
    if(p<r)
    {
        int q=Partition(A,p,r);
        QuickSort(A,p,q-1);
        QuickSort(A,q+1,r);
    }
}
int main()
{
    //int A[]= {2,1,3,4,10,5,8};
    int A[]={10,5,8,2,4,3,1};
    QuickSort(A,0,6);
    for(int i=0; i<7; i++)
    {
        cout<<A[i]<<" ";
    }


    return 0;
}

#include<bits/stdc++.h>

using namespace std;

void swaps(int *p,int *q)

{

int temp=*q;

*q=*p;

*p=temp;

}

int Partition(int A[],int p,int r)

{

int x=A[r];

int i=p-1;

for(int j=p; j<=r-1; j++)

{

if(A[j]<=x)

{

i=i+1;

//swap(A[i],A[j]);

//swapping

swaps(&A[i],&A[j]);

// int z=A[j];

// A[j]=A[i];

// A[i]=z;

}

//swap(A[i+1],A[r]);

//swapping

// int m=A[r];

// A[r]=A[i+1];

// A[i+1]=m;

swaps(&A[i+1],&A[r]);

return (i+1); //sending the pivot value to the actual caller function QuickSort

}

int QuickSort(int A[],int p,int r)

{

if(p<r)

{

int q=Partition(A,p,r);

QuickSort(A,p,q-1);

QuickSort(A,q+1,r);

}

int main()

{

//int A[]= {2,1,3,4,10,5,8};

int A[]={10,5,8,2,4,3,1};

QuickSort(A,0,6);

for(int i=0; i<7; i++)

{

cout<<A[i]<<" ";

}

return 0;

}

Quick Sorting in Process

Time and Space complexity: Best Case : omega(nlogn)
Worst case: O(n^2)

See this video to clear up the skills:

ideone example: http://ideone.com/oWbONR
Others Code:
http://www.cc.gatech.edu/classes/cs3158_98_fall/quicksort.html
Recursive:
http://www.algolist.net/Algorithms/Sorting/Quicksort
CLRS:
http://www.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/5-quicksort/quicksort.pdf

Google Search Terms:
https://www.google.com/webhp?sourceid=chrome-instant&rlz=1C1PRFC_enBD706BD706&ion=1&espv=2&ie=UTF-8#q=quick+sort+pseudocode&*

Leave a comment

Posted in A ll Codes, Algorithm, Quicksort

Tagged QuickSort

Stevie Hackerearth

Posted on June 9, 2017 | Leave a comment

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define prl(x) printf("%lld\n",x)
#define clr(x) memset(x,0,sizeof(x))
const int N=2e5+55; //max range 10^9

int n,a[N],b[N];
map<int,int> mpp; //<key value, mapped value>
//vector<int> A(n), B(n);
//cin>>n;
int main()
{
    sc(n);
    for(int i=1; i<=n; i++)
    {
        sc(a[i]);
    }
    for(int i=1; i<=n; i++)
    {
        sc(b[i]);
    }
    for(int i=1; i<=n; i++)
    {
        mpp[a[i]]=max(b[i],mpp[a[i]]);
    }
    for(int i=1; i<=n; i++)
    {
        cout<<mpp[a[i]]<<" ";
    }

}

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define sc(x) scanf("%d",&x)

#define scl(x) scanf("%lld",&x)

#define pr(x) printf("%d\n",x)

#define prl(x) printf("%lld\n",x)

#define clr(x) memset(x,0,sizeof(x))

const int N=2e5+55; //max range 10^9

int n,a[N],b[N];

map<int,int> mpp; //<key value, mapped value>

//vector<int> A(n), B(n);

//cin>>n;

int main()

{

sc(n);

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

{

sc(a[i]);

}

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

{

sc(b[i]);

}

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

{

mpp[a[i]]=max(b[i],mpp[a[i]]);

}

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

{

cout<<mpp[a[i]]<<" ";

}

Leave a comment

Posted in A ll Codes, Algorithm, HackerEarth, Pore Abar Bujhbo

Tagged map

Basics of Implementation – Hackerearth

Posted on June 7, 2017 | Leave a comment

Vowel count in a string:
code:

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int a=0,e=0,i=0,o=0,u=0;
    string s;
    cin>>s;
    int len=s.length();
    for(int j=0;j<len;j++)
    {
        if(s[j]=='a')
        {
            a++;
        }
        else if(s[j]=='e')
        {
            e++;
        }
        else if(s[j]=='i')
        {
            i++;
        }
        else if(s[j]=='o')
        {
            o++;
        }
        else if(s[j]=='u')
        {
            u++;
        }
    }

    cout<<"a "<<a<<endl;
    cout<<"e "<<e<<endl;
    cout<<"i "<<i<<endl;
    cout<<"o "<<o<<endl;
    cout<<"u "<<u<<endl;

}

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

int a=0,e=0,i=0,o=0,u=0;

string s;

cin>>s;

int len=s.length();

for(int j=0;j<len;j++)

{

if(s[j]=='a')

{

a++;

}

else if(s[j]=='e')

{

e++;

}

else if(s[j]=='i')

{

i++;

}

else if(s[j]=='o')

{

o++;

}

else if(s[j]=='u')

{

u++;

}

cout<<"a "<<a<<endl;

cout<<"e "<<e<<endl;

cout<<"i "<<i<<endl;

cout<<"o "<<o<<endl;

cout<<"u "<<u<<endl;

}

Count Digit:

#include<iostream>
using namespace std;
int main()
{
    int zero=0,one=0,two=0,three=0,four=0,five=0,six=0,seven=0,eight=0,nine=0;
    string s;
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++){
        if(s[i]=='0'){
            zero++;
        }
        else if(s[i]=='1'){
            one++;
        }
        else if(s[i]=='2'){
            two++;
        }
        else if(s[i]=='3')
        {
            three++;
        }
        else if(s[i]=='4'){
            four++;
        }
        else if(s[i]=='5')
        {
            five++;
        }
        else if(s[i]=='6'){
            six++;
        }
        else if(s[i]=='7'){
            seven++;
        }
        else if(s[i]=='8'){
            eight++;
        }
        else if(s[i]=='9')
        {
            nine++;
        }
    }
    cout<<"0 "<<zero<<endl;
    cout<<"1 "<<one<<endl;
    cout<<"2 "<<two<<endl;
    cout<<"3 "<<three<<endl;
    cout<<"4 "<<four<<endl;
    cout<<"5 "<<five<<endl;
    cout<<"6 "<<six<<endl;
    cout<<"7 "<<seven<<endl;
    cout<<"8 "<<eight<<endl;
    cout<<"9 "<<nine<<endl;

    return 0;
}

#include<iostream>

using namespace std;

int main()

{

int zero=0,one=0,two=0,three=0,four=0,five=0,six=0,seven=0,eight=0,nine=0;

string s;

cin>>s;

int len=s.length();

for(int i=0;i<len;i++){

if(s[i]=='0'){

zero++;

}

else if(s[i]=='1'){

one++;

}

else if(s[i]=='2'){

two++;

}

else if(s[i]=='3')

{

three++;

}

else if(s[i]=='4'){

four++;

}

else if(s[i]=='5')

{

five++;

}

else if(s[i]=='6'){

six++;

}

else if(s[i]=='7'){

seven++;

}

else if(s[i]=='8'){

eight++;

}

else if(s[i]=='9')

{

nine++;

}

cout<<"0 "<<zero<<endl;

cout<<"1 "<<one<<endl;

cout<<"2 "<<two<<endl;

cout<<"3 "<<three<<endl;

cout<<"4 "<<four<<endl;

cout<<"5 "<<five<<endl;

cout<<"6 "<<six<<endl;

cout<<"7 "<<seven<<endl;

cout<<"8 "<<eight<<endl;

cout<<"9 "<<nine<<endl;

return 0;

}

Leave a comment

Posted in A ll Codes, Adhoc/Brute Force, Algorithm, HackerEarth

C++ Vector push_back()…pop_back()

Posted on June 7, 2017 | Leave a comment

#include<vector>
#include<iostream>
using namespace std;
int main()
{

    vector<string> list;
    cout<<"Please enter the names, press Q to quit:"<<endl;
    string name; //string //
    while(name!="Q")
    {
        cin>>name;
        list.push_back(name); //pushing string to the list
    }
    list.pop_back(); //poping string from the list
    list.pop_back();

    cout<<"You have entered "<<list.size()<<" names:"<<endl;
    for(int i=0; i<list.size(); i++)
    {
        cout<<list[i]<<endl;
    }


    return 0;
}

#include<vector>

#include<iostream>

using namespace std;

int main()

{

vector<string> list;

cout<<"Please enter the names, press Q to quit:"<<endl;

string name; //string //

while(name!="Q")

{

cin>>name;

list.push_back(name); //pushing string to the list

}

list.pop_back(); //poping string from the list

list.pop_back();

cout<<"You have entered "<<list.size()<<" names:"<<endl;

for(int i=0; i<list.size(); i++)

{

cout<<list[i]<<endl;

}

return 0;

}

Leave a comment

Posted in A ll Codes, Algorithm, C++

Tagged STL

Algo – Linked List

Posted on June 5, 2017 | Leave a comment

Best Video Explained:

code:

some bugs here but understood the implementation:

#include<bits/stdc++.h>
void display(void);
void addatbegin(void);
void addafter(void);
struct node
{
    int data;
    struct node *link;
};

struct node *root=NULL;
int len;

void append()
{

    struct node *temp;
    temp=(struct node*)malloc(sizeof(struct node));
    printf("Enter node data: ");
    scanf("%d", &temp->data);
    temp->link=NULL;
    if(root==NULL) //list is empty
    {
        root=temp;
    }
    else
    {
        struct node* p;
        p=root;
        while(p->link!=NULL)
        {
            p=p->link;
        }
        p->link=temp;
    }
}

int length()
{
    int cnt=0;
    struct node *temp;
    temp=root;
    while(temp!=NULL)
    {
        cnt++;
        temp=temp->link;
    }
    return cnt;
}
void display()
{
    struct node* temp;
    temp==root;
    if(temp==NULL)
    {
        printf("List is empty\n");

    }
    else
    {
        while(temp!=NULL)
        {
            printf("%d-->",temp->data);
            temp=temp->link;
        }
        printf("\n");
    }
}
//void delete();

int main()
{
    int ch;
    while(1)
    {
        printf("Single linked list op:");
        printf("1. Append\n");
        printf("2. Add at begin\n");
        printf("3. Add at after\n");
        printf("4. Lenght\n");
        printf("5. Display\n");
        printf("6. Delete\n");
        printf("7. Quit\n");
        printf("enter your chocie: ");
        scanf("%d",ch);
        switch(ch)
        {
        case 1:
            append();
            break;
        case 2:
            addatbegin();
            break;
        case 3:
            addafter();
            break;
        case 4:
            len=length();
            printf("Length=%d",len);
            break;
        case 5:
            display();
            break;
        case 7:
            exit(1);
        default:
            printf("invalid\n");

        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

#include<bits/stdc++.h>

void display(void);

void addatbegin(void);

void addafter(void);

struct node

{

int data;

struct node *link;

};

struct node *root=NULL;

int len;

void append()

{

struct node *temp;

temp=(struct node*)malloc(sizeof(struct node));

printf("Enter node data: ");

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

temp->link=NULL;

if(root==NULL) //list is empty

{

root=temp;

}

else

{

struct node* p;

p=root;

while(p->link!=NULL)

{

p=p->link;

}

p->link=temp;

}

int length()

{

int cnt=0;

struct node *temp;

temp=root;

while(temp!=NULL)

{

cnt++;

temp=temp->link;

}

return cnt;

}

void display()

{

struct node* temp;

temp==root;

if(temp==NULL)

{

printf("List is empty\n");

}

else

{

while(temp!=NULL)

{

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

temp=temp->link;

}

printf("\n");

}

//void delete();

int main()

{

int ch;

while(1)

{

printf("Single linked list op:");

printf("1. Append\n");

printf("2. Add at begin\n");

printf("3. Add at after\n");

printf("4. Lenght\n");

printf("5. Display\n");

printf("6. Delete\n");

printf("7. Quit\n");

printf("enter your chocie: ");

scanf("%d",ch);

switch(ch)

{

case 1:

append();

break;

case 2:

addatbegin();

break;

case 3:

addafter();

break;

case 4:

len=length();

printf("Length=%d",len);

break;

case 5:

display();

break;

case 7:

exit(1);

default:

printf("invalid\n");

}

Leave a comment

Posted in A ll Codes, Algorithm, C, Linked List

Algorithm: Euler’s GCD

Posted on June 3, 2017 | Leave a comment

code:

int euclid_gcd(int a,int b)
{
    int dividend,divisor,remainder;
    dividend = a>=b?a:b;
    divisor= a<=b?a:b;

    while(divisor!=0)
    {
        remainder=dividend%divisor;
        dividend=divisor;
        divisor=remainder;
    }
    return dividend;
}

int euclid_gcd(int a,int b)

{

int dividend,divisor,remainder;

dividend = a>=b?a:b;

divisor= a<=b?a:b;

while(divisor!=0)

{

remainder=dividend%divisor;

dividend=divisor;

divisor=remainder;

}

return dividend;

}

more optimized:

int euclid_gcd(int a,int b)
{
    int dividend,divisor,remainder;
    dividend = a;
    divisor= b;

    while(divisor!=0)
    {
        remainder=dividend%divisor;
        dividend=divisor;
        divisor=remainder;
    }
    return dividend;
}

int euclid_gcd(int a,int b)

{

int dividend,divisor,remainder;

dividend = a;

divisor= b;

while(divisor!=0)

{

remainder=dividend%divisor;

dividend=divisor;

divisor=remainder;

}

return dividend;

}

Recursive:

#include<bits/stdc++.h>
int euclid_gcd_recursive(int a,int b)
{
    return b==0?a:euclid_gcd_recursive(b,a%b);
}
int main()
{
    int d,x,z;
    printf("Scanf a and b:");
    scanf("%d %d",&x,&z);
    d=euclid_gcd_recursive(x,z);
    printf("GCD= %d",d);
    return 0;
}

#include<bits/stdc++.h>

int euclid_gcd_recursive(int a,int b)

{

return b==0?a:euclid_gcd_recursive(b,a%b);

}

int main()

{

int d,x,z;

printf("Scanf a and b:");

scanf("%d %d",&x,&z);

d=euclid_gcd_recursive(x,z);

printf("GCD= %d",d);

return 0;

}

http://www.progkriya.org/gyan/basic-number-theory.html#section3

Leave a comment

Posted in A ll Codes, Algorithm, C, Euler GCD, Number Theory

Algo: Prime factorization of a number

Posted on June 3, 2017 | Leave a comment

code:

#include<bits/stdc++.h>
int main()
{
    int i,n,ct=0;;
    scanf("%d",&n);
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            ct=0;

            while(n%i==0)
            {
                n=n/i;
                ct++;
            }
            printf("(%d^%d)X",i,ct);
        }

    }
    if(n!=1)
        printf("%d^%d",n,1); //it's cleared but will see more about this in future

    return 0;
}

#include<bits/stdc++.h>

int main()

{

int i,n,ct=0;;

scanf("%d",&n);

for(i=2;i<=sqrt(n);i++)

{

if(n%i==0)

{

ct=0;

while(n%i==0)

{

n=n/i;

ct++;

}

printf("(%d^%d)X",i,ct);

}

if(n!=1)

printf("%d^%d",n,1); //it's cleared but will see more about this in future

return 0;

}

I/O:

input: 36
output: (2^2)X(3^2)X

1 2	input: 36 output: (2^2)X(3^2)X

Leave a comment

Posted in A ll Codes, Algorithm, C, Prime factorization

Prime Number: Trial division | Prime check upto N in C

Posted on June 2, 2017 | Leave a comment

code:

#include<bits/stdc++.h>

int main()
{
    int i,j,n,flag=0;
    printf("enter number: ");
    scanf("%d",&n);
    for(i=2;i<=n;i++) //first iterate upto n
    {
        flag=1;
        for(j=2;j<=sqrt(i);j++) //trial division is using here //(i/2) can also use instead of sqrt(i)
        {
            if(i%j==0)
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            printf("%d \t",i);
        }
    }


return 0;

}

#include<bits/stdc++.h>

int main()

{

int i,j,n,flag=0;

printf("enter number: ");

scanf("%d",&n);

for(i=2;i<=n;i++) //first iterate upto n

{

flag=1;

for(j=2;j<=sqrt(i);j++) //trial division is using here //(i/2) can also use instead of sqrt(i)

{

if(i%j==0)

{

flag=0;

break;

}

if(flag==1)

{

printf("%d \t",i);

}

return 0;

}

Help can be find:
http://www.studystreet.com/c-program-print-prime-numbers/
http://www.codingalpha.com/prime-number-c-program/
https://en.wikipedia.org/wiki/Primality_test

Leave a comment

Posted in A ll Codes, Algorithm, C, Trial Division

Tagged Trial Divison

Prime Finding: Sieve of Erastosthenes

Posted on June 2, 2017 | Leave a comment

I have watched the videos from mycodeschool and implemented it:
code:

//find all prime numbers upto n
//sieve of erastosthenes

#include<bits/stdc++.h>
int main()
{
    int n;
    scanf("%d",&n);
    int primes[n];
    for(int i=0; i<=n; i++)
    {
        primes[i]=1; //make prime to all numbers between 0 and n
    }
    primes[0]=0; //0 not prime
    primes[1]=0; //1 not prime
    for(int i=2; i<=n; i++) //2 to n iterating
    {
        if(primes[i]==1)   //if 2 to n is prime then
        {
            for(int j=2; i*j<=n; j++) //j=2 and i*j<=9 means 2*2<=9  
            {
                primes[i*j]=0;  //primes[i*j=2*2=4] means primes[4]=0;
            }
            printf("%d ",i); //
        }
    }

}

//find all prime numbers upto n

//sieve of erastosthenes

#include<bits/stdc++.h>

int main()

{

int n;

scanf("%d",&n);

int primes[n];

for(int i=0; i<=n; i++)

{

primes[i]=1; //make prime to all numbers between 0 and n

}

primes[0]=0; //0 not prime

primes[1]=0; //1 not prime

for(int i=2; i<=n; i++) //2 to n iterating

{

if(primes[i]==1) //if 2 to n is prime then

{

for(int j=2; i*j<=n; j++) //j=2 and i*j<=9 means 2*2<=9

{

primes[i*j]=0; //primes[i*j=2*2=4] means primes[4]=0;

}

printf("%d ",i); //

}

Video:

Leave a comment

Posted in Algorithm, Sieve of Erastosthenes

Tagged Erastosthenes, Prime, Sieve

Algo DS: Circular Queue

Posted on May 31, 2017 | Leave a comment

code:

#include<stdio.h>
#define size 4
int q[size];
int rear=-1;
int front=-1;

Enqueue(int item){
    if((rear+1)%size==front){
        printf("Queue Overflow\n");
    }else{
        if(rear==-1 && front==-1)
        {
            rear=0;
            front=0;
        }
        else{
            rear=(rear+1)%size;
        }
        q[rear]=item;
        printf("%d is inserted\n",item);
    }
}

 Dequeue(){
    int value;
    if(rear==-1 && front==-1)
    {
        printf("Queue underflow\n");
        return -1;
    }
    else{
        value=q[front];
        if(rear==front)
        {
            rear=-1;
            front=-1;
        }
        else{
            front=(front+1)%size;
        }
        return value;
    }
}

void Display()
{
    int i;
    if(rear==-1 && front==-1)
    {
        printf("Queue is empty\n");
    }
    else{
        if(front<=rear)
        {
            for(i=front;i<=rear;i++)
            {
                printf("q[%d]=%d\n",i,q[i]);
            }
        }
        else{
            for(i=front;i<size-1;i++)
            {
                printf("q[%d]=%d\n",i,q[i]);
                for(i=0;i<=rear;i++)
                {
                    printf("q[%d]=%d\n",i,q[i]);
                }
            }
        }
    }


}

int main()
{
    int cho,n;
    do{
        printf("press 1 for queue\n");
        printf("press 2 for dequeue\n");
        printf("press 3 for display\n");
        printf("press 4 for exit\n");
        printf("Enter your choice: ");
        scanf("%d",&cho);
        switch(cho)
        {
        case 1:

            printf("Enter item to insert: ");
            scanf("%d",&n);
            Enqueue(n);
            break;
        case 2:
            Dequeue();
            break;
        case 3:
            Display();
            break;
        }

    }while(cho!=4);


    return 0;
}

100

101

102

103

104

105

#include<stdio.h>

#define size 4

int q[size];

int rear=-1;

int front=-1;

Enqueue(int item){

if((rear+1)%size==front){

printf("Queue Overflow\n");

}else{

if(rear==-1 && front==-1)

{

rear=0;

front=0;

}

else{

rear=(rear+1)%size;

}

q[rear]=item;

printf("%d is inserted\n",item);

}

Dequeue(){

int value;

if(rear==-1 && front==-1)

{

printf("Queue underflow\n");

return -1;

}

else{

value=q[front];

if(rear==front)

{

rear=-1;

front=-1;

}

else{

front=(front+1)%size;

}

return value;

}

void Display()

{

int i;

if(rear==-1 && front==-1)

{

printf("Queue is empty\n");

}

else{

if(front<=rear)

{

for(i=front;i<=rear;i++)

{

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

}

else{

for(i=front;i<size-1;i++)

{

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

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

{

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

}

int main()

{

int cho,n;

do{

printf("press 1 for queue\n");

printf("press 2 for dequeue\n");

printf("press 3 for display\n");

printf("press 4 for exit\n");

printf("Enter your choice: ");

scanf("%d",&cho);

switch(cho)

{

case 1:

printf("Enter item to insert: ");

scanf("%d",&n);

Enqueue(n);

break;

case 2:

Dequeue();

break;

case 3:

Display();

break;

}

}while(cho!=4);

return 0;

}

Leave a comment

Posted in A ll Codes, Algorithm, C, C Refresh, Circular Queue

Data Structure: Queue

Posted on May 26, 2017 | Leave a comment

Stack VS Queue difference:

code:

/*
 * C Program to Implement a Queue using an Array
 */

#include <stdio.h>
#include <conio.h>
#define N 10

int queue[N];
int rear = - 1;
int front = - 1;
main()
{
    int choice;
    while (1)
    {
        printf("1.Insert element to queue \n");
        printf("2.Delete element from queue \n");
        printf("3.Display all elements of queue \n");
        printf("4.Quit \n");
        printf("Enter your choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:insert();
            	   break;

            case 2:delete();
                   break;

            case 3:display();
                   break;

            case 4:exit(1);
            
            default:printf("Wrong choice \n");
            
        } /*End of switch*/
    } /*End of while*/
} /*End of main()*/


insert()
{
    int element;

    if (rear == N - 1)
    printf("Queue Overflow \n");

    else
    {
        if (front == - 1)
        /*If queue is initially empty */
        front = 0;
        
        printf("Inset the element in queue : ");
        scanf("%d", &element);
        rear = rear + 1;
        queue[rear] = element;
    }
} 
 

delete()
{
    if (front == - 1 || front > rear)
    {
        printf("Queue Underflow \n");
        return ;
    }

    else
    {
        printf("Element deleted from queue is : %d\n", queue[front]);
        front = front + 1;
    }
} 


display()
{
    int i;

    if (front == - 1)
        printf("Queue is empty \n");

    else
    {
        printf("Queue is : \n");
        for (i = front; i <= rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
} 


Output:-

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 1
Inset the element in queue : 10

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 1
Inset the element in queue : 50

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 1
Inset the element in queue : 30

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 1
Inset the element in queue : 60

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 2
Element deleted from queue is : 10

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 3
Queue is :
50 30 60

1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit

Enter your choice : 4

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

* C Program to Implement a Queue using an Array

#include <stdio.h>

#include <conio.h>

#define N 10

int queue[N];

int rear = - 1;

int front = - 1;

main()

{

int choice;

while (1)

{

printf("1.Insert element to queue \n");

printf("2.Delete element from queue \n");

printf("3.Display all elements of queue \n");

printf("4.Quit \n");

printf("Enter your choice : ");

scanf("%d", &choice);

switch (choice)

{

case 1:insert();

break;

case 2:delete();

break;

case 3:display();

break;

case 4:exit(1);

default:printf("Wrong choice \n");

} /*End of switch*/

} /*End of while*/

} /*End of main()*/

insert()

{

int element;

if (rear == N - 1)

printf("Queue Overflow \n");

else

{

if (front == - 1)

/*If queue is initially empty */

front = 0;

printf("Inset the element in queue : ");

scanf("%d", &element);

rear = rear + 1;

queue[rear] = element;

}

delete()

{

if (front == - 1 || front > rear)

{

printf("Queue Underflow \n");

return ;

}

else

{

printf("Element deleted from queue is : %d\n", queue[front]);

front = front + 1;

}

display()

{

int i;

if (front == - 1)

printf("Queue is empty \n");

else

{

printf("Queue is : \n");

for (i = front; i <= rear; i++)

printf("%d ", queue[i]);

printf("\n");

}

Output:-

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Inset the element in queue : 10

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Inset the element in queue : 50

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Inset the element in queue : 30

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Inset the element in queue : 60

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 2

Element deleted from queue is : 10

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 3

Queue is :

50 30 60

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 4

My implementation:

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
int q[MAX];
int front=-1;
int rear=-1;
void Insert()
{
    int element;
    if(rear==MAX-1)
        printf("\nQueue Overflow\n");
    else
    {
        if(front==-1)
            front=0;
        printf("Insert the element in queue: ");
        scanf("%d",&element);
        rear=rear+1;
        q[rear]=element;
    }
}

void Delete()
{
    if(front==-1||front>rear)
    {
        printf("\nQueue Underflow\n");
        return;
    }
    else
    {
        printf("\nElement deleted from queue is: %d\n",q[front]);
        front=front+1;
    }
}
void Display()
{
    int i;
    if(front==-1)
        printf("\nQueue is empty\n");
    else
    {
        printf("\nQueue is: ");
        for(i=front; i<=rear; i++)
            printf("%d ",q[i]);
        printf("\n");
    }

}

int main()
{


    int choice;
    while(1)
    {

        printf("1. Insert element to queue\n");
        printf("2. Delete elements\n");
        printf("3. Display all elements\n");
        printf("4. Quit\n");
        printf("Enter your choice: ");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            Insert();
            break;
        case 2:
            Delete();
            break;
        case 3:
            Display();
            break;
        case 4:
            exit(1);
        default:
            printf("Wrong Choice\n");

        }
    }


    return 0;
}

#include<stdio.h>

#include<stdlib.h>

#define MAX 10

int q[MAX];

int front=-1;

int rear=-1;

void Insert()

{

int element;

if(rear==MAX-1)

printf("\nQueue Overflow\n");

else

{

if(front==-1)

front=0;

printf("Insert the element in queue: ");

scanf("%d",&element);

rear=rear+1;

q[rear]=element;

}

void Delete()

{

if(front==-1||front>rear)

{

printf("\nQueue Underflow\n");

return;

}

else

{

printf("\nElement deleted from queue is: %d\n",q[front]);

front=front+1;

}

void Display()

{

int i;

if(front==-1)

printf("\nQueue is empty\n");

else

{

printf("\nQueue is: ");

for(i=front; i<=rear; i++)

printf("%d ",q[i]);

printf("\n");

}

int main()

{

int choice;

while(1)

{

printf("1. Insert element to queue\n");

printf("2. Delete elements\n");

printf("3. Display all elements\n");

printf("4. Quit\n");

printf("Enter your choice: ");

scanf("%d",&choice);

switch(choice)

{

case 1:

Insert();

break;

case 2:

Delete();

break;

case 3:

Display();

break;

case 4:

exit(1);

default:

printf("Wrong Choice\n");

}

return 0;

}

Another Video:

Code from the video Mycodeschool(Using circular queue):

#include<stdio.h>
using namespace std;
#define MAX_SIZE 101
int A[MAX_SIZE];
int fronta,rear;

bool IsEmpty()
{
    return(fronta==-1 && rear==-1);
}

bool IsFull()
{
   // if(rear==MAX_SIZE-1)
    if((rear+1)%MAX_SIZE==fronta)
        return true;
    else
        return false;
}
void Enqeue(int x)
{
    printf("Enqueuing: %d",x);
    if(IsFull()){
        printf("Error: Queue is full\n");
        return;
    }
    else if(IsEmpty())
    {
        fronta=rear=0;
    }
    else
    {
        rear=(rear+1)%MAX_SIZE;
    }
    A[rear]=x;
}

void Dequeue()
{
    printf("Dequeuing:  ");
    if(IsEmpty())
        return;
    else if(fronta==rear)
        fronta=rear=1;
    else
        fronta=(fronta+1)%MAX_SIZE;
}

int Froonta()
{
    if(fronta==-1)
    {
        printf("Can't return from an empty queue\n");
        return -1;
    }
    return A[fronta];
}

void print()
{
    int counta=(rear+MAX_SIZE-fronta)%MAX_SIZE+1;
    printf(" Queue:  ");
    int i;
    for(i=0; i<counta; i++)
    {
        int index=(fronta+i)%MAX_SIZE;
        printf("%d ",A[index]);  //Index of element while traaversing circulrly from front
    }
    printf("\n");
}

int main()
{
    Enqeue(2);
    print();
    Enqeue(4);
    print();
    Enqeue(6);
    print();
    Enqeue(8);
    print();
    Dequeue();
    print();
    Enqeue(8);
    print();
    return 0;
}

#include<stdio.h>

using namespace std;

#define MAX_SIZE 101

int A[MAX_SIZE];

int fronta,rear;

bool IsEmpty()

{

return(fronta==-1 && rear==-1);

}

bool IsFull()

{

// if(rear==MAX_SIZE-1)

if((rear+1)%MAX_SIZE==fronta)

return true;

else

return false;

}

void Enqeue(int x)

{

printf("Enqueuing: %d",x);

if(IsFull()){

printf("Error: Queue is full\n");

return;

}

else if(IsEmpty())

{

fronta=rear=0;

}

else

{

rear=(rear+1)%MAX_SIZE;

}

A[rear]=x;

}

void Dequeue()

{

printf("Dequeuing: ");

if(IsEmpty())

return;

else if(fronta==rear)

fronta=rear=1;

else

fronta=(fronta+1)%MAX_SIZE;

}

int Froonta()

{

if(fronta==-1)

{

printf("Can't return from an empty queue\n");

return -1;

}

return A[fronta];

}

void print()

{

int counta=(rear+MAX_SIZE-fronta)%MAX_SIZE+1;

printf(" Queue: ");

int i;

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

{

int index=(fronta+i)%MAX_SIZE;

printf("%d ",A[index]); //Index of element while traaversing circulrly from front

}

printf("\n");

}

int main()

{

Enqeue(2);

print();

Enqeue(4);

print();

Enqeue(6);

print();

Enqeue(8);

print();

Dequeue();

print();

Enqeue(8);

print();

return 0;

}

Leave a comment

Posted in A ll Codes, Algorithm, C, C Refresh, Queue

Tagged queue

Algorithm: BFS(Breadth First Search)

Posted on May 26, 2017 | Leave a comment

Theory:

http://scanftree.com/Data_Structure/Breadth-First-Search

Bangla:

গ্রাফ থিওরিতে হাতেখড়ি-৪(ব্রেডথ ফার্স্ট সার্চ)

Video:

code implementation:

Some other links may help:

Breadth First Search Algorithm

code:

//bfs implementation for undirected unweighted graph
#include<fstream>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;

int main()
{
    int n,m,start;
    int a,b;
    cin>>n>>m>>start;
    vector<int> samp;
    vector<vector<int> > conn(n+1,samp); //conn taking custom value in vector to make it sizeable

    //loading adjacency matrix
    for(int i=0; i<m; i++)
    {
        cin>>a>>b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
    bool visited[n+1]; //visited node 1 to last
    for(int i=0; i<n+1; i++)
    {
        visited[i]=false;  //making each and every node false
    }
    queue<int> Q;  //creating a queue
    Q.push(start); //pushing the starting node in the queue
    visited[start]=true; //make the starting node only true
    int siz=0;
    int lev=0;
    while(!Q.empty())
    {
        cout<<"LEVEL:"<<lev<<endl;
        siz=Q.size();
        while(siz--)
        {
            int first=Q.front();
            Q.pop();
            cout<<first<<endl;
            for(int j=0; j<conn[first].size(); j++)
            {
                if(!visited[conn[first][j]])
                {
                visited[conn[first][j]]=true; //making true which have visited
                Q.push(conn[first][j]); //pushing the value in the queue
                }
            }

        }
        lev++; //level increasing in each iteration
    }
return 0;
}

//bfs implementation for undirected unweighted graph

#include<fstream>

#include<queue>

#include<vector>

#include<iostream>

using namespace std;

int main()

{

int n,m,start;

int a,b;

cin>>n>>m>>start;

vector<int> samp;

vector<vector<int> > conn(n+1,samp); //conn taking custom value in vector to make it sizeable

//loading adjacency matrix

for(int i=0; i<m; i++)

{

cin>>a>>b;

conn[a].push_back(b);

conn[b].push_back(a);

}

bool visited[n+1]; //visited node 1 to last

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

{

visited[i]=false; //making each and every node false

}

queue<int> Q; //creating a queue

Q.push(start); //pushing the starting node in the queue

visited[start]=true; //make the starting node only true

int siz=0;

int lev=0;

while(!Q.empty())

{

cout<<"LEVEL:"<<lev<<endl;

siz=Q.size();

while(siz--)

{

int first=Q.front();

Q.pop();

cout<<first<<endl;

for(int j=0; j<conn[first].size(); j++)

{

if(!visited[conn[first][j]])

{

visited[conn[first][j]]=true; //making true which have visited

Q.push(conn[first][j]); //pushing the value in the queue

}

lev++; //level increasing in each iteration

}

return 0;

}

Input:

9 10 1 //here 1 is starting node that can be any value
1 2
1 3
3 4
3 5
1 6
4 6
4 9
9 8
1 7
7 3

9 10 1 //here 1 is starting node that can be any value

1 2

1 3

3 4

3 5

1 6

4 6

4 9

9 8

1 7

7 3

Output:

Another code tried to write from the pseudocode is:

#include<iostream>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
//void BFS(int);
int WHITE=1,GRAY=2,BLACK=3,inf=31000,NIL=-1;
int num_e,num_v;
queue<int> Q;
int adj[20][20],color[20],d[20],p[20];
void initialization()
{
    int k,j;
    for(k=0; k<20; k++)
    {
        for(j=0; j<20; j++)
        {
            adj[k][j]=0;
        }
    }
}
void build_adj_matrix()
{
    int i,a,b;
    cin>>num_v;
    cin>>num_e;
    for(i=1; i<=num_e; i++)
    {
        cin>>a>>b;
        adj[a][b]=1;
        adj[b][a]=1;
    }
}
void BFS(int s)
{
    int i,u,v;
    for(i=1; i<=num_v; i++)
    {
        color[i]=WHITE;
        d[i]=inf;
        p[i]=NIL;
    }
    color[s]=GRAY;
    d[s]=0;
    p[s]=NIL;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.pop();
        for(v=1; v<=num_v; v++)
        {
            if(adj[u][v]==1)
            {
                if(color[v]==WHITE)
                {
                    color[v]=GRAY;
                    d[v]=d[u]+1;
                    p[v]=u;
                    Q.push(v);
                }
            }
        }
        color[u]=BLACK;
    }
}
void distance_output()
{
    int i;
    cout<<"Shortest path from source vertex";
    for(i=1; i<=num_v; i++)
    {
        cout<<"to node "<<i<<"is "<<d[i];

    }
}
void path_print(int s,int v)
{
    if(v==s)
    {
        cout<<s<<endl;
    }
    else if(p[v]==NIL)
    {
        cout<<"No path from"<<s<<"to "<<v<<"exists";
    }
    else
    {
        path_print(s,p[v]);
        cout<<v<<endl;
    }
}
int main()
{

    int source,destination;
    initialization();
    build_adj_matrix();
    cin>>source;
    cin>>destination;
    BFS(source);
    distance_output();
    path_print(source,destination);
    return 0;
}

100

101

102

103

#include<iostream>

#include<queue>

#include<bits/stdc++.h>

using namespace std;

//void BFS(int);

int WHITE=1,GRAY=2,BLACK=3,inf=31000,NIL=-1;

int num_e,num_v;

queue<int> Q;

int adj[20][20],color[20],d[20],p[20];

void initialization()

{

int k,j;

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

{

for(j=0; j<20; j++)

{

adj[k][j]=0;

}

void build_adj_matrix()

{

int i,a,b;

cin>>num_v;

cin>>num_e;

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

{

cin>>a>>b;

adj[a][b]=1;

adj[b][a]=1;

}

void BFS(int s)

{

int i,u,v;

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

{

color[i]=WHITE;

d[i]=inf;

p[i]=NIL;

}

color[s]=GRAY;

d[s]=0;

p[s]=NIL;

Q.push(s);

while(!Q.empty())

{

int u=Q.pop();

for(v=1; v<=num_v; v++)

{

if(adj[u][v]==1)

{

if(color[v]==WHITE)

{

color[v]=GRAY;

d[v]=d[u]+1;

p[v]=u;

Q.push(v);

}

color[u]=BLACK;

}

void distance_output()

{

int i;

cout<<"Shortest path from source vertex";

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

{

cout<<"to node "<<i<<"is "<<d[i];

}

void path_print(int s,int v)

{

if(v==s)

{

cout<<s<<endl;

}

else if(p[v]==NIL)

{

cout<<"No path from"<<s<<"to "<<v<<"exists";

}

else

{

path_print(s,p[v]);

cout<<v<<endl;

}

int main()

{

int source,destination;

initialization();

build_adj_matrix();

cin>>source;

cin>>destination;

BFS(source);

distance_output();

path_print(source,destination);

return 0;

}

reference from java code: http://www.programmingboss.com/2014/06/breadth-first-search-bfs-in-java.html

ppt slide: https://drive.google.com/file/d/0B0sCkwd_qKgJSzZyUWVYZU5GWlk/edit

Leave a comment

Posted in A ll Codes, Algorithm, BFS, C, C Refresh

Fibonacci in C with Recursion

Posted on May 16, 2017 | Leave a comment

code from 1:

#include<stdio.h>
long getFibbTerm(int t)
{
    if(t==1||t==2)
        return 1;
    return getFibbTerm(t-1)+getFibbTerm(t-2);
}
int main()
{
    int t;
    for(t=1; t<10; t++)
    {
        printf("%d\t",getFibbTerm(t));
    }
    return 0;
}

#include<stdio.h>

long getFibbTerm(int t)

{

if(t==1||t==2)

return 1;

return getFibbTerm(t-1)+getFibbTerm(t-2);

}

int main()

{

int t;

for(t=1; t<10; t++)

{

printf("%d\t",getFibbTerm(t));

}

return 0;

}

Code from 0:

#include<stdio.h>
long getFibbTerm(int t)
{
    if(t==0)
        return 0;
    if(t==1)
        return 1;
    return getFibbTerm(t-1)+getFibbTerm(t-2);
}
int main()
{
    int t;
    for(t=0; t<10; t++)
    {
        printf("%d\t",getFibbTerm(t));
    }
    return 0;
}

#include<stdio.h>

long getFibbTerm(int t)

{

if(t==0)

return 0;

if(t==1)

return 1;

return getFibbTerm(t-1)+getFibbTerm(t-2);

}

int main()

{

int t;

for(t=0; t<10; t++)

{

printf("%d\t",getFibbTerm(t));

}

return 0;

}

Youtube source:

Leave a comment

Posted in Fibonacci, Recursion

Tagged fibonacci, recursion

Category Archives: Algorithm

Bubble Sort

Selection Sort

QuickSort

Stevie Hackerearth

Basics of Implementation – Hackerearth

C++ Vector push_back()…pop_back()

Algo – Linked List

Algorithm: Euler’s GCD

Algo: Prime factorization of a number

Prime Number: Trial division | Prime check upto N in C

Prime Finding: Sieve of Erastosthenes

Algo DS: Circular Queue

Data Structure: Queue

Algorithm: BFS(Breadth First Search)

Fibonacci in C with Recursion

Caution and Tips:

About Me & MyBlog

Category

Recent Posts

Recent Comments

My Facebook

Follow Me

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

Category Archives: Algorithm

Caution and Tips:

About Me & MyBlog

Category

Recent Posts

Recent Comments

My Facebook

My Github

My Linkedin

Tags

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page