three sorting algorithms including the mergesort and quickso

three sorting algorithms, including the merge-sort and quick-sort algorithms.

Implement in JAVA.

Implement in C++ and Java three sorting algorithms, including the merge-sort and quick-sort algorithms, and compare the implementations on CPU time using three different inputs.

Solution

/*
* C++ Program to Implement Merge Sort
*/
#include <iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;
void merge(int *,int, int , int );
void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
void merge(int *a, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= mid)
{
c[k] = a[i];
k++;
i++;
}
while (j <= high)
{
c[k] = a[j];
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}

void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];

/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};

/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}

void BubbleSort(int num[],int n)
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = n;
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (num[j+1] < num[j]) // ascending order simply changes to <
{
temp = num[j]; // swap elements
num[j] = num[j+1];
num[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
int main()
{

int i,a[30],b[30],c[30];
// int a[30]={30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
// int b[30]={30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
// int c[30]={30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
  
  
  
//to generate 30 random numbers
  
  
for(i=0;i<30;i++)
a[i]=b[i]=c[i]=rand()%100;
  
  
int start_s=clock();
mergesort(a, 0, 29);
int stop_s=clock();
cout<<\"sorted array\ \";
for (i = 0; i < 30; i++)
{
cout<<a[i]<<\" \";
}
  
cout << \"\ Execution time for merge sort : \" << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
  
cout<<\"\ \";
start_s=clock();
quickSort(b, 0, 29);
stop_s=clock();
cout<<\"sorted array\ \";
for (i = 0; i < 30; i++)
{
cout<<b[i]<<\" \";
}
cout << \"\ Execution time for quick sort : \" << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
  

  
cout<<\"\ \";
start_s=clock();
BubbleSort(c,30);
stop_s=clock();
cout<<\"sorted array\ \";
for (i = 0; i < 30; i++)
{
cout<<c[i]<<\" \";
}
cout << \"\ Execution time for bubble sort : \" << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
  
  
}