测试用例插入排序，归并和快速排序 [英] Test case for Insertion Sort, MergeSort and Quick Sort
本文介绍了测试用例插入排序，归并和快速排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我已经实现（Java）中插入排序，归并，ModifiedMergeSort和快速排序：
ModifiedMergeSort先后为绑定元素的变量。如果要排序的元素都小于或等于绑定，然后用插入排序对它们进行排序。
为什么版本1比版本3，4和5更好？
是结果版本2和6现实？
下面是我的结果（以毫秒为单位）：
版本1 - 插入排序：运行时间超过50试运行
输入尺寸最佳情况最差情况下的平均情况
N = 10000 14 19 14.96
N = 20000 59 60 59.3
N = 40000 234 277 243.1
第2版 - 合并排序：运行时间超过50试运行
输入尺寸最佳情况最差情况下的平均情况
N = 10000 1 15 1.78
N = 20000 3 8 3.4
N = 40000 6月9日6.7
版本3 - 合并排序和插入排序的15个元素：运行时间超过50试运行
输入尺寸最佳情况最差情况下的平均情况
N = 10000 41 52 45.42
N = 20000 170 176 170.56
N = 40000 712 823 728.08
第4版 - 合并排序和插入排序的30个元素：运行时间超过50试运行
输入尺寸最佳情况最差情况下的平均情况
N = 10000 27 33 28.04
N = 20000 113 119 114.36
N = 40000 436 497 444.2
第5版 - 合并排序和插入排序上45元：运行时间超过50试运行
输入尺寸最佳情况最差情况下的平均情况
N = 10000 20 21 20.68
N = 20000 79 82 79.7
N = 40000 321 383 325.64
第6版 - 快速排序：运行时间超过50试运行
输入尺寸最佳情况最差情况下的平均情况
N = 10000 1 9 1.18
N = 20000 2 3 2.06
N = 40000 4 5 4.26
下面是我的code：
包com.testing;
进口com.sorting.InsertionSort;
进口com.sorting.MergeSort;
进口com.sorting.ModifiedMergeSort;
进口com.sorting.RandomizedQuickSort;
/ **
*
* @author mih1406
* /
公共类主要{
私有静态最终诠释R = 50; //＃测试
私有静态诠释N = 0; //输入尺寸
私有静态诠释[]数组; //测试阵列
私有静态诠释[]温度; //测试阵列
私有静态长InsertionSort_best = -1;
私有静态长InsertionSort_worst = -1;
私有静态双InsertionSort_average = -1.0;
私有静态长MergeSort_best = -1;
私有静态长MergeSort_worst = -1;
私有静态双MergeSort_average = -1.0;
私有静态长ModifiedMergeSort_V3_best = -1;
私有静态长ModifiedMergeSort_V3_worst = -1;
私有静态双ModifiedMergeSort_V3_average = -1.0;
私有静态长ModifiedMergeSort_V4_best = -1;
私有静态长ModifiedMergeSort_V4_worst = -1;
私有静态双ModifiedMergeSort_V4_average = -1.0;
私有静态长ModifiedMergeSort_V5_best = -1;
私有静态长ModifiedMergeSort_V5_worst = -1;
私有静态双ModifiedMergeSort_V5_average = -1.0;
私有静态长RandomizedQuickSort_best = -1;
私有静态长RandomizedQuickSort_worst = -1;
私有静态双RandomizedQuickSort_average = -1.0;
公共静态无效的主要（字符串的args []）{
StringBuilder的InsertionSort_text =新的StringBuilder（
版本1 - 插入排序：运行时间超过50个测试运行的\ n）;
StringBuilder的MergeSort_text =新的StringBuilder（
第2版 - 合并排序：运行时间超过50个测试运行的\ n）;
StringBuilder的ModifiedMergeSort_V3_text =新的StringBuilder（
第3版 - 合并排序和插入排序的15个元素：运行时间超过50个试运行的\ n）;
StringBuilder的ModifiedMergeSort_V4_text =新的StringBuilder（
第4版 - 合并排序和插入排序的30个元素：运行时间超过50个试运行的\ n）;
StringBuilder的ModifiedMergeSort_V5_text =新的StringBuilder（
第5版 - 合并排序和插入排序上45元：运行时间超过50个试运行的\ n）;
StringBuilder的RandomizedQuickSort_text =新的StringBuilder（
第6版 - 快速排序：运行时间超过50个测试运行的\ n）;
InsertionSort_text.append（输入尺寸\ t \ t的
+最好的情况\ t \ tWorst情况\ t \ tAverage情况下的\ n）;
MergeSort_text.append（输入尺寸\ t \ t的
+最好的情况\ t \ tWorst情况\ t \ tAverage情况下的\ n）;
ModifiedMergeSort_V3_text.append（输入尺寸\ t \ t的
+最好的情况\ t \ tWorst情况\ t \ tAverage情况下的\ n）;
ModifiedMergeSort_V4_text.append（输入尺寸\ t \ t的
+最好的情况\ t \ tWorst情况\ t \ tAverage情况下的\ n）;
ModifiedMergeSort_V5_text.append（输入尺寸\ t \ t的
+最好的情况\ t \ tWorst情况\ t \ tAverage情况下的\ n）;
RandomizedQuickSort_text.append（输入尺寸\ t \ t的
+最好的情况\ t \ tWorst情况\ t \ tAverage情况下的\ n）;
//当n = 10000
N = 10000;
fillArray（）;
testing_InsertionSort（）;
testing_MergeSort（）;
testing_ModifiedMergeSort（15）;
testing_ModifiedMergeSort（30）;
testing_ModifiedMergeSort（45）;
testing_RandomizedQuickSort（）;
InsertionSort_text.append（N =+ N +\ t \ t+ InsertionSort_best
+\ t \ t \ t+ InsertionSort_worst +\ t \ t \ t的
+ InsertionSort_average +\ N）;
MergeSort_text.append（N =+ N +\ t \ t+ MergeSort_best
+\ t \ t \ t+ MergeSort_worst +\ t \ t \ t的
+ MergeSort_average +\ N）;
ModifiedMergeSort_V3_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V3_best
+\ t \ t \ t+ ModifiedMergeSort_V3_worst +\ t \ t \ t的
+ ModifiedMergeSort_V3_average +\ N）;
ModifiedMergeSort_V4_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V4_best
+\ t \ t \ t+ ModifiedMergeSort_V4_worst +\ t \ t \ t的
+ ModifiedMergeSort_V4_average +\ N）;
ModifiedMergeSort_V5_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V5_best
+\ t \ t \ t+ ModifiedMergeSort_V5_worst +\ t \ t \ t的
+ ModifiedMergeSort_V5_average +\ N）;
RandomizedQuickSort_text.append（N =+ N +\ t \ t+ RandomizedQuickSort_best
+\ t \ t \ t+ RandomizedQuickSort_worst +\ t \ t \ t的
+ RandomizedQuickSort_average +\ N）;
//当n = 20000
N = 20000;
fillArray（）;
testing_InsertionSort（）;
testing_MergeSort（）;
testing_ModifiedMergeSort（15）;
testing_ModifiedMergeSort（30）;
testing_ModifiedMergeSort（45）;
testing_RandomizedQuickSort（）;
InsertionSort_text.append（N =+ N +\ t \ t+ InsertionSort_best
+\ t \ t \ t+ InsertionSort_worst +\ t \ t \ t的
+ InsertionSort_average +\ N）;
MergeSort_text.append（N =+ N +\ t \ t+ MergeSort_best
+\ t \ t \ t+ MergeSort_worst +\ t \ t \ t的
+ MergeSort_average +\ N）;
ModifiedMergeSort_V3_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V3_best
+\ t \ t \ t+ ModifiedMergeSort_V3_worst +\ t \ t \ t的
+ ModifiedMergeSort_V3_average +\ N）;
ModifiedMergeSort_V4_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V4_best
+\ t \ t \ t+ ModifiedMergeSort_V4_worst +\ t \ t \ t的
+ ModifiedMergeSort_V4_average +\ N）;
ModifiedMergeSort_V5_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V5_best
+\ t \ t \ t+ ModifiedMergeSort_V5_worst +\ t \ t \ t的
+ ModifiedMergeSort_V5_average +\ N）;
RandomizedQuickSort_text.append（N =+ N +\ t \ t+ RandomizedQuickSort_best
+\ t \ t \ t+ RandomizedQuickSort_worst +\ t \ t \ t的
+ RandomizedQuickSort_average +\ N）;
//当n = 40000
N = 40000;
fillArray（）;
testing_InsertionSort（）;
testing_MergeSort（）;
testing_ModifiedMergeSort（15）;
testing_ModifiedMergeSort（30）;
testing_ModifiedMergeSort（45）;
testing_RandomizedQuickSort（）;
InsertionSort_text.append（N =+ N +\ t \ t+ InsertionSort_best
+\ t \ t \ t+ InsertionSort_worst +\ t \ t \ t的
+ InsertionSort_average +\ N）;
MergeSort_text.append（N =+ N +\ t \ t+ MergeSort_best
+\ t \ t \ t+ MergeSort_worst +\ t \ t \ t的
+ MergeSort_average +\ N）;
ModifiedMergeSort_V3_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V3_best
+\ t \ t \ t+ ModifiedMergeSort_V3_worst +\ t \ t \ t的
+ ModifiedMergeSort_V3_average +\ N）;
ModifiedMergeSort_V4_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V4_best
+\ t \ t \ t+ ModifiedMergeSort_V4_worst +\ t \ t \ t的
+ ModifiedMergeSort_V4_average +\ N）;
ModifiedMergeSort_V5_text.append（N =+ N +\ t \ t+ ModifiedMergeSort_V5_best
+\ t \ t \ t+ ModifiedMergeSort_V5_worst +\ t \ t \ t的
+ ModifiedMergeSort_V5_average +\ N）;
RandomizedQuickSort_text.append（N =+ N +\ t \ t+ RandomizedQuickSort_best
+\ t \ t \ t+ RandomizedQuickSort_worst +\ t \ t \ t的
+ RandomizedQuickSort_average +\ N）;
的System.out.println（InsertionSort_text）;
的System.out.println（MergeSort_text）;
的System.out.println（ModifiedMergeSort_V3_text）;
的System.out.println（ModifiedMergeSort_V4_text）;
的System.out.println（ModifiedMergeSort_V5_text）;
的System.out.println（RandomizedQuickSort_text）;
}
私有静态无效fillArray（）{
//（重新）创建阵列
阵列=新INT [N];
//填充随机数阵列
//使用for循环和给定的随机数发生器指令
的for（int i = 0; I＆LT; array.length;我++）{
阵列[I] =（int）的（1 +的Math.random（）*（N-0 + 1））;
}
}
私有静态无效testing_InsertionSort（）{
//运行时间阵列
长[] run_times =新长[R]。
//开始/结束时间
长启动;
悠长;
的for（int i = 0; I＆LT; R;我++）{
copyArray（）;
//录制开始时间
开始= System.currentTimeMillis的（）;
//测试算法
InsertionSort.sort（临时）;
//录制结束时间
完成= System.currentTimeMillis的（）;
run_times [i] =完成启动;
}
InsertionSort_best = findMin（run_times）;
InsertionSort_worst = findMax（run_times）;
InsertionSort_average = findAverage（run_times）;
}
私有静态无效testing_MergeSort（）{
//运行时间阵列
长[] run_times =新长[R]。
//开始/结束时间
长启动;
悠长;
的for（int i = 0; I＆LT; R;我++）{
copyArray（）;
//录制开始时间
开始= System.currentTimeMillis的（）;
//测试算法
MergeSort.sort（临时）;
//录制结束时间
完成= System.currentTimeMillis的（）;
run_times [i] =完成启动;
}
MergeSort_best = findMin（run_times）;
MergeSort_worst = findMax（run_times）;
MergeSort_average = findAverage（run_times）;
}
私有静态无效testing_ModifiedMergeSort（INT界）{
//运行时间阵列
长[] run_times =新长[R]。
//设置绑定
ModifiedMergeSort.bound =绑定;
//开始/结束时间
长启动;
悠长;
的for（int i = 0; I＆LT; R;我++）{
copyArray（）;
//录制开始时间
开始= System.currentTimeMillis的（）;
//测试算法
ModifiedMergeSort.sort（临时）;
//录制结束时间
完成= System.currentTimeMillis的（）;
run_times [i] =完成启动;
}
如果（绑定== 15）{
ModifiedMergeSort_V3_best = findMin（run_times）;
ModifiedMergeSort_V3_worst = findMax（run_times）;
ModifiedMergeSort_V3_average = findAverage（run_times）;
}
如果（绑定== 30）{
ModifiedMergeSort_V4_best = findMin（run_times）;
ModifiedMergeSort_V4_worst = findMax（run_times）;
ModifiedMergeSort_V4_average = findAverage（run_times）;
}
如果（绑定== 45）{
ModifiedMergeSort_V5_best = findMin（run_times）;
ModifiedMergeSort_V5_worst = findMax（run_times）;
ModifiedMergeSort_V5_average = findAverage（run_times）;
}
}
私有静态无效testing_RandomizedQuickSort（）{
//运行时间阵列
长[] run_times =新长[R]。
//开始/结束时间
长启动;
悠长;
的for（int i = 0; I＆LT; R;我++）{
copyArray（）;
//录制开始时间
开始= System.currentTimeMillis的（）;
//测试算法
RandomizedQuickSort.sort（临时）;
//录制结束时间
完成= System.currentTimeMillis的（）;
run_times [i] =完成启动;
}
RandomizedQuickSort_best = findMin（run_times）;
RandomizedQuickSort_worst = findMax（run_times）;
RandomizedQuickSort_average = findAverage（run_times）;
}
私有静态长findMax（长[]次）{
长最大值=时间[0];
的for（int i = 1; I＆LT; times.length;我++）{
如果（MAX＆LT;次[I]）{
最大=倍[我]
}
}
返回最大值;
}
私有静态长findMin（长[]次）{
龙敏=时间[0];
的for（int i = 1; I＆LT; times.length;我++）{
如果（分＆GT;次[I]）{
分=倍[我]
}
}
返回分钟;
}
私有静态双findAverage（长[]次）{
长总和= 0;
双平均;
的for（int i = 0; I＆LT; times.length;我++）{
总和+ =次[I]
}
平均=（双）之和/（双）times.length;
平均回报;
}
私有静态无效copyArray（）{
临时=新的INT [N];
System.arraycopy（数组，0，温度，0，array.length）;
}
}
解决方案
似乎有你当前正在开展的一些方法的系统误差。我会说出一些你所面临的最明显的实验性的问题，即使他们可能并不直接是你的实验结果的罪魁祸首。
JVM编译
正如我在注释中说明previously，JVM将默认运行code间preTED模式。这意味着，在你的方法找到的每个字节code指令将PTED在现场除$ P $，然后跑了。
这种方法的优点是，它可以让你的应用程序具有更快的启动时间将比这会被编译为本地code在每台运行中的启动Java程序。
缺点是，虽然没有启动性能命中，你会得到一个较慢的表演节目比你会得到，否则。
要改善这两个问题，一个折衷被带到由JVM团队。最初，你的程序将PTED跨$ P $，但JVM将聚集方法（或零件的方法）被集中使用哪些信息，以及将编译下来只有那些似乎是用了很多。编译时，你会得到一个小的性能损失，但随后的code便一路快于以前。
你必须在做测量时把这个事实考虑在内。
标准的做法是热身JVM，也就是运行你的算法了一下，以确保JVM做了所有需要做的汇编。有code，它温暖的JVM是一样的，你会想标杆之一，它是非常重要的，否则，可能会有一些编辑，而你的标杆code。
测量时间
在测量的时候，你应该使用 System.nanoTime（），而不是 System.currentTimeMillis的的。我不会去了的细节，那些可以访问<一href="http://stackoverflow.com/questions/351565/system-currenttimemillis-vs-system-nanotime">here.
您也应该小心。的code以下块的可以的似乎相当于在第一，但会产生不同的结果大部分的时间：
totalDuration = 0;
对于（i = 0; I＆LT; 1000; ++ I）
startMeasure =现在（）;
算法（）;
endMeasure =现在（）;
持续时间= endMeasure - startMeasure;
totalDuration + =持续时间;
}
// ...
TRIALS_COUNT = 1000;
startMeasure =现在（）;
对于（i = 0; I＆LT; TRIALS_COUNT ++ I）
算法（）;
}
endMeasure =现在（）;
持续时间= endMeasure - startMeasure / TRIALS_COUNT;
为什么呢？因为特别是对于快算法（）的实现，他们的速度越快，就越难以得到准确的结果。
大的输入值
在渐近记法有助于了解的算法是如何将不同的升级 N 大值。应用它们对于小的输入值通常是没有意义的，因为在那个幅度通常你会想是计算操作的precise数量及其相关的费用（一个类似于什么样的Jakub一样）。大O符号才有意义，对于大O的大部分时间。大O将告诉你如何算法工程痛苦的输入值的大小，也不会如何表现为小的数字。典型的例子是，例如快速排序，这对于大的阵列将成为国王，但是这将是普遍较慢尺寸为4或5阵列不是选择或插入排序。你输入的大小似乎是足够大的，虽然。
关于最后一点
和为$ P $由长安pviously指出，通过的Jakub做数学练习是完全错误的，不应该被考虑进去。
I have implemented (in Java) Insertion Sort, MergeSort, ModifiedMergeSort and Quick Sort:
ModifiedMergeSort has a variable for the "bound" of elements. When the elements to be sorted are less than or equal to "bound" then use Insertion Sort to sort them.
How come Version 1 is better than Versions 3, 4 and 5?
Are the results for Versions 2 and 6 realistic?
Here is my results (In Milliseconds):
Version 1 - Insertion Sort: Run-Times over 50 test runs
Input Size Best-Case Worst-Case Average-Case
N = 10000 14 19 14.96
N = 20000 59 60 59.3
N = 40000 234 277 243.1
Version 2 - Merge Sort: Run-Times over 50 test runs
Input Size Best-Case Worst-Case Average-Case
N = 10000 1 15 1.78
N = 20000 3 8 3.4
N = 40000 6 9 6.7
Version 3 - Merge Sort and Insertion Sort on 15 elements: Run-Times over 50 test runs
Input Size Best-Case Worst-Case Average-Case
N = 10000 41 52 45.42
N = 20000 170 176 170.56
N = 40000 712 823 728.08
Version 4 - Merge Sort and Insertion Sort on 30 elements: Run-Times over 50 test runs
Input Size Best-Case Worst-Case Average-Case
N = 10000 27 33 28.04
N = 20000 113 119 114.36
N = 40000 436 497 444.2
Version 5 - Merge Sort and Insertion Sort on 45 elements: Run-Times over 50 test runs
Input Size Best-Case Worst-Case Average-Case
N = 10000 20 21 20.68
N = 20000 79 82 79.7
N = 40000 321 383 325.64
Version 6 - Quick Sort: Run-Times over 50 test runs
Input Size Best-Case Worst-Case Average-Case
N = 10000 1 9 1.18
N = 20000 2 3 2.06
N = 40000 4 5 4.26
Here is my code:
package com.testing;
import com.sorting.InsertionSort;
import com.sorting.MergeSort;
import com.sorting.ModifiedMergeSort;
import com.sorting.RandomizedQuickSort;
/**
*
* @author mih1406
*/
public class Main {
private static final int R = 50; // # of tests
private static int N = 0; // Input size
private static int[] array; // Tests array
private static int[] temp; // Tests array
private static long InsertionSort_best = -1;
private static long InsertionSort_worst = -1;
private static double InsertionSort_average = -1.0;
private static long MergeSort_best = -1;
private static long MergeSort_worst = -1;
private static double MergeSort_average = -1.0;
private static long ModifiedMergeSort_V3_best = -1;
private static long ModifiedMergeSort_V3_worst = -1;
private static double ModifiedMergeSort_V3_average = -1.0;
private static long ModifiedMergeSort_V4_best = -1;
private static long ModifiedMergeSort_V4_worst = -1;
private static double ModifiedMergeSort_V4_average = -1.0;
private static long ModifiedMergeSort_V5_best = -1;
private static long ModifiedMergeSort_V5_worst = -1;
private static double ModifiedMergeSort_V5_average = -1.0;
private static long RandomizedQuickSort_best = -1;
private static long RandomizedQuickSort_worst = -1;
private static double RandomizedQuickSort_average = -1.0;
public static void main(String args[]) {
StringBuilder InsertionSort_text = new StringBuilder(
"Version 1 - Insertion Sort: Run-Times over 50 test runs\n");
StringBuilder MergeSort_text = new StringBuilder(
"Version 2 - Merge Sort: Run-Times over 50 test runs\n");
StringBuilder ModifiedMergeSort_V3_text = new StringBuilder(
"Version 3 - Merge Sort and Insertion Sort on 15 elements: Run-Times over 50 test runs\n");
StringBuilder ModifiedMergeSort_V4_text = new StringBuilder(
"Version 4 - Merge Sort and Insertion Sort on 30 elements: Run-Times over 50 test runs\n");
StringBuilder ModifiedMergeSort_V5_text = new StringBuilder(
"Version 5 - Merge Sort and Insertion Sort on 45 elements: Run-Times over 50 test runs\n");
StringBuilder RandomizedQuickSort_text = new StringBuilder(
"Version 6 - Quick Sort: Run-Times over 50 test runs\n");
InsertionSort_text.append("Input Size\t\t"
+ "Best-Case\t\tWorst-Case\t\tAverage-Case\n");
MergeSort_text.append("Input Size\t\t"
+ "Best-Case\t\tWorst-Case\t\tAverage-Case\n");
ModifiedMergeSort_V3_text.append("Input Size\t\t"
+ "Best-Case\t\tWorst-Case\t\tAverage-Case\n");
ModifiedMergeSort_V4_text.append("Input Size\t\t"
+ "Best-Case\t\tWorst-Case\t\tAverage-Case\n");
ModifiedMergeSort_V5_text.append("Input Size\t\t"
+ "Best-Case\t\tWorst-Case\t\tAverage-Case\n");
RandomizedQuickSort_text.append("Input Size\t\t"
+ "Best-Case\t\tWorst-Case\t\tAverage-Case\n");
// Case N = 10000
N = 10000;
fillArray();
testing_InsertionSort();
testing_MergeSort();
testing_ModifiedMergeSort(15);
testing_ModifiedMergeSort(30);
testing_ModifiedMergeSort(45);
testing_RandomizedQuickSort();
InsertionSort_text.append("N = " + N + "\t\t" + InsertionSort_best
+ "\t\t\t" + InsertionSort_worst + "\t\t\t"
+ InsertionSort_average + "\n");
MergeSort_text.append("N = " + N + "\t\t" + MergeSort_best
+ "\t\t\t" + MergeSort_worst + "\t\t\t"
+ MergeSort_average + "\n");
ModifiedMergeSort_V3_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V3_best
+ "\t\t\t" + ModifiedMergeSort_V3_worst + "\t\t\t"
+ ModifiedMergeSort_V3_average + "\n");
ModifiedMergeSort_V4_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V4_best
+ "\t\t\t" + ModifiedMergeSort_V4_worst + "\t\t\t"
+ ModifiedMergeSort_V4_average + "\n");
ModifiedMergeSort_V5_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V5_best
+ "\t\t\t" + ModifiedMergeSort_V5_worst + "\t\t\t"
+ ModifiedMergeSort_V5_average + "\n");
RandomizedQuickSort_text.append("N = " + N + "\t\t" + RandomizedQuickSort_best
+ "\t\t\t" + RandomizedQuickSort_worst + "\t\t\t"
+ RandomizedQuickSort_average + "\n");
// Case N = 20000
N = 20000;
fillArray();
testing_InsertionSort();
testing_MergeSort();
testing_ModifiedMergeSort(15);
testing_ModifiedMergeSort(30);
testing_ModifiedMergeSort(45);
testing_RandomizedQuickSort();
InsertionSort_text.append("N = " + N + "\t\t" + InsertionSort_best
+ "\t\t\t" + InsertionSort_worst + "\t\t\t"
+ InsertionSort_average + "\n");
MergeSort_text.append("N = " + N + "\t\t" + MergeSort_best
+ "\t\t\t" + MergeSort_worst + "\t\t\t"
+ MergeSort_average + "\n");
ModifiedMergeSort_V3_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V3_best
+ "\t\t\t" + ModifiedMergeSort_V3_worst + "\t\t\t"
+ ModifiedMergeSort_V3_average + "\n");
ModifiedMergeSort_V4_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V4_best
+ "\t\t\t" + ModifiedMergeSort_V4_worst + "\t\t\t"
+ ModifiedMergeSort_V4_average + "\n");
ModifiedMergeSort_V5_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V5_best
+ "\t\t\t" + ModifiedMergeSort_V5_worst + "\t\t\t"
+ ModifiedMergeSort_V5_average + "\n");
RandomizedQuickSort_text.append("N = " + N + "\t\t" + RandomizedQuickSort_best
+ "\t\t\t" + RandomizedQuickSort_worst + "\t\t\t"
+ RandomizedQuickSort_average + "\n");
// Case N = 40000
N = 40000;
fillArray();
testing_InsertionSort();
testing_MergeSort();
testing_ModifiedMergeSort(15);
testing_ModifiedMergeSort(30);
testing_ModifiedMergeSort(45);
testing_RandomizedQuickSort();
InsertionSort_text.append("N = " + N + "\t\t" + InsertionSort_best
+ "\t\t\t" + InsertionSort_worst + "\t\t\t"
+ InsertionSort_average + "\n");
MergeSort_text.append("N = " + N + "\t\t" + MergeSort_best
+ "\t\t\t" + MergeSort_worst + "\t\t\t"
+ MergeSort_average + "\n");
ModifiedMergeSort_V3_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V3_best
+ "\t\t\t" + ModifiedMergeSort_V3_worst + "\t\t\t"
+ ModifiedMergeSort_V3_average + "\n");
ModifiedMergeSort_V4_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V4_best
+ "\t\t\t" + ModifiedMergeSort_V4_worst + "\t\t\t"
+ ModifiedMergeSort_V4_average + "\n");
ModifiedMergeSort_V5_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V5_best
+ "\t\t\t" + ModifiedMergeSort_V5_worst + "\t\t\t"
+ ModifiedMergeSort_V5_average + "\n");
RandomizedQuickSort_text.append("N = " + N + "\t\t" + RandomizedQuickSort_best
+ "\t\t\t" + RandomizedQuickSort_worst + "\t\t\t"
+ RandomizedQuickSort_average + "\n");
System.out.println(InsertionSort_text);
System.out.println(MergeSort_text);
System.out.println(ModifiedMergeSort_V3_text);
System.out.println(ModifiedMergeSort_V4_text);
System.out.println(ModifiedMergeSort_V5_text);
System.out.println(RandomizedQuickSort_text);
}
private static void fillArray() {
// (re)creating the array
array = new int[N];
// filling the array with random numbers
// using for-loop and the given random generator instruction
for(int i = 0; i < array.length; i++) {
array[i] = (int)(1 + Math.random() * (N-0+1));
}
}
private static void testing_InsertionSort() {
// run-times arrays
long [] run_times = new long[R];
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++) {
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
InsertionSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
InsertionSort_best = findMin(run_times);
InsertionSort_worst = findMax(run_times);
InsertionSort_average = findAverage(run_times);
}
private static void testing_MergeSort() {
// run-times arrays
long [] run_times = new long[R];
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++) {
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
MergeSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
MergeSort_best = findMin(run_times);
MergeSort_worst = findMax(run_times);
MergeSort_average = findAverage(run_times);
}
private static void testing_ModifiedMergeSort(int bound) {
// run-times arrays
long [] run_times = new long[R];
// setting the bound
ModifiedMergeSort.bound = bound;
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++) {
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
ModifiedMergeSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
if(bound == 15) {
ModifiedMergeSort_V3_best = findMin(run_times);
ModifiedMergeSort_V3_worst = findMax(run_times);
ModifiedMergeSort_V3_average = findAverage(run_times);
}
if(bound == 30) {
ModifiedMergeSort_V4_best = findMin(run_times);
ModifiedMergeSort_V4_worst = findMax(run_times);
ModifiedMergeSort_V4_average = findAverage(run_times);
}
if(bound == 45) {
ModifiedMergeSort_V5_best = findMin(run_times);
ModifiedMergeSort_V5_worst = findMax(run_times);
ModifiedMergeSort_V5_average = findAverage(run_times);
}
}
private static void testing_RandomizedQuickSort() {
// run-times arrays
long [] run_times = new long[R];
// start/finish times
long start;
long finish;
for(int i = 0; i < R; i++) {
copyArray();
// recording start time
start = System.currentTimeMillis();
// testing the algorithm
RandomizedQuickSort.sort(temp);
// recording finish time
finish = System.currentTimeMillis();
run_times[i] = finish-start;
}
RandomizedQuickSort_best = findMin(run_times);
RandomizedQuickSort_worst = findMax(run_times);
RandomizedQuickSort_average = findAverage(run_times);
}
private static long findMax(long[] times) {
long max = times[0];
for(int i = 1; i < times.length; i++) {
if(max < times[i]) {
max = times[i];
}
}
return max;
}
private static long findMin(long[] times) {
long min = times[0];
for(int i = 1; i < times.length; i++) {
if(min > times[i]) {
min = times[i];
}
}
return min;
}
private static double findAverage(long[] times) {
long sum = 0;
double avg;
for(int i = 0; i < times.length; i++) {
sum += times[i];
}
avg = (double)sum/(double)times.length;
return avg;
}
private static void copyArray() {
temp = new int[N];
System.arraycopy(array, 0, temp, 0, array.length);
}
}
解决方案
There seem to be some systematic errors on the approach you're currently undertaking. I'll state some of the most obvious experimental issues you're facing, even if they might not directly be the culprits of your experimental results.
JVM Compilation
As I've stated previously in a comment, the JVM will by default run your code in interpreted mode. That means each bytecode instruction found in your methods will be interpreted on-the-spot, and then ran.
The advantage of this approach is that it allows your application to have faster startup times than would a Java program that'd be compiled to native code on the startup of each of your runs.
The downside is that while there's no startup performance hit, you'll get a slower performing program than you'd get otherwise.
To ameliorate both concerns, a tradeoff was taken by the JVM team. Initially your program will be interpreted, but the JVM will gather information about which methods (or parts of methods) are being used intensively, and will compile down only those ones that seem to be used a lot. When compiling, you'll get a small performance hit, but then the code will be way faster than was before.
You'll have to take this fact into consideration when doing measurements.
The standard approach is to "warm up the JVM", that is, to run your algorithms for a bit to make sure the JVM does all the compilations it needs to do. It is important to have the code that warms the JVM be the same as the one you'll want to benchmark, otherwise there may be some compilation while you're benchmarking your code.
Measuring time
When measuring time, you should use System.nanoTime() instead of System.currentTimeMillis. I won't go over the details, those can be accessed here.
You should also be careful. The following blocks of code may seem equivalent at first, but will yield different results most of the times:
totalDuration = 0;
for (i = 0; i < 1000; ++i)
startMeasure = now();
algorithm();
endMeasure = now();
duration = endMeasure - startMeasure;
totalDuration += duration;
}
//...
TRIALS_COUNT = 1000;
startMeasure = now();
for (i = 0; i < TRIALS_COUNT; ++i)
algorithm();
}
endMeasure = now();
duration = endMeasure - startMeasure / TRIALS_COUNT;
Why? Because especially for faster algorithm() implementations, the faster they are, the harder it is to get accurate results.
Large input values
The asymptotic notation is useful to understand how different algorithms will escalate for big values of n. Applying them for small input values is often nonsensical, because at that magnitude generally what you'd want is to count the precise number of operations and their associated costs (something akin to what Jakub did). Big O notation only makes sense for big Os most of the time. Big O will tell you how the algorithm works for excruciating input value sizes, not how it will behave for small numbers. The canonical example is for instance QuickSort, which for big arrays will be king, but that will be generally slower for arrays of size 4 or 5 than Selection or Insertion Sort. Your input sizes seem to be big enough, though.
On a final note
and as previously stated by Chang, the mathematical exercise done by Jakub is completely wrong and should not be taken into consideration.
这篇关于测试用例插入排序，归并和快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
