6
I know the Quick Sort algorithm, but at the moment I want to analyze Merge Sort.
I found two types of Merge Sort implementation on the Internet. But when I compare them to the Insertion algorithm, they seem to be 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
There is another way to implement Merge Sort to make it more efficient than the Insertion algorithm ?
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 ------------------------------
}
I think the first point is that a single round is not a good parameter. Who knows how to run 20 times and take the average is standard deviation? I also don’t think it’s interesting to run based on a single starting situation. Finally, you only have 501 distinct items (or would it be 500? , if starting from 1?), the insertion algorithm is optimal when there is partial ordering (up to
o(n)in the best case), mergesort will always executeo(n log n)instructions– Jefferson Quesado
My conclusion is that I see more problematic research methodology than algorithm itself
– Jefferson Quesado
There’s a spot I picked up on
merge2: the extra memory size of mergesort isn + o(log n) + o(1). Note that part is constant, because you need an auxiliary vector in the algorithm, not an auxiliary vector for each function callmerge2. Another point that helps is that you always pass the two vectors, alternating who is the main vector and who is the secondary in recursion.– Jefferson Quesado
Okay @Jefferson Quesado! I’ll follow your lead. Thank you!
– João Paulo Rolim
I made a small model to do the math. Just picking up here your sorting implementations to test and see if the times are compatible
– Jefferson Quesado
What test environment? I’m on my 2.4GHz i7 laptop and, running 100 times bubblesort, I got the accumulated total time of 310 seconds
– Jefferson Quesado
I am creating a repository to make it easier to follow what is being done: https://gitlab.com/totalcross/stack-overflow/tree/master/performance-sort; when finished, I put the relevant parts in the answer
– Jefferson Quesado