Question

implement merge sort,quick sort, and radix sort algorithms in java and test how long it will take to sort with random data sets of users input numbers.

Answer 1

Merge Sort

/*In the merge sort we divide the array into two parts recursively,until we get a pair of two and then sort them
and join subarrays again by sorting them*/

/*In the merge sort we divide the array into two parts recursively,until we get a pair of two and then sort them
and join subarrays again by sorting them*/
class Main
{
void combine(int a[], int l, int m, int r) // Combine two arrays
{
int e = m - l + 1;
int f = r - m;
int Left[] = new int [e]; //Left array
int Right[] = new int [f];
for (int i=0; i<e; ++i)
Left[i] = a[l + i];
for (int j=0; j<f; ++j)
Right[j] = a[m + 1+ j];
int i = 0, j = 0;
int k = l;
while (i < e && j < f)
{
if (Left[i] <= Right[j])
{
a[k] = Left[i];
i++;
}
else
{
a[k] = Right[j];
j++;
}
k++;
}
while (i < e)
{
a[k] = Left[i];
i++;
k++;
}
while (j < f)
{
a[k] = Right[j];
j++;
k++;
}
}
void applysort(int a[], int l, int r) // Divide the array into two parts
{
if (l < r)
{
int m = (l+r)/2;
applysort(a, l, m); //divide from 0 to half
applysort(a , m+1, r); //half to end
combine(a, l, m, r); //join both by sorting
}
}
static void display(int a[]) //display the array
{
int n = a.length;
for (int i=0; i<n; ++i)
System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int a[] = {9,5,4,5,8,10};

display(a);
  
Main ob = new Main();
ob.applysort(a, 0, a.length-1);
display(a);
}
}

Time Complexity = o(nlogn)

Quick Sort

/* In quick sort we select the pivot element from beginning and then start comparing it with the array from end, if we find the element shorter than pivot element then we replace them, then we start comparing the pivot element from start and if we get element greater than pivot element we replace them, this process is repeated until the pivot element is placed at desired position.*/

class Main
{
int divide(int array[], int start, int end)
{
int ele = array[end];
int i = (start-1);
for (int j=start; j<end; j++)
{
if (array[j] < ele)
{
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i+1];
array[i+1] = array[end];
array[end] = temp;
  
return i+1;
}
void doMaining(int array[], int start, int end)
{
if (start < end) {
int pi = divide(array, start, end);
doMaining(array, start, pi-1);
doMaining(array, pi+1, end);
}
}
  
static void display(int array[])
{
int n = array.length;
for (int i=0; i<n; ++i)
System.out.print(array[i]+" ");
System.out.println();
}
  
public static void main(String args[])
{
int array[] = {5,1,9,5,3,10};
int n = array.length;
  
Main ob = new Main();
ob.doMaining(array, 0, n-1);
  
display(array);
}
}

Average complexity - O(nlogn)

worst complexity - O(n^2)

Radix sort - The radix dort sort the element by digits that is by least significant digits

import java.io.*;
import java.util.*;
  
class Main {
static int FindMax(int array[], int n)
{
int temp = array[0];
for (int i = 1; i < n; i++)
if (array[i] > temp)
temp = array[i];
return temp;
}
  
static void findcount(int array[], int n, int s)
{
int result[] = new int[n];
int i;
int c[] = new int[10];
Arrays.fill(c,0);
  
for (i = 0; i < n; i++)
c[ (array[i]/s)%10 ]++;
for (i = 1; i < 10; i++)
c[i] += c[i - 1];
  
for (i = n - 1; i >= 0; i--)
{
result[c[ (array[i]/s)%10 ] - 1] = array[i];
c[ (array[i]/s)%10 ]--;
}
for (i = 0; i < n; i++)
array[i] = result[i];
}
  
static void dosort(int array[], int n)
{
int m = FindMax(array, n);
for (int s = 1; m/s > 0; s *= 10)
findcount(array, n, s);
}
  
static void display(int array[], int n)
{
for (int i=0; i<n; i++)
System.out.println(array[i]+" ");
}
  
public static void main (String[] args)
{
int array[] = {1,55,89,41,36};
int n = array.length;
dosort(array, n);
display(array, n);
}
}

Time complexity - O(nk) where k is size of integer