Introduction需求分析：基于链表的队列伪代码基于链表的堆栈伪代码使用伪元素的基于链表的队列伪代码堆，快速排序，更多排序和算法分析1.（10分）第3章显示了使用链表实现Queue的伪代码。假设有一个固定的优先级范围，比如1··n。（a）（3分）使用链表实现的队列，对给定的优先级范围实施优先级排序。（提示：你可以使用多个队列。）（b）（3分）使用上面的答案编写Insert（elem，优先级）的伪代码。（c）（4分）在上面的答案中显示Insert（elem，优先级）的时间复杂度。解释您的答案。2 .（10分）教科书中的Quicksort将列表分为两个子列表和关键点，想象一下，您将得到一个配分函数，将列表分为三个子列表和两个支点pivot1和pivot2。最左边的子列表只包含小于或等于pivot1的元素。中间子列表包含大于pivot1且小于或等于pivot2的元素。 例如，如果输入数组为{5,3,6,9,4,1,2,8}，则分区函数可以将3和6分别选为pivot1和pivot2，并将输入数组分割为[1， 2]，[3]，[5，4]，[6]，[9,8]。（a）（3分）写出使用此新配分函数的Quicksort的伪代码。（b）（3分）写出这个Quicksort的递归关系。（c）（4分）考虑到配分函数以O（n）将输入数组分割为n个项目，使用代入法来显示此Quicksort的时间复杂度为O（n2）。3. （6分）如果排序算法保留了重复元素的顺序，它是稳定的（考虑我们基于关键字段对数组记录进行排序的情况，两个不同的记录可以具有相同的关键字，如果排序是稳定的， 那么对于具有相同键字段的任何两个记录x和y，x将出现在排序列表中的y之前当且仅当x在原始列表中出现在y之前。以下哪种排序算法是稳定的：插入，选择， 冒泡，合并，堆，快速？用教科书中的伪代码来回答这个问题，解释你的答案。4.（8分）在列表中查找最小值和最大值。（a）（4分）给出n个元素的列表，在最坏的情况下给出一个算法来找出列表中最小和最大的元素。在你的算法中需要多少次比较 ñ，在最坏的情况下？请注意，我需要确切的比较次数，而不仅仅是比较次数的O（）边界。（b）（4分）给出n个元素的列表，在最好的情况下给出一个算法来找出列表中最小和最大的元素。在最好的情况下，你的算法需要总是给出正确的答案，但是 您正试图优化最佳性能，而不是最差情况下的性能。 在最好的情况下，您的算法需要多少次比较，以n为单位？在最坏的情况下如何？ 注意我想要确切的比较次数，而不仅仅是比较次数的O（）边界。RequirementDepartment of Computer Science University of San FranciscoComputer Science 245Spring 2018Homework 4 Heap, Quicksort, More sorting, and AlgorithmAnalysisDue Monday, March 5th by 11:59pm on Canvas1. (10 points) Chapter 3 shows the pseudocode that implements Queue using linked list.Assume that there is a fixed range of priorities, say 1···n.(a) (3 points) Implement a priority queue for the given range of priorities using Queueimplemented with linked list. (Hint: you may use multiple Queues.)(b) (3 points) Write pseudocode of Insert(elem, priority) using your answer above.(c) (4 points) Show the time complexity of Insert(elem, priority) in your answer above.Explain your answer.2. (10 points) Quicksort in the textbook partitions a list into two sublists and the pivot.Imagine that you are given a partition function that partitions a list into three sublistsand two pivots, pivot1 and pivot2. The leftmost sublist only contains elements lessthan or eqJava代写Homework Heap, Quicksort, More sorting, and Algorithm代ual to pivot1. The middle sublist contains elements greater than pivot1and less than or equal to pivot2. For example, if the input array is {5, 3, 6, 9, 4, 1, 2,8}, the partition function can pick 3 and 6 to be pivot1 and pivot2 respectively, andpartition the input array into [1, 2], [3], [5, 4], [6], [9, 8].(a) (3 points) Write the pseudocode for Quicksort that uses this new partition func-tion.(b) (3 points) Write the recurrent relation for this Quicksort.(c) (4 points) Given that the partition function takes Θ(n) to partition an input arraywith n items, use the substitution method to show this Quicksort has the timecomplexity of O(n 2 ).3. (6 points) A sorting algorithm is stable if it preserves the order of duplicate elements.(Consider the case where we are sorting an array records based on a key field. Twodifferent records could have the same key. If the sort is stable, then for any two recordsx and y with the same key field, x would appear before y in the sorted list if and onlyif x appeared before y in the original list. Which of the following sorting algorithmsare stable: insertion, selection, bubble, merge, heap, quick? Use the pseudocodes inthe textbook to answer this question. Explain your answer.4. (8 points) Finding the Minimum and Maximum values in a list.(a) (4 points) Given a list of n elements, give an algorithm to find the smallest andlargest elements in the list in the smallest number of comparisons, in the worst1case. How many comparisons does your algorithm require, in terms of n, in theworst case? Note that I want the exact number of comparisons, not just a Θ()bound on the number of comparisons.(b) (4 points) Given a list of n elements, give an algorithm to find the smallest andlargest elements in the list in the smallest number of comparisons, in the bestcase. Your algorithm needs to always give the correct answer, but you are tryingto optimize the best-case performance, not the worst case performance. Howmany comparisons does your algorithm require, in terms of n, in the best case?How about in the worst case? Note I want the exact number of comparisons, notjust a Θ() bound on the number of comparisons.转自：http://ass.3daixie.com/2018052610000131.html