Question

Using Java programming

1. Using System.nanoTime(), compare the performance of bucketsort with the sorting algorithms
   1. insertion sort,
   2. quicksort,
   3. merge sort.

Does it really perform faster in practice?

Answer 1

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Vamsi
*/
public class Comparing_Sorts {
static int maxValue(int[] sequence)
{
int maxValue = 0;
for (int i = 0; i < sequence.length; i++)
if (sequence[i] > maxValue)
maxValue = sequence[i];
return maxValue;
}
//bucket sort
static int[] Bucket_Sort(int[] sequence, int maxValue)
{
// Bucket Sort
int[] Bucket = new int[maxValue + 1];
int[] sorted_sequence = new int[sequence.length];

for (int i = 0; i < sequence.length; i++)
Bucket[sequence[i]]++;

int outPos = 0;
for (int i = 0; i < Bucket.length; i++)
for (int j = 0; j < Bucket[i]; j++)
sorted_sequence[outPos++] = i;

return sorted_sequence;
}
  

//insertion sort
public static void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
  
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
  
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
  
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
  
return i+1;
}
  
  

public static void quicksort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
  
// Recursively sort elements before
// partition and after partition
quicksort(arr, low, pi-1);
quicksort(arr, pi+1, high);
}
}
  
  
//merge sort
public static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
  
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
  
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
  
  
/* Merge the temp arrays */
  
// Initial indexes of first and second subarrays
int i = 0, j = 0;
  
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
  
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
  
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
  
// Main function that sorts arr[l..r] using
// merge()
public static void mergesort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
  
// Sort first and second halves
mergesort(arr, l, m);
mergesort(arr , m+1, r);
  
// Merge the sorted halves
merge(arr, l, m, r);
}
}
  
  
public static void main(String argv[]){
  
int a[] = {1,6,3,8,9,3,4,5,9,1,8,5,4,2,3,44,28,99,31,45};
int c[] =new int[a.length];
  
  
for(int i=0;i<a.length;i++)
c[i]=a[i];
  
int max=a[0];
for(int i=0;i<a.length;i++)
if(max<a[i])max=a[i];
//sorting using bucket sort
long bu = System.nanoTime();
Bucket_Sort(c,max);
bu = System.nanoTime()-bu;
System.out.println("Time taken by bucket sort :"+bu);
  

for(int i=0;i<a.length;i++)
c[i]=a[i];
  
//sorting using insertion sort
long in = System.nanoTime();
insertionSort(c,a.length);
in = System.nanoTime()-in;
System.out.println("Time taken by insertion sort :"+in);
  
for(int i=0;i<a.length;i++)
c[i]=a[i];
  
//sorting using quick sort
long q = System.nanoTime();
quicksort(c,0,a.length-1);
q = System.nanoTime()-q;
System.out.println("Time taken by quick sort :"+q);
  
for(int i=0;i<a.length;i++)
c[i]=a[i];
  
//sorting using bucket sort
long m = System.nanoTime();
mergesort(c,0,a.length-1);
m = System.nanoTime()-m;
System.out.println("Time taken by bucket sort :"+m);
}
  
}



  
  

output:

run:
Time taken by bucket sort :9123
Time taken by insertion sort :7412
Time taken by quick sort :29649
Time taken by bucket sort :38772
BUILD SUCCESSFUL (total time: 0 seconds)