The purpose of this lab is to help reinforce sorting algorithms in C++. Specific
ID: 3721521 • Letter: T
Question
The purpose of this lab is to help reinforce sorting algorithms in C++. Specifically, the lab is to problem 10 page 681 of the text.
Please refer the example of Radix sort (Lab 11):
Input: 1, 7, 4, 0, 9, 4, 8, 8, 2, 4 (Since 9 is the largest number, Radix sort needs 4 iterations of 1, 2, 4, 8)
divisor: 1
list1: 1, 7, 9 (Odd numbers)
list0: 4, 0, 4, 8, 8, 2, 4 (Even numbers)
l: 4, 0, 4, 8, 8, 2, 4, 1, 7, 9 (Merge list1 and list0, list0 comes first)
divisor: 2
list1: 2, 7 (Odd numbers after dividing by 2)
list0: 4, 0, 4, 8, 8, 4, 1, 9 (Even numbers after dividing by 2)
l: 4, 0, 4, 8, 8, 4, 1, 9, 2, 7 (Merged list)
divisor: 4
list1: 4, 4, 4, 7 (Odd numbers after dividing by 4)
list0: 0, 8, 8, 1, 9, 2 (Odd numbers after dividing by 4)
l: 0, 8, 8, 1, 9, 2, 4, 4, 4, 7 (Merged list)
divisor: 8
list1: 8, 8, 9 (Odd numbers after dividing by 8)
list0: 0, 1, 2, 4, 4, 4, 7 (Odd numbers after dividing by 8)
l: 0, 1, 2, 4, 4, 4, 7, 8, 8, 9 (Merged list)
Output: 0, 1, 2, 4, 4, 4, 7, 8, 8, 9
A radix sort is a technique for sorting unsigned integers (or other data that has individual characters or digits) One version of radix sort works with a linked list of unsigned integers. In addition to the list that is be- ing sorted, there are two extra lists called list0 and listl The algorithm begins by going through the list of elements to be sorted; every even number is trans- ferred from the original list to the tail of list0, and every odd number is transferred to the tail of listl (If you are using the STL list class, you may re- move an item from the head of a list with the pop front member function, and you may add a new node to the tail of a list with push_back) After all numbers have been processed, put the two lists together (with list0 in front and list at the back) and then put the whole thing back in the original list. With the STL list class, this can be done in constant time with two splice statements shown here: splice(original.begin, 1istl); splice original.begin, list0); In this code, original is the original list (that is empty before the two splices because we moved ev- erything to list0 andlistl). The process of separating and splicing is repeat ed a second time, but now we separate based on the boolean expression ((n/2) % 2-0). And then we separate and splice using ((n/4) % 2-0) And so on with larger and larger divisors 8, 16 2,... The process stops when the divisor is bigger than the largest number in the list. Here is one way to implement the algorithm:Explanation / Answer
Output:
-802 -90 2 24 45 66 75 170
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.