Page 177 - ARM 64 Bit Assembly Language

164 Chapter 6

The header file and the main program file would not require any changes. The header file pro-
vides function prototypes that the C compiler uses to determine how parameters should be
passed to the functions. As long as our new assembly function conforms to its C header defi-
nition, the program will work correctly.

6.2.1 Sorting by word frequency
The linked list is created in alphabetical order, but the wl_print_numerical function is re-
quired to print it sorted in reverse order of number of occurrences. There are several ways in
which this could be accomplished, with varying levels of efficiency. Possible approaches in-
clude, but are not limited to:
• Re-ordering the linked list using an insertion sort. This approach creates a complete new
list by removing each item, one at a time, from the original list, and inserting it into a
new list sorted by the number of occurrences rather than the words themselves. The time
2
complexity for this approach would be O(N ), but would require no additional storage.
However, if the list were later needed in alphabetical order, or any more words were to be
added, then it would need to be re-sorted in the original order.
• Sorting the linked list, using a merge sort algorithm. Merge sort is one of the most effi-
cient sorting algorithms known, and can be efficiently applied to data in files and linked
lists. The merge sort works as follows:
1. The sub-list size, i,isset to 1.
2. The list is divided into sub-lists, each containing i elements. Each sub-list is assumed
to be sorted. (A sub-list of length one is sorted by definition.)
3. The sub-lists are merged together to create a list of sub-lists of size 2i, where each
sub-list is sorted.
4. The sub-list size, i is set to 2i.
5. The process is repeated from step 2 until i ≥ N,where N is the number of items to be
sorted.
The time complexity for the merge sort algorithm is O(N logN), which is far more ef-
ficient than the insertion sort. This approach would also require no additional storage.
However, if the list were later needed in alphabetical order, or any more words were to be
added, then it would need to be re-sorted in the original alphabetical order.
• Create an index, and sort the index rather than rebuilding the list. Since the number of
elements in the list is known, we can allocate an array of pointers. Each pointer in the
array is then initialized to point to one element in the linked list. The array forms an in-
dex, and the pointers in the array can be re-sorted in any desired order, using any common
2
2
sorting method such as bubble sort (O(N )), in-place insertion sort (O(N )), quick sort
(O(N logN)), or others. This approach requires additional storage, but has the advantage
that it does not modify the original linked list.