I know quick sort algorithm, but I am concerned with merge sort algorithm only.
I found out on internet two types of merge sort algorithm implementation. But when I compare them with insertion algorithm, they seem less efficient and this is not expected for a large number of items.
Enter the number of elements you want to sort:
300000
Time spent to executing BubbleSort: 362123 milliseconds
Time spent to executing Selection: 108285 milliseconds
Time spent to executing Insertion: 18046 milliseconds
Time spent to executing MergeSort: 35968 milliseconds
Time spent to executing MergeSort2: 35823 milliseconds
Is there another way to implement the merge sort algorithm to make it more efficient than the insertion algorithm?
Take a look at my code...
package br.com.test.test1;
import java.util.Random;
import java.util.Scanner;
/**
*
* @author Joao
*/
public class Main {
// generate an int array with random numbers between 0 and 500
public static int[] generateRand(int n){
int[] randArray = new int[n];
Random number = new Random();
// random numbers between 0 and 500
for (int i = 0; i < n; i++){
randArray[i] = number.nextInt(501);
}
return randArray;
}
public static void main(String[] args) {
long startTime;
Scanner input = new Scanner(System.in);
int n;
System.out.println("Enter the number of elements you want to sort:");
n = input.nextInt();
MyArray array = new MyArray(n);
int[] aux = new int[n];
aux = generateRand(n);
array.copy(aux);
startTime = System.currentTimeMillis();
array.bubblesort();
// Time spent to executing BUBBLESORT
System.out.println("\nTime spent to executing BubbleSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");
array.copy(aux);
startTime = System.currentTimeMillis();
array.selection();
// Time spent to executing SELECTION
System.out.println("Time spent to executing Selection: "+(System.currentTimeMillis() - startTime)+" milliseconds");
array.copy(aux);
startTime = System.currentTimeMillis();
array.insertion();
// Time spent to executing INSERTION
System.out.println("Time spent to executing Insertion: "+(System.currentTimeMillis() - startTime)+" milliseconds");
array.copy(aux);
startTime = System.currentTimeMillis();
array.mergeSort(0, n-1);
// Time spent to executing MERGESORT
System.out.println("Time spent to executing MergeSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");
array.copy(aux);
startTime = System.currentTimeMillis();
array.mergeSort2(0, n-1);
// Time spent to executing MERGESORT 2
System.out.println("Time spent to executing MergeSort2: "+(System.currentTimeMillis() - startTime)+" milliseconds");
}
}
---- and ------
package br.com.test.test1;
/**
*
* @author Joao Paulo
*/
class MyArray {
private int[] v;
private int n; // array index
private int len;
public MyArray(int length) {
len = length;
v = new int[len];
n = 0;
}
public void copy(int[] k){
n = 0;
for (int i = 0; i < len; i++) {
v[i] = k[i];
n++;
}
}
public void show(){
for (int i = 0; i < n; i++) {
System.out.print(" " + v[i]);
}
System.out.println("\n");
}
// ******* START OF ALGORITHMS TO SORT *******
// ---------- Start of BubbleSort and Selection --------------
public void bubblesort(){
for (int i = 0; i < n; i++){
for (int j = 0; j < n-1; j++) {
if (v[j] > v[j+1]) {
change(j, j+1);
}
}
}
}
public void selection() {
int min;
for (int i = 0; i < n-1; i++) {
min = i;
for (int j = i+1; j < n; j++){
if (v[j] < v[min]){
min = j;
}
}
change(i, min);
}
}
private void change(int one, int two) {
int temp = v[one];
v[one] = v[two];
v[two] = temp;
}
// ---------- End of BubbleSort and Selection ----------------
// ---------- Start of Insertion -----------------------------
public void insertion() {
int i, j;
int temp;
for (i=1; i < n; i++) {
temp = v[i]; // marked variable
j = i;
while ((j > 0) && (v[j-1] > temp)) {
v[j] = v[j-1];
j = j - 1;
}
v[j] = temp;
}
}
// ---------- End of Insertion -------------------------------
// ---------- Start of MergeSort -----------------------------
public void mergeSort (int start, int end){
if(start == end) return;
int middle = (start+end)/2;
mergeSort(start,middle);
mergeSort(middle+1,end);
merge(start,middle,end);
}
public void merge(int start, int middle, int end) {
int[] aux = new int[v.length];
for (int x = start; x <= end; x++) {
aux[x] = v[x];
}
int i = start;
int j = middle+1;
int k = start;
//emptying out array 'v' inserting items neatly in array 'aux'
while (i <= middle && j <= end) {
if (aux[i] < aux[j]){
v[k++] = aux[i++];
} else {
v[k++] = aux[j++];
}
}
//copying values from 'aux' to 'v'
while (i <= middle){
v[k++] = aux[i++];
}
while (j <= end){
v[k++] = aux[j++];
}
}
// ---------- End of MergeSort -------------------------------
// ---------- Start of MergeSort 2 ----------------------------
public void mergeSort2 (int start, int end) {
if(start >= end) return;
int middle = (start+end)/2;
mergeSort2(start,middle);
mergeSort2(middle+1,end);
merge2(start,middle,end);
}
public void merge2(int start, int middle, int end) {
int[] helper = new int[v.length];
// Copy both parts into the helper array
for (int i = start; i <= end; i++) {
helper[i] = v[i];
}
int i = start;
int j = middle + 1;
int k = start;
// Copy the smallest values from either the left or the right side back to the original array
while (i <= middle && j <= end) {
if (helper[i] <= helper[j]) {
v[k] = helper[i];
i++;
} else {
v[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
v[k] = helper[i];
k++;
i++;
}
// Since we are sorting in-place any leftover elements from the right side
// are already at the right position.
}
// ---------- End of MergeSort 2 ------------------------------
}
