Using C++ implement the sorting using bubble sort, insertion sort merge sort and quick sort

Develop templates for sorting using bubble sort, insertion sort, merge sort and quick sort

Aim

To implement the sorting using bubble sort, insertion sort merge sort and quick sort by using c++.

Algorithm

Step 1: Start the Program Execution

Step 2: Create the Classes and declare all the Variables and Member functions.

Step 3: Create the class with LIST..

Step 4: Create a member function for constructor and to insert the element

in the linked list.

Step 5: Use the pointer to refer the next list.

Step 6: Display the list value.

Step 7:  Stop the Program Execution.

Program:

(a).Develop templates for sorting using bubble sort

#include<iostream.h>

#include<conio.h>

template<class T>

void print(T *a,int n)

{

cout<<a[0];

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

{              

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

}

}

template<class T>

void sort(T *a, int n)

{

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

{

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

{

if(a[j-1]>a[j])

{

T temp=a[j-1];

a[j-1]=a[j];

a[j]=temp;

} }

}  }

void main()

{

int a[]={12,11,15,13,17,14,16,19,18};

clrscr();

cout<<"\n Before sorting";

print(a,9);

sort(a,9);

cout<<"\n After sorting\n";

print(a,9);

char ch[]={'b','d','a','f','g','j','r','u','s'};

cout<<"\n Before sorting\n";

print(ch,9);

sort(ch,9);

cout<<"\n After sorting\n";

print(ch,9);

getch();

}

Output:

 Before sorting12,11,15,13,17,14,16,19,18

 After sorting

11,12,13,14,15,16,17,18

 Before sorting

b,d,a,f,g,j,r,u,s

 After sorting

a,b,d,f,g,j,r,s

(b).Develop templates for sorting using Insertion sort

#include<iostream.h>

#include<conio.h>

template<class T>

void print(T *a,int n)

{

cout<<a[0];

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

{

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

}

}

template<class T>

void sort(T *a,int n)

{

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

{

T temp=a[i];

for(int j=i;j>0&&a[j-1]>temp;j--)

{

a[j]=a[j-1];

}

a[j]=temp;

}

}

void main()

{

int a[]={12,11,15,13,17,14,16,19,18};

clrscr();

cout<<"\n Before sorting";

print(a,9);

sort(a,9);

cout<<"\n After sorting\n";

print(a,9);

char ch[]={'b','d','a','f','g','j','r','u','s'};

cout<<"\n Before sorting\n";

print(ch,9);

sort(ch,9);

cout<<"\n After sorting\n";

print(ch,9);

getch();

}

Output:

 Before sorting12,11,15,13,17,14,16,19,18

 After sorting

11,12,13,14,15,16,17,18,19

 Before sorting

b,d,a,f,g,j,r,u,s

 After sorting

a,b,d,f,g,j,r,s,u

  

(c).Develop templates for sorting using merge sort

#include<iostream.h>

#include<conio.h>

template<class T>

void print(T *a,int n)

{

cout<<a[0];

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

{

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

}

}

template<class T>

void merge(T *a,int n1,int n2)

{

T *temp=new T[n1+n2];

int i=0,j1=0,j2=0;

while(j1<n1 && j2<n2)

temp[i++]=(a[j1]<=a[n1+j2]?a[j1++]:a[n1+j2++]);

while(j1<n1)

temp[i++]=a[j1++];

while(j2<n2)

temp[i++]=(a+n1)[j2++];

for(i=0;i<n1+n2;i++)

a[i]=temp[i];

delete[] temp;

}

template<class T>

void sort(T *a,int n)

{

if(n>1)

{

int n1=n/2;

int n2=n-n1;

sort(a,n1);

sort(a+n1,n2);

merge(a,n1,n2);

}

}

void main()

{

int a[]={12,11,15,13,17,14,16,19,18};

clrscr();

cout<<"\n Before sorting";

print(a,9);

sort(a,9);

cout<<"\n After sorting\n";

print(a,9);

char ch[]={'b','d','a','f','g','j','r','u','s'};

cout<<"\n Before sorting\n";

print(ch,9);

sort(ch,9);

cout<<"\n After sorting\n";

print(ch,9);

getch();

}

Output:

 Before sorting12,11,15,13,17,14,16,19,18

 After sorting

11,12,13,14,15,16,17,18,19

 Before sorting

b,d,a,f,g,j,r,u,s

 After sorting

a,b,d,f,g,j,r,s,u

  

(d). Develop templates of Quick sort algorithm

#include<iostream.h>

#include<conio.h>

template<class T>

void print(T *a,int n)

{

cout<<a[0];

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

{

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

}

}

template<class T>

void quick(T *a,int first,int last)

{

int i,j,pivot;

if(first<last)

{

pivot=a[first];

i=first;

j=last;

while(i<j)

{

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

i++;

while(a[j]>=pivot&&j>first)

j--;

if(i<j)

swap(a,i,j);

}

swap(a,first,j);

quick(a,first,j-1);

quick(a,j+1,last);

}

}

template<class T>

void swap(T *a,int i,int j)

{

T temp=a[i];

a[i]=a[j];

a[j]=temp;

}

void main()

{

int a[]={12,11,13,15,14,17,16,19,18};

clrscr();

cout<<"\n Before Sorting\n";

print(a,9);

quick(a,0,9-1);

cout<<"\n After Sorting\n";

print(a,9);

char ch[]={'b','h','j','c','f','e','r','a','s'};

cout<<"\n Before Sorting\n";

print(ch,9);

quick(ch,0,9-1);

cout<<"\n After Sorting\n";

print(ch,9);

getch();

}

Output:

 Before Sorting

12,11,13,15,14,17,16,19,18

 After Sorting

11,12,13,14,15,16,17,18,19

 Before Sorting

b,h,j,c,f,e,r,a,s

 After Sorting

a,b,c,e,f,h,j,r,s

Posted in: C / C++ Program