Sorting Algorithms

Fall 2020 COSC 5313

Analysis of Algorithms Assignment 5

Due: 23:59:00, 09/27/2020

1. Please use counting sort to sort the following array: [2 5 2 3 5 5 5 0 2 1 6] (30 points)

2. Given the following list of positive integers, use radix sort to sort them in an increasing order: 439 45 234 91 649 932 47 829 48 732 843 236 727 462 828 999 619

503 290 83 439 545 9 475 683 889 (30 points)

3. Suppose that we have a stack of characters, denoted by S, and a queue of characters, denoted by Q. We also assume that we execute the following code for

each data structure separately:

Insert(‘C’);

Insert(‘b’);

Insert(‘A’);

x = Delete();

Insert(‘d’);

y = Delete();

z = Delete();

What are the values of x, y, and z for each data structure S and Q, respectively?

Please show the intermediate steps. (40 points)