Python代做编程辅导:ECM1414 Data Structures and Algorithms
2023-06-13 09:14:14 时间
全文链接:tecdat.cn/?p=29696
Introduction
Insert Sort和Merge Sort是排序算法中两个最基础的算法,虽然实际中很难用到,但是作为排序的启蒙还是不错的。 此次要求写出Insert Sort和Merge Sort,并根据随机输入对比两个算法的时间复杂度。分别在最好和最坏以及平均的情况下,通过不同数据量的输入进行对比实验。
Requirement
In this exercise you will implement two sorting algorithms and compare their computational complexities, as measured by the number of comparisons, expressed as a function of the length of the list being sorted.
- Implement the following (see lecture notes for guidance): lessThan(x, y), which performs a standard comparison operation (using “x < y”) and increases the global number of comparisons by 1. You should use this function instead of x < y in the following functions so that you have an easy way of counting comparison operations for the complexity analyses. insert(item, list), which uses the straight (linear) insertion method to insert an element item into a sorted list list. insertSort(list), which sorts a list list by insertion, using the insert function. split(list, list, list), which splits a list in the middle into two (see lecture notes for the detailed description). merge(list, list), which merges two sorted lists, and return the merged list. mergeSort(list), which sorts a list by recursive merging. randomList(n), which generates a list of random integers, of length n specified by the user (the integers should be in the range [-10n, +10n]).
- Use these procedures to write a function listdemo(n), which demonstrates the above functions by generating a random list of length n, sorting it by both insertSort and mergeSort, and printing the original unsorted list and the number of comparisons made in each case. In your hard-copy submission you should include print-outs of four runs of listdemo(n), with n = 25, 50, 75, 100.
- Now for n = 200, 400, 600, 800, 1000 generate 5 random lists of length n and tabulate the number of comparisons made in sorting each list both by insertSort and by mergeSort. Plot these results in a graph, clearly distinguishing between data for insertSort and data for mergeSort (e.g., using different symbols or colours). Your graph should have n, the length of the list, plotted along the horizontal axis, and the number of comparisons plotted along the vertical axis. In the same graph, for each n, plot the number of comparisons for sorting (a) the already sorted list [1, 2, 3, … , n], and (b) the reverse-sorted list [n, n - 1, … , 2, 1], using both sorting methods.
- Assuming that the average-case and worst-case complexity functions of the two sorting algorithms are of the form an2 (linear insert sort) and bn log2 n (merge sort) respectively, use your data to form empirical estimates of the coefficients a and b. To this end, you may and it helpful to tabulate the values of cn=n2 and cn=(n log2 n), where cn is the number of comparisons. Also use your data to form a hypothesis about the best-case complexities for the two algorithms.
- Comment on your results, with reference to the theoretical complexity analyses of the algorithms used, best and worst cases, and the choice of complexity measure. To what extent is the theory borne out in practice? What have you learnt from this exercise that will be useful in future?
相关文章
- 浙江新增python编程_9月起,浙江省八年级新增Python编程课,未来编程是处理大数据的手段…「建议收藏」
- python编程是啥-Python编程「建议收藏」
- 哪些软件是python编写出来的_用Python编程需要什么软件?
- python人工智能学习笔记_[Python] 人工智能与自然语言处理学习笔记(1)[通俗易懂]
- python 和 java 到底该学哪个?
- 神经网络学习笔记1——BP神经网络原理到编程实现(matlab,python)[通俗易懂]
- 多进程 python_python课程
- python requests json开发者人员工具实现窃取api接口调用
- 【说站】python套接字编程的服务器和客户端
- Python 中的面向接口编程
- Python Django 编程 | 连载 03 - Django 视图
- python 图像处理库_Python图像处理库
- python绘制条形柱状图_Python柱状图
- 「Python实用秘技13」Python中临时文件的妙用
- (十)Python网络编程
- python入门之后须掌握的知识点(模块化编程、时间模块)【一】
- Python基础(十五):推导式的讲解
- python多进程编程-多进程编程中的异常处理(二)
- python-Python与SQLite数据库-处理SQLite查询结果(二)
- python性能测试脚本详解编程语言
- 掌握Linux环境下的Python编程(linux执行python)
- 在Linux上学习Python——你的编程之路(linux学python)
- Python实现MySQL数据库的读取(python读取mysql)
- 实例讲解python函数式编程
- 零基础写python爬虫之爬虫的定义及URL构成
- Python常用列表数据结构小结
- python网络编程实例简析