Code:
#include<iostream>
#include<stdio.h>
using namespace std;
int bubbleSort(int *array,int n);
void printElements(int *array,int n);
int swap(int &x, int &y);
void heapify(int a[], int lower, int upper);
int heapsort(int a[], int numelts);
int quicksort(int a[], int numelts);
int partition(int a[],int lower, int upper);
int main()
{
//int a[]={9,6,5,23,2,6,2,7,1,8,99,98}; // BUBBBLE SORT
//int b[]={7,10,5,209,7,8,-2,0,100,45,9,5,2,10,6}; // HEAP SORT
//int c[] = {3,8,-9,56,10,8,22,7,100,45,-9,5,-2,10,6}; // QUICK SORT
int a[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
int b[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
int c[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
int n =30;
int main_count=0;
int count=0;
cout<<"*******BUBBLE SORT**************"<<endl<<endl;
cout<<"Original Array: "<<endl;
printElements(a,n);
cout<<endl<<endl;
cout<<"Sorted Array: "<<endl;
main_count = bubbleSort(a,n); //call to bubble sort
printElements(a,n);
cout<<endl;
cout<<"Number of comparisons: "<<main_count<<endl;
cout<<endl<<endl;
cout<<"*******HEAP SORT**************"<<endl<<endl;
cout<<"Original Array: "<<endl;
printElements(b,n);
cout<<endl<<endl;
cout<<"Sorted Array: "<<endl;
main_count = heapsort(b,n); //call to heap sort
printElements(b,n);
cout<<endl;
cout<<"Number of comparisons: "<<main_count<<endl;
cout<<endl<<endl;
cout<<"*******QUICK SORT**************"<<endl<<endl;
cout<<"Original Array: "<<endl;
printElements(c,n);
cout<<endl<<endl;
cout<<"Sorted Array: "<<endl;
main_count = quicksort(c,n); //call to heap sort
printElements(c,n);
cout<<endl;
cout<<"Number of comparisons: "<<main_count<<endl;
cout<<endl<<endl;
system("pause");
return 0;
}
/***************************************************************************************************************
***************************************************************************************************************
***********************************************END OF MAIN()***************************************************
***************************************************************************************************************
***************************************************************************************************************/
/*This function will print the elements of the
arrays which were sorted by different sorting
methods. It will receive an array and # of
elemnents as a parameter.
*/
void printElements(int *array,int n) //print array elements
{
int i=0;
for(i=0;i<n;i++)
cout<<array[i]<<" ";
cout<<endl;
}
/*BUBBLE SORT
This sorting algorithm is considered inefficient or
stupid, because if given data in reverse order, it
will do a horrible job. It will make n^2(O(n^2)) comparisons.
Bubble Sort works by comparing two adjacent items,
and moves them if there is a need. Bubble Sort will
work best on almost sorted order. It will have about n-1
comparisons. This function will receive an array and a # of
elements to process, as a parameter. This function will only return
count of comparisons made.
*/
int bubbleSort(int *array,int n)//Bubble sort function
{
int i,j;
int count=0;
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
count++;//count # of comparisons
if(array[i]<array[j])
{
int temp=array[i]; //swap
array[i]=array[j];
array[j]=temp;
}
}
}
return count;
}
/*This function will be used by both HEAP SORT and
QUICK SORT. It will be used for interchenging
items when required by algorithm. It will receive
two reference parameters x and y, and will not
return an answer.
*/
int swap(int &x, int &y)
{
int temp;
temp = x;
x = y;
y = temp;
return count;
}
/*This function will be used by HEAP SORT algorithm.
It will be used keep the tree that is being sorted
balanced - that is the major advantage of max heap
over other sorts. It will receive an array to be sorted,
and two integers lower and upper. This function will be
called by heapsort().
*/
void heapify(int a[], int lower, int upper)
{
int parent = lower, child;
while (parent <= (upper+1)/2 - 1) {
child = 2 * parent + 1;
if (child < upper && a[child] < a[child+1]){
child++;
}
if (a[child] > a[parent]) {
swap(a[parent],a[child]);
parent = child;
}
else
return;
}
return;
}
/*HEAP SORT
This function will construct a heap and then reads
of values. This functions will be called ny MAIN(),
after which this function will call heapify().
*/
int heapsort(int a[], int numelts)
{
int count=0;
for (int i = numelts/2 - 1; i >= 0; i--){
heapify(a,i,numelts - 1);
}
for (int i = numelts - 1; i > 0; i--) {
swap(a[0],a[i]);
count++;
heapify(a,0,i-1);
}
return count;
}
/*This function will be used/called by quicksort().
This function will select a position (xpos) to send
partition and then will move array elements to the
left or right side of position
*/
int partition(int a[],int lower, int upper)
{
int lo = lower, hi = upper, xpos = lower;
int x = a[lower];
while(lo <= hi) {
while (hi >= lo && x <= a[hi]){
hi--;
}
if (hi >= lo) {
a[lo] = a[hi];
xpos = hi;
lo++;
}
while (lo <= hi && x >= a[lo]){
lo++;
}
if (lo <= hi) {
a[hi] = a[lo];
xpos = lo;
hi--;
}
}
if (xpos != lower)
a[xpos] = x;
return xpos;
}
/*This function will be used/called by quicksort().
This function will use a value xpos, returned
by partition(), in order to continue the process.
*/
void qsort(int a[], int lower, int upper)
{
int pos;
if (lower >= upper)
return;
pos = partition(a,lower,upper);
qsort(a,lower,pos-1);
qsort(a,pos+1,upper);
return;
}
/*QUICK SORT
This function will be responsible for sorting an
array using Quick Sort method. It will work by
picking a certain element(pivot), then it wil move all
elements smaller to the left, and all larger to the right. The
process wil be repeated untill the array is sorted. The function
will operate recursively. Function receives array as a parameter
and # of elements. It will be called by MAIN()
*/
int quicksort(int a[], int numelts)
{
int count=0;
qsort(a,0,numelts-1);
count++;
return count;
}