ravenex
- 浏览: 11281 次
- 性别:
- 来自: 体育仓库
-
最新评论
-
ravenex：
chong_zh 写道例子中的Cindy,Mom,Grandm ...
谁是initiating loader -
chong_zh：
例子中的Cindy,Mom,Grandma并没有载入委派关系， ...
谁是initiating loader -
beyondqinghua：
有时间慢慢看,收藏先!
几种排序算法的对比
引用
Programming: Sort Testing
Your task this week is to implement four sorts, and do experiments to see how fast they run for different sizes and types of input data sets. The sorts are: selection sort, insertion sort, bubble sort and merge sort.
We're interested in two "modes" for your program:
A demonstration mode takes in a data set from the user, sorts it with each sorting algorithm, and prints out the data set at each step during each sort. In particular, it prints the entire set after each selection, each insertion, and each bubble swap. For merge sort, it describes each split into smaller subsets, and each merge into a unified subset. (Your output should match example output below.)
A comparison mode does not take a data set from the user or print out any data sets. Rather, it takes a single integer from the user, which is a set size. The program then constructs four data sets of that size: an already sorted set, a reverse-sorted set, a random set, and an "almost-sorted set" where approximately 20% of the elements are out of sort order. The program then uses all four sorts (insertion, selection, bubble, merge) to sort each of the four sets, and times how long each sort took to complete. The program then repeats the entire process for ten trials, and finds an average time for each sort, for each set type. Each of these averages (16 in all, from 160 trials) is then printed out for the user.
The usage of the program is:
$ java SortTester [1 or more integers]
If one integer is given, the program goes into comparison mode for input sets of the given size. If more than one integer is given, the program goes into demonstration mode and sorts the given set of integers.
You do not have to implement the user interface or even the code that collects and reports running-time data. That is all provided. Your only job is to fill in the actual routines that run the four sorts. However, please look over the provided code carefully so that you understand what it is doing, and why.
Please work from the following files:
SortTester.java is the driver class. It accepts and parses integer input from the user, and contains code to perform both demonstration and comparison modes. In the case of comparison mode, it generates sample sets, runs the sorts, and reports the average running times. You do not need to modify this file.
Sorters.java is the back-end that contains functions for performing the four sorts. There is one function set up for you for each sort. The functions take the form of
The first argument, set, is the set of integers you are to sort. The second argument, printSteps, is true if the driver wants step-by-step printouts of how the function is sorting the array (i.e., demonstration mode), and false if the driver wants no printed output whatsoever (i.e., comparison mode). It is critical that if printSteps is false, no output is printed. This is because the act of printing is very, very slow, enough to dwarf the time it actually takes to sort. You will end up timing how long it takes to print, rather than how long it takes to sort.
The function returns a double of the number of milliseconds it takes to perform the sort. You do not need to figure out how to calculate the running time of the function; that is already provided in the framework. At the beginning of the function, the current system time is recorded. At the end of the function, the current system time is recorded again, and the difference between those two times is returned. Do not alter these lines, or else you may return erroneous running time results.
Once you have completed the code, perform experiments to see how long the four sorts take on different sizes and styles of input. Specifically, run your program in comparison mode for sets of 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 and 10000. Plot the results on four graphs, one for each set type. Each set type graph should contain four plots, one for each sort type. The x axis of all four graphs should be the set size, from 1000 to 10000. The y axis should be the running time in milliseconds reported by your program, from 0 to the maximum time encountered in your experiment. (All four graphs should be scaled the same on both axes.)
You may use Microsoft Excel or any other plotting program to do your graphs. Feel free to modify the formatting of the output (in SortTester.java) so that it can be easily copied into Excel -- 160 numbers is a lot to copy by hand. If you like, you can try gnuplot, a free graphing program installed on Cunix. The usage would be
$ gnuplot HW3Sorted.gp
where HW3Sorted.gp is an input file that contains instructions about how to set up the graph, as well as the actual data to plot. The output is stored in a postscript file HW3Sorted.ps. Here is a sample gnuplot file that you can modify to fit your needs. (The output file name, and file format, are set as options in that file.)
Include your graphs, in PS (postscript), TIF or PDF files, as well as the output data from which you constructed your graphs, with your submission. Name the graphs and output file(s) so it is clear which is which. Do not submit graphs in any other format.
Example Output
Programming Analysis
Answer the following questions in your README (each worth 5 points):
For already sorted input, why did the running time for each sort grow as it did with respect to set size? Which sort(s) were able to efficiently recognize already-sorted input, and which continued to take quadratic time as sets grew larger? Why?
What was the ranking of your sorts from fastest to slowest for random input? Why did the slowest sorts perform slowest, and the fastest ones perform fastest? Did your results here match up with expectations?
What differences, if any, do you see between the performances of your sorts over reverse-sorted input and random input? How do you explain these differences or lack of differences?
What differences, if any, do you notice between random input and almost-sorted input? (One of your sorts should have performed surprisingly differently, where the other three performed more or less the same.) How can you explain this? What can you conclude about the suitability of different sorts for different types of input data?
Extra Credit
10 points extra credit for including two variations of Shellsort (Shellsort-A and Shellsort-B) throughout the entire programming assignment (and analysis). This will require adjusting both Java files and adding new plots to all four graphs. Shellsort-A should start with an interval of 1/2 input size and reduce the interval by half on each iteration. (Recall that Shellsort reverts to insertion sort once the interval is 1, and while sorting every "slice" as we discussed in class.) Shellsort-B should start with an interval of 1/2 input size and each iteration should reduce the interval by 2/3 (e.g., 120 goes to 40). For demonstration mode, both should first print the gap sequence they will use, then, for each interval in the gap sequence, each slice, before and after sorting that slice, and then the complete list after the slices are reassembled. (You do not need to print the details of insertion sort for each individual slice). Be sure to test on lists with duplicate elements! (You can modify the driver code, SortTester, to create such lists to test on.) What differences do you see between the performance of Shellsort-A and Shellsort-B, if any? How do you explain these differences by the interval reduction strategy? Do you notice anything unusual if the input size is a power of 2? (Recall our discussion of Shell's gap sequence, which goes by powers of 2.)
10 points extra credit for including four variations of quicksort (quicksort-A through quicksort-D) throughout the entire programming assignment (and analysis). This will require adjusting both Java files and adding new plots to all four graphs. Quicksort-A should use the middle element as the pivot; quicksort-B should use median-of-three pivot selection; quicksort-C should use median-of-five, and quicksort-D should (update) use the actual median element (i.e., scan the entire list and calculate the optimal pivot). For demonstration mode, each recursive call to quicksort should print the original list, the pivot selected, each pair of elements that are swapped, and the final list, with a clear distinction between left partition, pivot and right partition. Be sure to test on lists with duplicate elements! (You can modify the driver code, SortTester, to create such lists to test on.) How does quicksort match up against the other sorts, mergesort in particular? For each type of input set, how did pivot selection affect quicksort running time? How do you explain these differences? (Note: quicksort-A may crash on Cunix for large data sets due to running out of memory. Don't panic if this happens. Document the set size where quicksort runs out of memeory, and include quicksort-A on your graph only up until that set size.)
Your task this week is to implement four sorts, and do experiments to see how fast they run for different sizes and types of input data sets. The sorts are: selection sort, insertion sort, bubble sort and merge sort.
We're interested in two "modes" for your program:
A demonstration mode takes in a data set from the user, sorts it with each sorting algorithm, and prints out the data set at each step during each sort. In particular, it prints the entire set after each selection, each insertion, and each bubble swap. For merge sort, it describes each split into smaller subsets, and each merge into a unified subset. (Your output should match example output below.)
A comparison mode does not take a data set from the user or print out any data sets. Rather, it takes a single integer from the user, which is a set size. The program then constructs four data sets of that size: an already sorted set, a reverse-sorted set, a random set, and an "almost-sorted set" where approximately 20% of the elements are out of sort order. The program then uses all four sorts (insertion, selection, bubble, merge) to sort each of the four sets, and times how long each sort took to complete. The program then repeats the entire process for ten trials, and finds an average time for each sort, for each set type. Each of these averages (16 in all, from 160 trials) is then printed out for the user.
The usage of the program is:
$ java SortTester [1 or more integers]
If one integer is given, the program goes into comparison mode for input sets of the given size. If more than one integer is given, the program goes into demonstration mode and sorts the given set of integers.
You do not have to implement the user interface or even the code that collects and reports running-time data. That is all provided. Your only job is to fill in the actual routines that run the four sorts. However, please look over the provided code carefully so that you understand what it is doing, and why.
Please work from the following files:
SortTester.java is the driver class. It accepts and parses integer input from the user, and contains code to perform both demonstration and comparison modes. In the case of comparison mode, it generates sample sets, runs the sorts, and reports the average running times. You do not need to modify this file.
Sorters.java is the back-end that contains functions for performing the four sorts. There is one function set up for you for each sort. The functions take the form of
public static double sortType (int[] set, boolean printSteps)
The first argument, set, is the set of integers you are to sort. The second argument, printSteps, is true if the driver wants step-by-step printouts of how the function is sorting the array (i.e., demonstration mode), and false if the driver wants no printed output whatsoever (i.e., comparison mode). It is critical that if printSteps is false, no output is printed. This is because the act of printing is very, very slow, enough to dwarf the time it actually takes to sort. You will end up timing how long it takes to print, rather than how long it takes to sort.
The function returns a double of the number of milliseconds it takes to perform the sort. You do not need to figure out how to calculate the running time of the function; that is already provided in the framework. At the beginning of the function, the current system time is recorded. At the end of the function, the current system time is recorded again, and the difference between those two times is returned. Do not alter these lines, or else you may return erroneous running time results.
Once you have completed the code, perform experiments to see how long the four sorts take on different sizes and styles of input. Specifically, run your program in comparison mode for sets of 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 and 10000. Plot the results on four graphs, one for each set type. Each set type graph should contain four plots, one for each sort type. The x axis of all four graphs should be the set size, from 1000 to 10000. The y axis should be the running time in milliseconds reported by your program, from 0 to the maximum time encountered in your experiment. (All four graphs should be scaled the same on both axes.)
You may use Microsoft Excel or any other plotting program to do your graphs. Feel free to modify the formatting of the output (in SortTester.java) so that it can be easily copied into Excel -- 160 numbers is a lot to copy by hand. If you like, you can try gnuplot, a free graphing program installed on Cunix. The usage would be
$ gnuplot HW3Sorted.gp
where HW3Sorted.gp is an input file that contains instructions about how to set up the graph, as well as the actual data to plot. The output is stored in a postscript file HW3Sorted.ps. Here is a sample gnuplot file that you can modify to fit your needs. (The output file name, and file format, are set as options in that file.)
Include your graphs, in PS (postscript), TIF or PDF files, as well as the output data from which you constructed your graphs, with your submission. Name the graphs and output file(s) so it is clear which is which. Do not submit graphs in any other format.
Example Output
$ java SortTester 9 5 1 7 9 20 2 5 6 SELECTION SORT 9 5 1 7 9 20 2 5 6 1 5 9 7 9 20 2 5 6 1 2 9 7 9 20 5 5 6 1 2 5 7 9 20 5 9 6 1 2 5 5 9 20 7 9 6 1 2 5 5 6 20 7 9 9 1 2 5 5 6 7 20 9 9 1 2 5 5 6 7 9 9 20 1 2 5 5 6 7 9 9 20 -=-=-=-=-=-=-=- INSERTION 9 5 1 7 9 20 2 5 6 5 9 1 7 9 20 2 5 6 1 5 9 7 9 20 2 5 6 1 5 7 9 9 20 2 5 6 1 5 7 9 9 20 2 5 6 1 5 7 9 9 20 2 5 6 1 2 5 7 9 9 20 5 6 1 2 5 5 7 9 9 20 6 1 2 5 5 6 7 9 9 20 -=-=-=-=-=-=-=- BUBBLE 9 5 1 7 9 20 2 5 6 Round 1 5 9 1 7 9 20 2 5 6 5 1 9 7 9 20 2 5 6 5 1 7 9 9 20 2 5 6 5 1 7 9 9 2 20 5 6 5 1 7 9 9 2 5 20 6 5 1 7 9 9 2 5 6 20 Round 2 1 5 7 9 9 2 5 6 20 1 5 7 9 2 9 5 6 20 1 5 7 9 2 5 9 6 20 1 5 7 9 2 5 6 9 20 Round 3 1 5 7 2 9 5 6 9 20 1 5 7 2 5 9 6 9 20 1 5 7 2 5 6 9 9 20 Round 4 1 5 2 7 5 6 9 9 20 1 5 2 5 7 6 9 9 20 1 5 2 5 6 7 9 9 20 Round 5 1 2 5 5 6 7 9 9 20 Round 6 No swaps. Final set: 1 2 5 5 6 7 9 9 20 -=-=-=-=-=-=-=- MERGE 9 5 1 7 9 20 2 5 6 Divided 9 5 1 7 9 20 2 5 6 into 9 5 1 7 and 9 20 2 5 6 Divided 9 5 1 7 into 9 5 and 1 7 Divided 9 5 into 9 and 5 Merged 9 and 5 into 5 9 Divided 1 7 into 1 and 7 Merged 1 and 7 into 1 7 Merged 5 9 and 1 7 into 1 5 7 9 Divided 9 20 2 5 6 into 9 20 and 2 5 6 Divided 9 20 into 9 and 20 Merged 9 and 20 into 9 20 Divided 2 5 6 into 2 and 5 6 Divided 5 6 into 5 and 6 Merged 5 and 6 into 5 6 Merged 2 and 5 6 into 2 5 6 Merged 9 20 and 2 5 6 into 2 5 6 9 20 Merged 1 5 7 9 and 2 5 6 9 20 into 1 2 5 5 6 7 9 9 20 1 2 5 5 6 7 9 9 20
$ java SortTester 10000 Testing performance for sets of 10000, 10 trials... SELECTION SORTED 10000 130.6 SELECTION ALMOST-SORTED 10000 130.4 SELECTION REVERSE 10000 131.0 SELECTION RANDOM 10000 131.0 INSERTION SORTED 10000 0.2 INSERTION ALMOST-SORTED 10000 25.6 INSERTION REVERSE 10000 218.2 INSERTION RANDOM 10000 109.5 BUBBLE SORTED 10000 0.0 BUBBLE ALMOST-SORTED 10000 523.9 BUBBLE REVERSE 10000 676.1 BUBBLE RANDOM 10000 689.3 MERGE SORTED 10000 5.3 MERGE ALMOST-SORTED 10000 4.2 MERGE REVERSE 10000 3.9 MERGE RANDOM 10000 5.2
Programming Analysis
Answer the following questions in your README (each worth 5 points):
For already sorted input, why did the running time for each sort grow as it did with respect to set size? Which sort(s) were able to efficiently recognize already-sorted input, and which continued to take quadratic time as sets grew larger? Why?
What was the ranking of your sorts from fastest to slowest for random input? Why did the slowest sorts perform slowest, and the fastest ones perform fastest? Did your results here match up with expectations?
What differences, if any, do you see between the performances of your sorts over reverse-sorted input and random input? How do you explain these differences or lack of differences?
What differences, if any, do you notice between random input and almost-sorted input? (One of your sorts should have performed surprisingly differently, where the other three performed more or less the same.) How can you explain this? What can you conclude about the suitability of different sorts for different types of input data?
Extra Credit
10 points extra credit for including two variations of Shellsort (Shellsort-A and Shellsort-B) throughout the entire programming assignment (and analysis). This will require adjusting both Java files and adding new plots to all four graphs. Shellsort-A should start with an interval of 1/2 input size and reduce the interval by half on each iteration. (Recall that Shellsort reverts to insertion sort once the interval is 1, and while sorting every "slice" as we discussed in class.) Shellsort-B should start with an interval of 1/2 input size and each iteration should reduce the interval by 2/3 (e.g., 120 goes to 40). For demonstration mode, both should first print the gap sequence they will use, then, for each interval in the gap sequence, each slice, before and after sorting that slice, and then the complete list after the slices are reassembled. (You do not need to print the details of insertion sort for each individual slice). Be sure to test on lists with duplicate elements! (You can modify the driver code, SortTester, to create such lists to test on.) What differences do you see between the performance of Shellsort-A and Shellsort-B, if any? How do you explain these differences by the interval reduction strategy? Do you notice anything unusual if the input size is a power of 2? (Recall our discussion of Shell's gap sequence, which goes by powers of 2.)
10 points extra credit for including four variations of quicksort (quicksort-A through quicksort-D) throughout the entire programming assignment (and analysis). This will require adjusting both Java files and adding new plots to all four graphs. Quicksort-A should use the middle element as the pivot; quicksort-B should use median-of-three pivot selection; quicksort-C should use median-of-five, and quicksort-D should (update) use the actual median element (i.e., scan the entire list and calculate the optimal pivot). For demonstration mode, each recursive call to quicksort should print the original list, the pivot selected, each pair of elements that are swapped, and the final list, with a clear distinction between left partition, pivot and right partition. Be sure to test on lists with duplicate elements! (You can modify the driver code, SortTester, to create such lists to test on.) How does quicksort match up against the other sorts, mergesort in particular? For each type of input set, how did pivot selection affect quicksort running time? How do you explain these differences? (Note: quicksort-A may crash on Cunix for large data sets due to running out of memory. Don't panic if this happens. Document the set size where quicksort runs out of memeory, and include quicksort-A on your graph only up until that set size.)
SortTester.java:
import java.util.Random;
/**
* Sort-tester driver class for 3134 S08 HW3. DKE, 2/2008
*/
public class SortTester {
/**
* Constructor receives command-line arguments.
*/
public SortTester(String[] args) throws Exception {
// At least one argument required.
if (args.length < 1) {
throw new Exception(
"SortTester must be run with at least 1 integer argument.");
}
if (args.length == 1) {
// If the user gave one argument it is assumed to be a set
// size for comparison mode.
comparison(Integer.parseInt(args[0]));
} else {
// Otherwise, the multiple arguments are assumed to be
// a set for demonstration mode.
demonstration(args);
}
}
/**
* Main function constructs a SortTester object.
*/
public static void main(String[] args) throws Exception {
try {
new SortTester(args);
} catch (Exception e) {
//System.err.println(e.getMessage());
e.printStackTrace();
}
}
/**
* Sort the set provided the user. Demonstrate how the various sets work.
*/
public void demonstration(String[] stringSet) throws Exception {
int[] set;
/**
* Prepare an array of ints that is the same size as the array of
* strings given at the command line.
*/
set = new int[stringSet.length];
// Convert the strings to ints..
// For each string in the input set...
for (int i = 0; i < stringSet.length; i++) {
String token = stringSet[i];
try {
// Convert the string to int.
set[i] = Integer.parseInt(token);
} catch (NumberFormatException e) {
throw new Exception("Bad integer in position " + (i + 1) + ": "
+ token);
}
}
System.out.println("Ready to sort " + set.length + " integers.");
// Run selection sort
Sorters.selectionSort(makeCopy(set), true);
// Run insertion sort
Sorters.insertionSort(makeCopy(set), true);
// Run bubble sort
Sorters.bubbleSort(makeCopy(set), true);
// Run merge sort
Sorters.mergeSort(makeCopy(set), true);
// Run Shellsort-A
Sorters.shellSortA(makeCopy(set), true);
// Run Shellsort-B
Sorters.shellSortB(makeCopy(set), true);
// Run Quicksort-A
Sorters.quickSortA(makeCopy(set), true);
// Run Quicksort-B
Sorters.quickSortB(makeCopy(set), true);
// Run Quicksort-C
Sorters.quickSortC(makeCopy(set), true);
// Run Quicksort-D
Sorters.quickSortD(makeCopy(set), true);
}
public static int[] makeCopy(int[] set) {
int[] result = new int[set.length];
for (int i = 0; i < set.length; i++) {
result[i] = set[i];
}
return result;
}
/**
* Run each the sorts 10 times on a user-given set size and report the
* average time it took for each sort to run.
*/
public void comparison(int setSize) throws Exception {
// Number of trials
int trials = 10;
// Matrix stores the times for each experiment
// First [] stores the sort type, from 0 to 9
// Second [] stores the set type, from 0 to 3
double[][] times = new double[10][4];
int[] set;
System.out.println("Testing performance for sets of " + setSize + ", "
+ trials + " trials...");
// For each trial...
for (int i = 0; i < trials; i++) {
// Make a sorted set and do selection sort
set = makeSortedSet(setSize);
times[0][0] += Sorters.selectionSort(set, false);
// Make a sorted set and do insertion sort
set = makeSortedSet(setSize);
times[1][0] += Sorters.insertionSort(set, false);
// Make a sorted set and do bubble sort
set = makeSortedSet(setSize);
times[2][0] += Sorters.bubbleSort(set, false);
// Make an sorted set and do merge sort
set = makeSortedSet(setSize);
times[3][0] += Sorters.mergeSort(set, false);
// Make an sorted set and do Shellsort-A
set = makeSortedSet(setSize);
times[4][0] += Sorters.shellSortA(set, false);
// Make an sorted set and do Shellsort-B
set = makeSortedSet(setSize);
times[5][0] += Sorters.shellSortB(set, false);
// Make an sorted set and do Quicksort-A
set = makeSortedSet(setSize);
times[6][0] += Sorters.quickSortA(set, false);
// Make an sorted set and do Quicksort-B
set = makeSortedSet(setSize);
times[7][0] += Sorters.quickSortB(set, false);
// Make an sorted set and do Quicksort-C
set = makeSortedSet(setSize);
times[8][0] += Sorters.quickSortC(set, false);
// Make an sorted set and do Quicksort-D
set = makeSortedSet(setSize);
times[9][0] += Sorters.quickSortD(set, false);
// Make an almost sorted set and do selection sort
set = makeAlmostSortedSet(setSize);
times[0][1] += Sorters.selectionSort(set, false);
// Make an almost sorted set and do insertion sort
set = makeAlmostSortedSet(setSize);
times[1][1] += Sorters.insertionSort(set, false);
// Make an almost sorted set and do bubble sort
set = makeAlmostSortedSet(setSize);
times[2][1] += Sorters.bubbleSort(set, false);
// Make an almost sorted set and do merge sort
set = makeAlmostSortedSet(setSize);
times[3][1] += Sorters.mergeSort(set, false);
// Make an almost sorted set and do Shellsort-A
set = makeAlmostSortedSet(setSize);
times[4][1] += Sorters.shellSortA(set, false);
// Make an almost sorted set and do Shellsort-B
set = makeAlmostSortedSet(setSize);
times[5][1] += Sorters.shellSortB(set, false);
// Make an almost sorted set and do Quicksort-A
set = makeAlmostSortedSet(setSize);
times[6][1] += Sorters.quickSortA(set, false);
// Make an almost sorted set and do Quicksort-B
set = makeAlmostSortedSet(setSize);
times[7][1] += Sorters.quickSortB(set, false);
// Make an almost sorted set and do Quicksort-C
set = makeAlmostSortedSet(setSize);
times[8][1] += Sorters.quickSortC(set, false);
// Make an almost sorted set and do Quicksort-D
set = makeAlmostSortedSet(setSize);
times[9][1] += Sorters.quickSortD(set, false);
// Make a reverse sorted set and do selection sort
set = makeReverseSet(setSize);
times[0][2] += Sorters.selectionSort(set, false);
// Make a reverse sorted set and do insertion sort
set = makeReverseSet(setSize);
times[1][2] += Sorters.insertionSort(set, false);
// Make a reverse sorted set and do bubble sort
set = makeReverseSet(setSize);
times[2][2] += Sorters.bubbleSort(set, false);
// Make a reverse sorted set and do merge sort
set = makeReverseSet(setSize);
times[3][2] += Sorters.mergeSort(set, false);
// Make an reverse sorted set and do Shellsort-A
set = makeReverseSet(setSize);
times[4][2] += Sorters.shellSortA(set, false);
// Make an reverse sorted set and do Shellsort-B
set = makeReverseSet(setSize);
times[5][2] += Sorters.shellSortB(set, false);
// Make an reverse sorted set and do Quicksort-A
set = makeReverseSet(setSize);
times[6][2] += Sorters.quickSortA(set, false);
// Make an reverse sorted set and do Quicksort-B
set = makeReverseSet(setSize);
times[7][2] += Sorters.quickSortB(set, false);
// Make an reverse sorted set and do Quicksort-C
set = makeReverseSet(setSize);
times[8][2] += Sorters.quickSortC(set, false);
// Make an reverse sorted set and do Quicksort-D
set = makeReverseSet(setSize);
times[9][2] += Sorters.quickSortD(set, false);
// Make a random set and do selection sort
set = makeRandomSet(setSize);
times[0][3] += Sorters.selectionSort(set, false);
// Make a random set and do insertion sort
set = makeRandomSet(setSize);
times[1][3] += Sorters.insertionSort(set, false);
// Make a random set and do bubble sort
set = makeRandomSet(setSize);
times[2][3] += Sorters.bubbleSort(set, false);
// Make a random set and do merge sort
set = makeRandomSet(setSize);
times[3][3] += Sorters.mergeSort(set, false);
// Make an random set and do Shellsort-A
set = makeRandomSet(setSize);
times[4][3] += Sorters.shellSortA(set, false);
// Make an random set and do Shellsort-B
set = makeRandomSet(setSize);
times[5][3] += Sorters.shellSortB(set, false);
// Make an random set and do Quicksort-A
set = makeRandomSet(setSize);
times[6][3] += Sorters.quickSortA(set, false);
// Make an random set and do Quicksort-B
set = makeRandomSet(setSize);
times[7][3] += Sorters.quickSortB(set, false);
// Make an random set and do Quicksort-C
set = makeRandomSet(setSize);
times[8][3] += Sorters.quickSortC(set, false);
// Make an random set and do Quicksort-D
set = makeRandomSet(setSize);
times[9][3] += Sorters.quickSortD(set, false);
}
// Now we need to compile and print the results.
// For each sort type...
for (int sortType = 0; sortType < 10; sortType++) {
// Choose the string that represents the sort type
String sortTypeString;
if (sortType == 0) {
sortTypeString = "SELECTION";
} else if (sortType == 1) {
sortTypeString = "INSERTION";
} else if (sortType == 2) {
sortTypeString = "BUBBLE";
} else if (sortType == 3) {
sortTypeString = "MERGE";
} else if (sortType == 4) {
sortTypeString = "SHELLSORT-A";
} else if (sortType == 5) {
sortTypeString = "SHELLSORT-B";
} else if (sortType == 6) {
sortTypeString = "QUICKSORT-A";
} else if (sortType == 7) {
sortTypeString = "QUICKSORT-B";
} else if (sortType == 8) {
sortTypeString = "QUICKSORT-C";
} else {
sortTypeString = "QUICKSORT-D";
}
// For each set type..
for (int setType = 0; setType < 4; setType++) {
// Find the AVERAGE time among the trials by dividing the
// running sum by the number of trials
times[sortType][setType] /= trials;
// Choose the string that represents the set type
String setTypeString;
if (setType == 0) {
setTypeString = "SORTED";
} else if (setType == 1) {
setTypeString = "ALMOST-SORTED";
} else if (setType == 2) {
setTypeString = "REVERSE";
} else {
setTypeString = "RANDOM";
}
// Print the results
System.out.println(sortTypeString + " " + setTypeString + " "
+ setSize + " " + times[sortType][setType]);
}
}
}
/**
* Make a sorted set of integers.
*/
public static int[] makeSortedSet(int size) {
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = i + 1;
}
return result;
}
/**
* Make an almost-sorted set of integers.
*/
public static int[] makeAlmostSortedSet(int size) {
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = i + 1;
}
Random r = new Random();
// Swap one-fifth of the elements with other elements
for (int i = 0; i < (size / 10); i++) {
// Pick two random elements and swap them
int firstToSwap = r.nextInt(size);
int secondToSwap = r.nextInt(size);
int crossover = result[firstToSwap];
result[firstToSwap] = result[secondToSwap];
result[secondToSwap] = crossover;
}
return result;
}
/**
* Make a reverse-sorted set of integers.
*/
public static int[] makeReverseSet(int size) {
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = size - i;
}
return result;
}
/**
* Make a random set of integers.
*/
public static int[] makeRandomSet(int size) {
Random r = new Random();
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = r.nextInt();
}
return result;
}
}
Sorters.java:
/**
* Back-end class for 3134 HW3. This is the one you edit.
*/
public class Sorters {
/**
* Run selection sort on a set.
*/
public static double selectionSort(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("SELECTION SORT");
System.out.println(printList(set));
}
// DO SELECTION SORT HERE!
// Print progress if printSteps is set to true.
int length = set.length;
for (int i = 0; i < length - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < length; ++j) {
if (set[minIdx] > set[j]) {
minIdx = j;
}
}
swap(set, i, set, minIdx);
// print progress
if (printSteps) {
System.out.println(printList(set));
}
}
// Print the output set if we are asked to.
if (printSteps) {
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
/**
* Run insertion sort on a set.
*/
public static double insertionSort(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
insertionSort(set, 0, set.length - 1, printSteps);
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
/**
* Internal method shared by insertion sort and Quicksort methods.
*
* @param set
* @param left
* @param right
* @param printSteps
*/
private static void insertionSort(int[] set, int left, int right,
boolean printSteps) {
int length = right - left + 1;
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("INSERTION");
System.out.println(printList(set, left, length));
;
}
// DO INSERTION SORT HERE!
// Print progress if printSteps is set to true.
int j = 0;
for (int i = left + 1; i <= right; ++i) {
// avoids explicit swap
int min = set[i];
for (j = i; (j > left) && (set[j - 1] > min); --j) {
set[j] = set[j - 1];
}
set[j] = min;
// print progress
if (printSteps) {
System.out.println(printList(set, left, length));
}
}
// Print the output set if we are asked to.
if (printSteps) {
System.out.println("-=-=-=-=-=-=-=-");
}
}
/**
* Run bubble sort on a set.
*/
public static double bubbleSort(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("BUBBLE");
System.out.println(printList(set));
}
// DO BUBBLE SORT HERE!
// Print progress if printSteps is set to true.
int length = set.length;
for (int round = 1; round < length; ++round) {
boolean hasSwap = false;
if (printSteps) {
System.out.println("Round " + round);
}
for (int j = 0; j < length - round; ++j) {
if (set[j] > set[j + 1]) {
swap(set, j, set, j + 1);
hasSwap = true;
if (printSteps) {
System.out.println(printList(set));
}
}
}
// the array is already sorted, end loop
if (!hasSwap) {
break;
}
}
// Print the output set if we are asked to.
if (printSteps) {
System.out.println("No swaps. Final set:");
System.out.println(printList(set));
;
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
/**
* Run merge sort on a set.
*/
public static double mergeSort(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("MERGE");
System.out.println(printList(set));
}
// DO MERGE SORT HERE!
// (You will need to call other functions, recursively)
// Print progress if printSteps is set to true.
int length = set.length;
int[] copy = new int[length];
mergeSort(set, copy, 0, length - 1, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
/**
* Internal method that makes resursive calls.
*
* @param array
* the original array to sort.
* @param tempArray
* an array to place the merged result.
* @param left
* the left-most index of the subarray.
* @param right
* the right-most index of the subarray.
* @param printSteps
* whether to print sort progress.
*/
private static void mergeSort(int[] array, int[] tempArray, int left,
int right, boolean printSteps) {
if (left < right) {
int center = (left + right) / 2;
if (printSteps) {
System.out.print("Divided ");
System.out.print(printList(array, left, right - left + 1));
System.out.print(" into ");
System.out.print(printList(array, left, center - left + 1));
System.out.print(" and ");
System.out
.println(printList(array, center + 1, right - center));
}
mergeSort(array, tempArray, left, center, printSteps);
mergeSort(array, tempArray, center + 1, right, printSteps);
merge(array, tempArray, left, center + 1, right, printSteps);
}
}
/**
* Internal method to merge two sorted halves of a subarray.
*
* @param array
* the original array to sort.
* @param tempArray
* an array to place the merged result.
* @param leftIdx
* the left-most index of the subarray.
* @param rightIdx
* the index of the start of the second half.
* @param rightEnd
* the right-most index of the subarray.
* @param printSteps
* whether to print sort progress.
*/
private static void merge(int[] array, int[] tempArray, int leftIdx,
int rightIdx, int rightEnd, boolean printSteps) {
int leftEnd = rightIdx - 1;
int tempIdx = leftIdx;
int tempIdx2 = tempIdx;
int numElements = rightEnd - leftIdx + 1;
if (printSteps) {
System.out.print("Merged ");
System.out.print(printList(array, leftIdx, leftEnd - leftIdx + 1));
System.out.print(" and ");
System.out
.print(printList(array, rightIdx, rightEnd - rightIdx + 1));
}
// main loop
while (leftIdx <= leftEnd && rightIdx <= rightEnd) {
if (array[leftIdx] < array[rightIdx]) {
tempArray[tempIdx++] = array[leftIdx++];
} else {
tempArray[tempIdx++] = array[rightIdx++];
}
}
// copy rest of left half
while (leftIdx <= leftEnd) {
tempArray[tempIdx++] = array[leftIdx++];
}
// copy rest of right half
while (rightIdx <= rightEnd) {
tempArray[tempIdx++] = array[rightIdx++];
}
if (printSteps) {
System.out.print(" into ");
System.out.println(printList(tempArray, tempIdx2, tempIdx
- tempIdx2));
}
// copy tempArray back
for (int i = 0; i < numElements; ++i, --rightEnd) {
array[rightEnd] = tempArray[rightEnd];
}
}
/**
* Run Shellsort-A on a set.
*/
public static double shellSortA(int[] set, boolean printSteps) {
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("SHELLSORT-A");
System.out.println(printList(set));
}
// DO SHELLSORT-A HERE!
// Print progress if printSteps is set to true.
double result = shellSort(set, 1.0 / 2.0, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
return result;
}
/**
* Run Shellsort-B on a set.
*/
public static double shellSortB(int[] set, boolean printSteps) {
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("SHELLSORT-B");
System.out.println(printList(set));
}
// DO SHELLSORT-B HERE!
// Print progress if printSteps is set to true.
double result = shellSort(set, 1.0 / 3.0, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
return result;
}
/**
* Internal method, run Shellsort on a set.
*/
private static double shellSort(int[] set, double reductionRatio,
boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
int length = set.length;
// print gap sequence
if (printSteps) {
System.out.print("GAP SEQUENCE:");
for (int gap = length / 2; gap > 0; gap *= reductionRatio) {
System.out.print(" " + gap);
}
System.out.println();
}
for (int gap = length / 2; gap > 0; gap *= reductionRatio) {
// print the slices before sort in current interval
if (printSteps) {
System.out.println("Gap: " + gap);
for (int i = 0; i < gap; ++i) {
if (printSteps) {
System.out.print("Slice before:");
for (int j = i; j < length; j += gap) {
System.out.print(" " + set[j]);
}
System.out.println();
}
}
}
// sort the slices
for (int i = gap; i < length; ++i) {
// avoids explicit swap
int temp = set[i];
int j = i;
for (; (j >= gap) && (temp < set[j - gap]); j -= gap) {
set[j] = set[j - gap];
}
set[j] = temp;
}
// print the slices after sort in current interval
if (printSteps) {
for (int i = 0; i < gap; ++i) {
if (printSteps) {
System.out.print("Slice after:");
for (int j = i; j < length; j += gap) {
System.out.print(" " + set[j]);
}
System.out.println();
}
}
}
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
private static final int CUTOFF = 10;
public static double quickSortA(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("QUICKSORT-A");
System.out.println(printList(set));
}
// DO QUICKSORT-A HERE!
// Print progress if printSteps is set to true.
_quickSortA(set, 0, set.length - 1, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
private static void _quickSortA(int[] set, int left, int right,
boolean printSteps) {
if (printSteps) {
System.out.println("List: " + printList(set));
}
if (left + CUTOFF <= right) {
// select pivot
int center = (left + right) / 2;
int pivot = set[center];
if (printSteps) {
System.out.println("Pivot: " + pivot);
}
// place pivot at position right
set[center] = set[right];
set[right] = pivot;
// Begin partitioning
int i = left - 1;
int j = right;
while (true) {
while (set[++i] < pivot) { }
while ((j > left) && (set[--j] > pivot)) { }
if (i < j) {
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[j]);
}
swap(set, i, set, j);
} else {
break;
}
}
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[right]);
}
swap(set, i, set, right); // Restore pivot
_quickSortA(set, left, i - 1, printSteps); // Sort small elements
_quickSortA(set, i + 1, right, printSteps); // Sort large elements
} else {
insertionSort(set, left, right, false);
}
}
public static double quickSortB(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("QUICKSORT-B");
System.out.println(printList(set));
}
// DO QUICKSORT-B HERE!
// Print progress if printSteps is set to true.
_quickSortB(set, 0, set.length - 1, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
private static void _quickSortB(int[] set, int left, int right,
boolean printSteps) {
if (printSteps) {
System.out.println("List: " + printList(set));
}
if (left + CUTOFF <= right) {
// median3 implicitly places pivot at position right-1
int pivot = median3(set, left, right);
if (printSteps) {
System.out.println("Pivot: " + pivot);
}
// begin partitioning
int i = left;
int j = right - 1;
while (true) {
while (set[++i] < pivot) { }
while (set[--j] > pivot) { }
if (i < j) {
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[j]);
}
swap(set, i, set, j);
} else {
break;
}
}
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[right - 1]);
}
swap(set, i, set, right - 1); // restore pivot
_quickSortB(set, left, i - 1, printSteps);
_quickSortB(set, i + 1, right, printSteps);
} else {
insertionSort(set, left, right, false);
}
}
public static double quickSortC(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("QUICKSORT-C");
System.out.println(printList(set));
}
// DO QUICKSORT-C HERE!
// Print progress if printSteps is set to true.
_quickSortC(set, 0, set.length - 1, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
private static void _quickSortC(int[] set, int left, int right,
boolean printSteps) {
if (printSteps) {
System.out.println("List: " + printList(set));
}
if (left + CUTOFF <= right) {
// median5 implicitly places pivot at position right-1
int pivot = median5(set, left, right);
if (printSteps) {
System.out.println("Pivot: " + pivot);
}
// begin partitioning
int i = left;
int j = right - 1;
while (true) {
while (set[++i] < pivot) { }
while (set[--j] > pivot) { }
if (i < j) {
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[j]);
}
swap(set, i, set, j);
} else {
break;
}
}
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[right - 1]);
}
swap(set, i, set, right - 1); // restore pivot
_quickSortC(set, left, i - 1, printSteps);
_quickSortC(set, i + 1, right, printSteps);
} else {
insertionSort(set, left, right, false);
}
}
public static double quickSortD(int[] set, boolean printSteps) {
// Mark the start time.
double startTime = System.currentTimeMillis();
// Print the input set if we are asked to.
if (printSteps) {
System.out.println("QUICKSORT-D");
System.out.println(printList(set));
}
// DO QUICKSORT-D HERE!
// Print progress if printSteps is set to true.
_quickSortD(set, 0, set.length - 1, printSteps);
// Print the output set if we are asked to.
if (printSteps) {
System.out.println(printList(set));
System.out.println("-=-=-=-=-=-=-=-");
}
// Mark the finish time and return the time it took to sort.
return System.currentTimeMillis() - startTime;
}
private static void _quickSortD(int[] set, int left, int right,
boolean printSteps) {
if (printSteps) {
System.out.println("List: " + printList(set));
}
if (left + CUTOFF <= right) {
// use quick select to find the actual median as pivot
// the pivot is placed at position center
int pivot = quickSelectMedian(set, left, right, printSteps);
if (printSteps) {
System.out.println("Pivot: " + pivot);
}
// place pivot at position right
int center = left + (right - left) / 2;
set[center] = set[right];
set[right] = pivot;
// Begin partitioning
int i = left - 1;
int j = right;
while (true) {
while (set[++i] < pivot) { }
while ((j > left) && (set[--j] > pivot)) { }
if (i < j) {
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[j]);
}
swap(set, i, set, j);
} else {
break;
}
}
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[right]);
}
swap(set, i, set, right); // Restore pivot
_quickSortD(set, left, i - 1, printSteps); // Sort small elements
_quickSortD(set, i + 1, right, printSteps); // Sort large elements
} else {
insertionSort(set, left, right, false);
}
}
private static int median3(int[] set, int left, int right) {
int center = (left + right) / 2;
// sort the subarray of left-center-right
if (set[center] < set[left]) {
swap(set, left, set, center);
}
if (set[right] < set[left]) {
swap(set, left, set, right);
}
if (set[right] < set[center]) {
swap(set, center, set, right);
}
// place pivot at position right-1
swap(set, center, set, right - 1);
return set[right - 1];
}
// a hack to reduce memory allocation time
private static int[] _tempArrayForMedian5 = new int[5];
private static int median5(int[] set, int left, int right) {
int center = (left + right) / 2;
int leftCenter = (left + center) / 2;
int rightCenter = (center + right) / 2;
// sort the subarray of
// left-leftCenter-center-rightCenter-rightCenter
_tempArrayForMedian5[0] = set[left];
_tempArrayForMedian5[1] = set[leftCenter];
_tempArrayForMedian5[2] = set[center];
_tempArrayForMedian5[3] = set[rightCenter];
_tempArrayForMedian5[4] = set[right];
insertionSort(_tempArrayForMedian5, false);
// copy the sort results back to the input array
// and place the pivot at position right-1
set[left] = _tempArrayForMedian5[0];
set[leftCenter] = _tempArrayForMedian5[1];
set[center] = set[right - 1];
set[right - 1] = _tempArrayForMedian5[2];
set[rightCenter] = _tempArrayForMedian5[3];
set[right] = _tempArrayForMedian5[4];
return set[right - 1];
}
public static int quickSelectMedian(int[] set, int left, int right,
boolean printSteps) {
int k = (right - left) / 2 + 1; // expected median's index as k
quickSelect(set, left, right, k, printSteps);
return set[left + k - 1];
}
/**
* Internal selection method that makes recursive calls. Uses
* median-of-three partitioning and a cutoff of 10. Places the kth smallest
* item in set[k-1]. NOTE: This method will modify the input array's order.
*
* @param set
* the input array of int.
* @param left
* the left-most index of the subarray.
* @param right
* the right-most index of the subarray.
* @param k
* the desired rank (1 is minimum) in the entire array.
*/
private static void quickSelect(int[] set, int left, int right, int k,
boolean printSteps) {
if (left + CUTOFF <= right) {
int pivot = median3(set, left, right);
// begin partitioning
int i = left;
int j = right - 1;
while (true) {
while (set[++i] < pivot) { }
while (set[--j] > pivot) { }
if (i < j) {
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[j]);
}
swap(set, i, set, j);
} else {
break;
}
}
if (printSteps) {
System.out.println("Pair to swap: " + set[i] + ", "
+ set[right - 1]);
}
swap(set, i, set, right - 1); // restore pivot
if (k - 1 < i) {
quickSelect(set, left, i - 1, k, printSteps);
} else if (k - 1 > i) {
quickSelect(set, i + 1, right, k, printSteps);
}
} else {
// do an insertion sort on the subarray
insertionSort(set, left, right, false);
}
}
/**
* Return a rendering of a list as a StringBuffer. You can pass the buffer
* to a System.out.println() to actually print the set.
*/
private static StringBuffer printList(int[] set) {
return printList(set, 0, set.length);
}
private static StringBuffer printList(int[] set, int beginIdx, int length) {
StringBuffer result = new StringBuffer();
for (int i = 0; i < length; i++) {
result.append(set[beginIdx++]);
// Add spaces between elements
if (i < (length - 1)) {
result.append(" ");
}
}
return result;
}
private static final void swap(int[] src, int srcIdx, int[] dst, int dstIdx) {
int temp = src[srcIdx];
src[srcIdx] = dst[dstIdx];
dst[dstIdx] = temp;
}
}
AutomateSortComparisonReport.java: see attached file.
Uses JFreeChart 1.0.1 for charting. Visit http://www.jfree.org/jfreechart/ for more information on JFreeChart.
Sample plot graphs of this project can be found here: http://rednaxelafx.iteye.com/blog/174063
- AutomateSortComparisonReport.zip (2.9 KB)
- 下载次数: 57
分享到：
发表评论
相关推荐
关于数据的几种排序算法的程序对比分析，结合具体案例
每种排序算法都有其独特的应用场景和优缺点。在实际开发中，我们需要根据数据特性、内存限制以及时间效率要求来选择合适的排序算法。例如，快速排序通常用于通用排序，而归并排序可能更适合于需要稳定排序的结果，...
在提供的文件`test.cpp`、`sort.cpp`和`sort.h`中，你可能会找到这些排序算法的具体实现代码，通过阅读和分析这些代码，你可以进一步理解每种排序算法的细节，以及如何在C++中有效地实现它们。这些实现可以帮助你更...
【内部排序算法比较课程设计】主要关注的是对六种经典的内部排序算法的性能对比，包括起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆排序。这些算法是计算机科学中用于对数据进行排序的基础工具，各...
本篇文章将详细探讨几种常见的排序算法：快速排序、插入排序、基数排序、希尔排序以及归并排序，并在不同数据规模下进行性能对比。 **快速排序（Quick Sort）** 快速排序由C.A.R. Hoare在1960年提出，它是一种采用...
本项目针对内部排序算法进行了性能分析，通过设计一个测试程序，对比了几种常见内部排序算法的关键字比较次数和移动次数，以帮助我们更直观地理解不同算法的效率差异。以下是关于内部排序算法的一些关键知识点： 1....
各种排序算法效率分析比较及源代码 C语言实现 各种排序包括： 直接插入排序，折半插入排序，2—路插入排序和表插入排序；希尔排序和链式基数排序；起泡排序，快速排序，归并排序；简单选择排序，树形选择排序和堆...
这个文件"JAVA关于几种排序算法的性能比较.pdf"显然探讨了不同排序算法在Java环境下的效率对比，包括直接插入排序、直接选择排序、冒泡排序、希尔排序、快速排序和堆排序。这些排序算法各有优劣，适用于不同的场景，...
在实现测试程序时，我们可以为每种排序算法设计一个函数，记录每一步的比较和移动操作，最后统计总次数。例如，可以创建一个通用的接口，定义比较和移动的计数器，然后让每个排序算法函数调用这个接口。这样可以保证...
以下是几种常见的排序算法的详细说明： 1. 直接插入排序（Insertion Sort）： 直接插入排序是一种简单的排序算法，它通过比较当前元素与前面已排序的元素，将元素逐步插入到正确的位置。在每一轮中，它将一个未排序...
1. **算法实现**：详细描述每种排序算法的代码实现，包括关键步骤和逻辑。 2. **性能分析**：通过时间复杂度和空间复杂度的理论分析，对比不同算法的效率。 3. **实际测试**：通过真实数据对每种算法进行测试，记录...
- **原理**：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆属性：即子节点的键值或索引总是小于（或大于）它的父节点。 - **时间复杂度**：最好、平均、最坏情况均为O...
通过分析这三种排序算法的实现，我们不仅了解了它们的基本原理和操作流程，还对比了它们在不同场景下的性能表现。插入排序和冒泡排序由于其简单直观的特点，在教学和小规模数据处理中被广泛采用；而二分插入排序则在...
描述部分指明了实验的目的和范围，要求对六种排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序、桶排序——进行实现并比较它们的性能。 #### 标签解读 标签“算法导论 排序算法”标明了该文档属于...
本文将详细讲解C#中实现的几种常见排序算法，并对它们的执行效率进行对比。 1. **冒泡排序（Bubble Sort）** 冒泡排序是一种简单的排序方法，通过重复遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把...
实验结果分析则需对比不同算法在不同数据规模下的表现，并可能包括中间结果的展示，以全面评估排序算法的性能。同时，提交实验报告时，应包括带中间结果和不带中间结果的两种打印版本，以满足不同需求的分析。