Syed Ahmed Zaki

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

Software Development Life Cycle

Posted on June 25, 2017 | Leave a comment

Leave a comment

Posted in Software Development, Software Development Life Cycle(SDLC)

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

SOLID Concepts

Posted on June 23, 2017 | Leave a comment

Leave a comment

Posted in OO Analysis and Design, OOP

Object Oriented Programming Concepts

Posted on June 23, 2017 | Leave a comment

Leave a comment

Posted in OO Analysis and Design

Interview Experience: Software Engineering Interview Guideline for Freshers in Bangladesh

Posted on June 20, 2017 | Leave a comment

Today given an interview for intern position so, I think they asked me some questions that is related to other interview which was Full Time Software Engineering Job I have faced. I have found an pattern for interview purpose in software engineering position in Bangladesh:

Maximum of them ask:
OOP Concept Basic like, What is class, What is Overriding and Overloading(Must be good at it, why it is needed), Polymorphism, Interface, Inherit etc.
Object Oriented Design – Design Pattern, SOLID priniciple
Algorithm Basics – All Sorting, Bubble Sort, QuickSort, Binary Search Tree(BST), (Is must to see first)
Software Development Life Cycle(SDLC) Phases, UML Actors, and Scrum/Agile methodology
Basic SQL, Join, Normalization

-> Basic RAM Related Questions-> Stack/Heap where actually program runs that knowledge

content included in this blog link below must be finished and must be in head when needed anything: http://blog.devskill.com/%E0%A6%B8%E0%A6%AB%E0%A6%9F%E0%A6%93%E0%A7%9F%E0%A7%8D%E0%A6%AF%E0%A6%BE%E0%A6%B0-%E0%A6%A1%E0%A7%87%E0%A6%AD%E0%A7%87%E0%A6%B2%E0%A6%AA%E0%A6%BE%E0%A6%B0%E0%A6%A6%E0%A7%87%E0%A6%B0-%E0%A6%9C%E0%A6%A8/

Leave a comment

Posted in Fresher/Intern, Job

Overriding vs. Overloading in Java

Posted on June 20, 2017 | Leave a comment

Overriding code:

class Dog{
    public void bark(){
        System.out.println("woof ");
    }
}
class Hound extends Dog{
    public void sniff(){
        System.out.println("sniff ");
    }
 
    public void bark(){
        System.out.println("bowl");
    }
}
 
public class OverridingTest{
    public static void main(String [] args){
        Dog dog = new Hound();
        dog.bark();
    }
}

class Dog{

public void bark(){

System.out.println("woof ");

}

class Hound extends Dog{

public void sniff(){

System.out.println("sniff ");

}

public void bark(){

System.out.println("bowl");

}

public class OverridingTest{

public static void main(String [] args){

Dog dog = new Hound();

dog.bark();

}

output:

bowl

bowl

Overloading code:

class Dog{
    public void bark(){
        System.out.println("woof ");
    }
 
