算法基础 上机实验 1 学 期: 2016 (秋).

Presentation on theme: "算法基础 上机实验 1 学 期: 2016 (秋)."— Presentation transcript:

1 算法基础 上机实验 1 学 期: (秋)

2 Project 1: Sorting 实验1：排序 n 个元素，元素为随机生成的长为1..16的字符串（字符串均为英文小写字母），n的取值为：32，34，36，38，310，312； 算法：直接插入排序，堆排序，归并排序，快速排序， SHELL排序（5个增量，分别是：1，3，7，15，21）。 实验2：排序n个元素，元素为随机生成的1到65535之间的整数，n的取值为：33，35，37，39，311，313； 算法：冒泡排序，快速排序，归并排序， 基数排序，计数排序。

3 Project 1: Sorting 字符串大小判断标准： 1.首先按字符串长度进行排序（短字符串在前，长字符串在后）。
2.对长度相同的字符串，按字母顺序进行排序。 如：ab, gdh, c, gaa, caa排序后的结果是：c, ab, caa, gaa, gdh

4 实验要求： 1、实验格式: C)output：
a)实验需建立根文件夹，文件夹名称为：学号-project1，在根文件夹下需包括实验报告、和ex1、ex2两个子文件夹，每个子文件夹又分别包含3个子文件夹： input文件夹：存放输入数据 source文件夹：源程序 output文件夹：输出数据 b)input： 输入文件中每行一个随机数据，总行数大于等于313 顺序读取N个数据，进行排序 example：用插入排序对310个字符串进行排序，其随机数据的输入文件路径为 学号-project1/ex1/input/input_strings.txt，顺序读取前310个字符串进行排序。 C)output： 每种算法建立一个子文件夹，其输出结果数据导出到其对应子文件下面 result_n.txt：排序结果的数据(N为数据规模的指数)，每个数据规模一个输出文件 time.txt：运行时间效率的数据，六个规模的时间结果都写到同个文件 Example：用插入排序对310个字符串进行排序，其排序结果文件路径为 学号-project1/ex1/output/insert_sort/result_10.txt

5 2、性能分析的要求： a)用适当的方法，或工具记录排序算法在执行时所消耗的时间；
b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图；比较你的曲线是否与课本中的算法渐进性能是否相同，若否，为什么，给出分析。 c)比较分析不同的排序算法的时间曲线， 根据你的图表分析各种排序算法在不同输入规模下哪个更占优势，与课本上介绍的算法渐进性能的相符吗？如果不相符，为什么？

6 3、注意事项： a)实验报告中要有必要的实验过程截图和图表； b)图片要有单位，横纵坐标等信息；
c)ex1,ex2目录结构严格按照实验格式的要求； d)代码中需要有必要的注释； e)实验杜绝抄袭他人代码或者实验结果，如发现代码高度相似或者实验报告雷同者算0分； f)实验报告模板另附课程主页上。

7 4、实验提交： a)按实验要求提交源码，输入输出结果，实验报告。
c)如果有同学在截止日期前要重复提交，邮件主题需说明重复提交。 d)第一次实验截止日期：10月31日晚24点，逾期提交实验成绩将作0分处理。