Executive Summary

This report aims to identify the 4 corresponding sorts from the 18 given sorts, after running and anlysing the four given test sort programs. The 4 given programs' code are not given.

Introduction

In the previous report, it has alrealy mentioned each sort's feature in detail.  This report has to use the previous materials to give the right answers and give a detailed analysis on how the results be worked out. 

Analysis

Sort_1

Stability:

Here I conduct a stability test. Here is the test data.

From the document we can find out that the 'A' is in order as the line increase. Then we use sort 1 to sort it for 10 times to see if  'A' are still in their right order. Here is the data after testing.

Obviously, the order of 'A' is stable. Thus, sort 1 is stability.

Time complexity:

I have tested 10 sets of data on sort_1 to get the time complexity. The time result is shown on the follow form. Each data is in 10 length.

According to these figure, I work out the curve graph as follow.

Firstly, from the curve graph we can find out that the sort should be a linear sort in all cases. The growth rate of sort 1 is relative to n. Therefore, we assume that it can be Radix Sort(LSD,MSD) or Counting Sort. 

Secondly, I want to identify if it is a Counting Sort. So I changed the length in one line, and left the other lines as it was. After my 5 times tests, the result is as planned. The time complexity changed sharply. And this feature just met the Counting Sort's feature. 

Finally, I identify Sort 1 is a Counting Sort!

Sort_2

Stability:

Here I use the same stability test as sort 1. Here is the test data.

Then we use sort 2 to sort it for 10 times to see if  'A' are still in their right order. Here is the data after testing.

Obviously, the order of 'A' is stable. Thus, sort 2 is stability.

Time complexity:

I have tested 10 sets of data on sort_2 to get the time complexity. The time result is shown on the follow form. Each data is in 10 length.

According to these figure, I work out the curve graph as follow.

Firstly, from the curve graph we can find out that the sort has both linear sort and curved sort. 

Secondly, as it is stability. I test if it is a Bucket Sort. I create a 10000 lines test data in 10 length, and all of these strings are have the same first letter. I also create a 10000 lines test data in 10 length, but all of these strings are have different first letters. Then I just test these two datas' time complexity, and the result is extraodinary different. Afterwards, I tested 3 times as the same way but with different lines. The results are as predicted. The time complexity is sharply different concerning the first letter. This result met Bucket Sort's feature.

Finally, I identify Sort 2 is a Bucket Sort!

Sort_3

Stability:

 Here is the test data.

From the document we can find out that the 'A' is in order as the line increase. Then we use sort 1 to sort it for 10 times to see if  'A' are still in their right order. Here is the data after testing.

Obviously, the order of 'A' is stable. Thus, sort 3 is stability.

Time complexity:

I have tested 10 sets of data on sort_3 to get the time complexity. The time result is shown on the follow form. Each data is in 10 length.

According to these figure, I work out the curve graph as follow.

Firstly, according to the curve graph the growth rate of sort 3 cannot be relative to n^2. As it is stability, it could just be Merge Sort, which is close to nlogn.

Secondly, I did one more test to identify if it is Merge Sort. I compared two test data, one is 100,000 lines with 10 in length, another is 100,000 lines with 100 in length. Which means, the lines are the same, and the length are different. As predicted, the time complexity is almost the same. It is known that the length does not influence the result in Merge Sort.

Finally,  I identify Sort 3 is a Merge Sort!

Sort_4

Here is the test data.

In this sort, there is no output in both random and worst cases. The time complexity in best case is more less than 0.1 second. Obviously, it is a Bogo Sort!

Conclusion

Sort_1 is a Counting Sort.

Sort_2 is a Bucket Sort.

Sort_3 is a Merge Sort.

Sort_4 is a Bogo Sort.