    //overloading method
    public void bark(int num){
    	for(int i=0; i<num; i++)
    		System.out.println("woof ");
    }
}

class Dog{

public void bark(){

System.out.println("woof ");

}

//overloading method

public void bark(int num){

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

System.out.println("woof ");

}

Reference:
http://www.programcreek.com/2009/02/overriding-and-overloading-in-java-with-examples/

Leave a comment

Posted in Interview, Java

OOP Clear

Posted on June 17, 2017 | Leave a comment

http://jompesh.com/videos/list/category/76

Leave a comment

Posted in OOP

What are the signs of a fake programmer?

Posted on June 15, 2017 | Leave a comment

What are the signs of a fake programmer?

How would someone with experience in the tech industry (and hopefully experience as a software engineer, but not necessarily) identify someone who just shouldn’t be/wasn’t meant to be a software engineer?

Robin Thomas, M.Tech Computer Science & Security, University of Hyderabad (2016)

Updated Mon · Upvoted by Joe Francis, 24 years as a software engineer, 18 as architect and development manager. and NitHish Divakar, Bachelors in Computer Science. Masters in Computational Science.

They talk and talk about their code. But their code won’t do much talking.
Modular Design. They just don’t understand it. Nor about maintaining a large codebase.
Their comments are larger than their code.
NoSQL and shiny languages/frameworks are their buzzwords. But have no idea why one should or should not use them.
Memorizing code. I repeat. Memorizing code. Line by line. Especially for technical interviews.
Copy-paste code from StackOverflow without at least reading through it once.
Won’t get frustrated when something doesn’t work as intended. It won’t keep them up at night. Would lack that delight at finding the solution that had been staring at his/her face for so long!
They code and its over. They don’t want to keep polishing it later.

Good programmers are mostly lazy. They don’t like to do redundant stuff if it can automated. They are proud of their work. They are always willing to learn. They are always trying to be jack of all trades.

34.8k Views · 1,147 Upvotes · Not for Reproduction

Upvote1.1k

Leave a comment

Posted in Tech Debate

Why Python is Not a Good OOP Language

Posted on June 15, 2017 | Leave a comment

Anonymous

Answered Feb 22

I’ll go against popular opinion. I started with Python. I did all my projects in my Master’s program in Python. However, after graduating, I started working for a company that worked on Microsoft stack. I realized the importance of strongly typed language when it came to writing large applications. I fell for “hey, how simple it is to write hello world program in python” trick. Everything looks nice, and feels better when you write a to-do app. You’ll see the real face of the language when your application grows. I recommend learning python after you have mastered a strongly typed language like Java/C#. There are “recommended” ways to write Python but not enforced upon. Also, I’ve heard learning about types is not a big hurdle for beginners.

Leave a comment

Posted in Python, Tech Debate

Java Programmer

Posted on June 15, 2017 | Leave a comment

CAREER OPPORTUNITY

About Company:
Since its inception in 2000, bdjobs.com has been acknowledged as the most recognized career portal, training center in Bangladesh. Innovative product, dynamic solution & flexibility are core components of bdjobs brand.

Swosti [www.swosti.net], Mobile Credit Card is an offshoot of Bdjobs.com. Swosti, a mBillionth Award-2014 [http://mbillionth.in/] winning concept deals with automated credit and savings management solution in Bangladesh. Now the company invites applications from competent people for the following position(s):

Position : Java Programmer

Educational Requirement:

Graduation/ Masters preferably in CSE, Mathematics, Physics, Accounting from any reputed universities.

Qualifications/ Skill:

Must have good skill in Java programming
Knowledge of Java MVC framework/ Hibernate/ Spring/ GWT/ J2EE/ Eclipse/ JSF/ Oracle/ MySQL/ Tomcat/ iReport/ JMS/ Web Service are needed
Experience in Test Code Development
Good OOP Knowledge
Should be familiar in both operating systems – Linux & Windows
Experience in developing Financial Software will be an added advantage
2~3years proven experience is expected
Educational qualification will be relaxed for the candidates having strong professional skill.

Preference:

Preference will be given to candidates having working experience in development of Android (Mobile based), Financial Applications etc.

Salary: Market-driven

Other Benefits

Yearly two festival bonuses (Applicable after 6 months of joining)
Performance based yearly salary increment & Profit Sharing
Daily refreshment facilities & Lunch benefits
Friendly working environment

Apply Instruction:

Application Deadline: June 15, 201

Leave a comment

Posted in Interview, Java

Hackerearth – Jarvis and Numbers

Posted on June 14, 2017 | Leave a comment

code i have understand for last 6 hours:
problem statement was little bit clumsy but understood atlast:

#include<bits/stdc++.h>
using namespace std;
int gcd(int n1,int n2){
    if(n2!=0)
        return gcd(n2,n1%n2);
    else
        return n1;
}
int main()
{
    int t,i,n,temp,commonfactor,sum,ans;
    cin>>t;
    while(t--)
    {
        sum=0;
        int n;
        cin>>n;
        printf("Main temp %d\n",n);
        for(i=2; i<n; i++)
        {
            int temp=n;
            ans=0;
            while(temp>0)
            {
                ans=ans+temp%i;
                temp=temp/i;
                printf("i=%d temp=%d ",i,temp);
                cout<<"ans="<<ans<<endl;
            }
            sum=sum+ans;
            cout<<"\nSum="<<sum<<endl;
        }
        //cout<<"Sum="<<sum<<endl;
        commonfactor=gcd(sum,n-2);
        cout<<"Common factor :"<<commonfactor<<" ";
        cout<<"N-2 :"<<n-2;
        ans=(n-2)/commonfactor;
        printf("\n%d\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int gcd(int n1,int n2){

if(n2!=0)

return gcd(n2,n1%n2);

else

return n1;

}

int main()

{

int t,i,n,temp,commonfactor,sum,ans;

cin>>t;

while(t--)

{

sum=0;

int n;

cin>>n;

printf("Main temp %d\n",n);

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

{

int temp=n;

ans=0;

while(temp>0)

{

ans=ans+temp%i;

temp=temp/i;

printf("i=%d temp=%d ",i,temp);

cout<<"ans="<<ans<<endl;

}

sum=sum+ans;

cout<<"\nSum="<<sum<<endl;

}

//cout<<"Sum="<<sum<<endl;

commonfactor=gcd(sum,n-2);

cout<<"Common factor :"<<commonfactor<<" ";

cout<<"N-2 :"<<n-2;

ans=(n-2)/commonfactor;

printf("\n%d\n",ans);

}

return 0;

}

accepted code took help from editorial:

#include<bits/stdc++.h>
using namespace std;
int gcd(int n1,int n2){
    if(n2!=0)
        return gcd(n2,n1%n2);
    else
        return n1;
}
int main()
{
    int t,i,n,temp,commonfactor,sum,ans;
    cin>>t;
    while(t--)
    {
        sum=0;
        int n;
        cin>>n;
        //printf("Main temp %d\n",n);
        for(i=2; i<n; i++)
        {
            int temp=n;
            ans=0;
            while(temp>0)
            {
                ans=ans+temp%i;
                temp=temp/i;
              //  printf("i=%d temp=%d ",i,temp);
                //cout<<"ans="<<ans<<endl;
            }
            sum=sum+ans;
           // cout<<"\nSum="<<sum<<endl;
        }
        //cout<<"Sum="<<sum<<endl;
        commonfactor=gcd(sum,n-2);
       // cout<<"Common factor :"<<commonfactor<<" ";
       // cout<<"N-2 :"<<n-2;
        ans=(n-2)/commonfactor;
        printf("%d\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int gcd(int n1,int n2){

if(n2!=0)

return gcd(n2,n1%n2);

else

return n1;

}

int main()

{

int t,i,n,temp,commonfactor,sum,ans;

cin>>t;

while(t--)

{

sum=0;

int n;

cin>>n;

//printf("Main temp %d\n",n);

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

{

int temp=n;

ans=0;

while(temp>0)

{

ans=ans+temp%i;

temp=temp/i;

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

//cout<<"ans="<<ans<<endl;

}

sum=sum+ans;

// cout<<"\nSum="<<sum<<endl;

}

//cout<<"Sum="<<sum<<endl;

commonfactor=gcd(sum,n-2);

// cout<<"Common factor :"<<commonfactor<<" ";

// cout<<"N-2 :"<<n-2;

ans=(n-2)/commonfactor;

printf("%d\n",ans);

}

return 0;

}

official editorial:

#include<stdio.h>

int gcd(int n1, int n2)
{
    if (n2 != 0)
       return gcd(n2, n1%n2);
    else
       return n1;
}

int main(){
    int t,i,n,temp,c,sum,common_factor,ans;
    scanf("%d",&t);             // Take input from user
    while(t--){                 // loop it for t test-cases
        sum = 0;                // Sum variable as average = sum/(n-2)
        scanf("%d",&n);         // Take n as input
        for(i=2;i<=n-1;i++){    // loop for changing the number n to all the bases from 2 to (n-1)
            temp = n;           // storing at temporary variable
            c=0;                // to find the sum of all the numbers formed on conversions and there sum so c = 0
            while(temp > 0){
                c+=temp%i;
                temp=temp/i;
            }
            sum+=c;             // Adding sum of each conversion to the total
        }
        common_factor = gcd(sum,n-2);       // Common factor in sum and n-2 to find the irreducible form of average
        ans = (n-2)/common_factor;          // denominator of average
        printf("%d\n",ans);
    }
return 0;
}

#include<stdio.h>

int gcd(int n1, int n2)

{

if (n2 != 0)

return gcd(n2, n1%n2);

else

return n1;

}

int main(){

int t,i,n,temp,c,sum,common_factor,ans;

scanf("%d",&t); // Take input from user

while(t--){ // loop it for t test-cases

sum = 0; // Sum variable as average = sum/(n-2)

scanf("%d",&n); // Take n as input

for(i=2;i<=n-1;i++){ // loop for changing the number n to all the bases from 2 to (n-1)

temp = n; // storing at temporary variable

c=0; // to find the sum of all the numbers formed on conversions and there sum so c = 0

while(temp > 0){

c+=temp%i;

temp=temp/i;

}

sum+=c; // Adding sum of each conversion to the total

}

common_factor = gcd(sum,n-2); // Common factor in sum and n-2 to find the irreducible form of average

ans = (n-2)/common_factor; // denominator of average

printf("%d\n",ans);

}

return 0;

}

Leave a comment

Posted in HackerEarth, Pore Abar Bujhbo

Codeforces: A. Next Round

Posted on June 13, 2017 | Leave a comment

My code: didn’t passed all testcase:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    int a[100];
    cin>>n;
    cin>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    if(a[k]==0 && a[k+1]==0)
    {
        cout<<"0";
    }
    else if(a[k]==1 && a[k+1]==1)
    {
        cout<<"5";
    }
    else if(n==k)
    {
        cout<<n;
    }

    else if(a[k-1]==a[(k-1)+1])
    {
        printf("%d",k+1);
    }
    else if(a[k]>a[k+1])
    {
        cout<<k;
    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n,k;

int a[100];

cin>>n;

cin>>k;

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

{

cin>>a[i];

}

if(a[k]==0 && a[k+1]==0)

{

cout<<"0";

}

else if(a[k]==1 && a[k+1]==1)

{

cout<<"5";

}

else if(n==k)

{

cout<<n;

}

else if(a[k-1]==a[(k-1)+1])

{

printf("%d",k+1);

}

else if(a[k]>a[k+1])

{

cout<<k;

}

return 0;

}

Then looked out the solution but din’t understand one thing but implemented my own:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    int a[100];
    cin>>n;
    cin>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    int counter=0;
    int margin=a[k-1];
    for(int i=0; i<n; i++)
    {
        if(a[i]>=margin && a[i]) //10 >= 7 && 10//i have confusion in >=&&a[i]
        {
            counter++;
        }
    }
    cout<<counter;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n,k;

int a[100];

cin>>n;

cin>>k;

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

{

cin>>a[i];

}

int counter=0;

int margin=a[k-1];

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

{

if(a[i]>=margin && a[i]) //10 >= 7 && 10//i have confusion in >=&&a[i]

{

counter++;

}

cout<<counter;

return 0;

}

http://itisadumbblog.blogspot.com/2015/05/codeforces-158a-next-round-solution.html

https://tausiq.wordpress.com/2014/07/13/cf-158a-next-round/

Leave a comment

Posted in Codeforces, Pore Abar Bujhbo

Print Hackerearth

Posted on June 12, 2017 | Leave a comment

I am implementing the solution after seeing the code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{

    int n;
    int p;
    cin>>n;
    string s;
    cin>>s;
    int a[7]= {0};
    if(n<11)
    {
        cout<<"0";
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            if(s[i]=='h')
            {
                a[0]++;
            }
            else if(s[i]=='a')
            {
                a[1]++;
            }
            else if(s[i]=='c')
            {
                a[2]++;
            }
            else if(s[i]=='k')
            {
                a[3]++;
            }
            else if(s[i]=='e')
            {
                a[4]++;
            }
            else if(s[i]=='r')
            {
                a[5]++;
            }
            else if(s[i]=='t')
            {
                a[6]++;
            }
        }
        a[0]=a[0]/2;
        a[1]=a[1]/2;
        a[4]=a[4]/2;
        a[5]=a[5]/2;

        p=a[0];
        for(int i=0; i<7; i++)
        {
            if(p>a[i])
            {
                p=a[i];
            }
        }

        cout<<p<<endl;
    }
    return 0;
}

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

int p;

cin>>n;

string s;

cin>>s;

int a[7]= {0};

if(n<11)

{

cout<<"0";

}

else

{

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

{

if(s[i]=='h')

{

a[0]++;

}

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

{

a[1]++;

}

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

{

a[2]++;

}

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

{

a[3]++;

}

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

{

a[4]++;

}

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

{

a[5]++;

}

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

{

a[6]++;

}

a[0]=a[0]/2;

a[1]=a[1]/2;

a[4]=a[4]/2;

a[5]=a[5]/2;

p=a[0];

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

{

if(p>a[i])

{

p=a[i];

}

cout<<p<<endl;

}

return 0;

}

Leave a comment

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

Syed Ahmed Zaki

Bubble Sort

Software Development Life Cycle

Selection Sort

QuickSort

SOLID Concepts

Object Oriented Programming Concepts

Interview Experience: Software Engineering Interview Guideline for Freshers in Bangladesh

Overriding vs. Overloading in Java

OOP Clear

What are the signs of a fake programmer?

Why Python is Not a Good OOP Language

Java Programmer

Hackerearth – Jarvis and Numbers

Codeforces: A. Next Round

Print Hackerearth

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

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