这是一篇来自美国的关于计在链表上实现一个快速排序算法的编程代写
1 Project Description
The goal of the project is to write a program that implements a quick sorting algorithm on a linked list in the LEGv8 assembly language. Overall, the program will import an array of data and create a singly linked list based on its values. Then the array will be printed in its unsorted state, after which the array will be sorted and reprinted in ascending order. You must use project starter code.s provided in the course canvas as the template file. Notice the implementation of our code is a bit different from normal quick sort. Hence, the runtime of our implementation isn’t nlogn. The reason is to let you practice writing the assembly of double recursive functions. Your goal is to translate C code in the following pages to LEGv8 assembly.
A linked list is a chain of nodes, much akin to a string of pearls on a necklace. Figure 1 shows an example of a singly-linked list. Each node has at least two elements: first, an element that stores the data value, and, second, an element that stores the address of the next node in the list. The head of a linked list is the first node in said list and the tail of a linked list is the last node (see: figure 2). Given the tail does not have a next node, it points instead to NULL, which is defined as the number zero. One can only progress from the head of a singly-linked list to its tail. This project will use a singly-linked list, although the use of linked lists is not a prerequisite to implement the quick sort algorithm.
Figure 1: Singly-linked list. Numbers entered by the user are: 12, 99, 37
Figure 2: Singly-linked list with a single node. The value at that node is 37 and the node pointer is null, i.e., it does not point to another node. In programming, a null pointer typically is one that is set to 0.
2 Quick Sort Algorithm Description
The overview of a quick sort algorithm is conceptually simple:
- Get the end node of the input list. We will consider the value of this node the “pivot” value.
- Partition the input list based on the pivot value so that nodes on the left side have values less than the pivot value and nodes to the right side have value greater or equal to the pivot value. The boundary between left and right is not in the middle. It is computed and retained for next steps.
- Recursively call quick sort on the left and right sub-lists, respectively. Use the boundary computed in the previous step to distinguish left and right.
- Return the now-sorted list to the calling function.
The recursive quick sort will keep dividing the sub-list until the sub-list holds a single element. A single element sub-list (the base case) is inherently sorted. It is highly recommended that you read over the description of a quick sort on quick sort on Wikipedia (it’s a very good overview), and graphical view of the sort at: www.sorting-algorithms.com/quick-sort.
Your project must use the provided template file. While you are free to add any further helper functions, your code must implement the following functions according to specification given below.
Interoperability. The grader should be able to remove any of these functions (and any nonessential helper functions it may use) from your code and use it in another person’s programming assignment without issue (i.e. do not change the register names passed to functions).
3 Implementation
In this project, you have to write six functions, namely SwapNodeValue, GetLastNode,GetNodeWithVal, Parition, QuickSort, and QuickSortWrapper to implement the quick sort algorithm in the LEGv8 assembly language. Some details to note:
- Use the procedures prototype as mentioned below and given to you in the template. Don’t change the registers or the arguments passed to the procedures or the values returned.
- Follow the “Procedure Call Convention” for calling procedures, passing registers and managing the stack. The procedures should not make any assumptions about the implementation of other procedures, except for the name of input/output registers (as indicated below) and the conventions mentioned in the course. A code that works correctly but does not follow conventions will be penalized.
- We expect your code to be well-commented. Each instruction should be commented with a meaningful description of the operation. For example, this comment is bad as it tells you nothing:
// x1 gets x2 – 1
sub x1, x2, #1
A good comment should explain the meaning behind the instruction. A better example would be:
// Initialize loop counter x1 to n-1
sub x1, x2, #1
In this project we use the following c-like structure to implement linked-list nodes:
struct Node {
__int64 data; // the numeric value held in this node
Node* next; // address of the next node (0 for NULL)
};
In the following pesudo-codes, we will also use some c-like notations.
For a node with memory address p:
- p→data: The integer value stored in memory address p
- p→next: The memory address of the next element stored in memory address p+8
In other words, if p is stored in x0, then you can get p→value in x11 and p→next in x12 using the following instructions:
LDUR x11, [x0, #0]
LDUR x12, [x0, #8]
程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: itcsdx@outlook.com 微信:itcsdx
如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。
