In addition to what has been covered in previous assignments, the use of the fol

Question

In addition to what has been covered in previous assignments, the use of the following items, discussed in class, will probably be needed:

Queues

In this assignment, you are going to implement a sorting algorithm using queues by completing the Sorting class.

It has the following attributes:

Attribute name

Attribute type

Description

mainQueue

LinkedList

Main-Queue to be used to show intermediate stage of the sorting

subQueues

Array of LinkedLists

An array of queues to be used for the sorting

SIZE

Constant integer

It is used to create an array of Linked List subQueues as its size.

maxDigits

int

The maximum number of digits. It should be initialized to 0.

The following public methods should be provided to interact with the Assignment11.java file.

Method

Description

Sorting()

A Constructor of the Sorting class. The mainQueue and subQueues are instantiated and maxDigits is initialized to 0.

void addToMainQueue(Integer num)

The addToMainQueue method checks the number of digits of the positive integer parameter "num", and if it is larger than the current value in "maxDigits", it updates its value to the number of digits of "num". The method also enqueues "num" to the main-queue.

String listMainQueue()

The listMaintQueue method returns a string containing the content of the main-queue. (This method is already provided by the instructor)

String listSubQueues()

The listSubQueues method returns a string containing the content of the sub-queues (This method is already provided by the instructor)

String listQueue(LinkedList queue)

The listQueue method returns a string containing the content of the parameter queue (This method is already provided by the instructor)

void sortNumbers()

The sortNumbers method sorts numbers in the main queue.

You will need to complete the three method, Sorting( ), addToMainQueue(Integer num), and sortNumbers().

Here is a detailed algorithm for this assignment:

1. Create 10 queues called SubQueues[0], SubQueues[1],, SubQueues[9]in the constructor Sorting( )

2. In the sortNumbers( ) method, remove a number from the mainQueue and extract its right most digit (every number in the queue will be a positive integer) This digit will be called digit.

3. Enqueue the number mentioned in (2) to the SubQueue[digit].

4. Repeat above step (2) and step (3) until mainQueue becomes empty. Note that the step (2) needs to be repeated for the 2nd from the right most digit for the second time. Thus, the step (2) can be re-written as: remove a number from the mainQueue and extract its i-th right most digit where i starts with 1 and is incremented every iteration of the loop (the loop specified in the step (10)) .

5. Print the subQueues (This code is already in the sortNumbers( ) method)

6. Remove (dequeue) the first element from the subQueues[0] and insert (enqueue) it into the mainQueue.

7. Repeat step (6) until the subQueues[0] is empty.

8. Do similar operation for the steps 6-7 on subQueues[i], where i takes value from 1 to 9.

9. Print the mainQueue (This code is already in the sortNumbers( ) method)

10. Repeat the procedure starting from step (2) to step (9) maxDigits times where the value of maxDigits is equal to the number of digits in the largest number of the sequence.

Example: An application of the queue data structure to sort numbers using the sort.

mainQueue = { 539 264 372 424 419 129 322 544 367 }

subQueues[0] : { }

subQueues[1] : { }

subQueues[2] : { 372 322 }

subQueues[3] : { }

subQueues[4] : { 264 424 544 }

subQueues[5] : { }

subQueues[6] : { }

subQueues[7] : { 367 }

subQueues[8] : { }

subQueues[9] : { 539 419 129 }

The first pass of the sort is focusing on the right most digit. After above step, the mainQueue is:

mainQueue = { 372 322 264 424 544 367 539 419 129 }

The second pass of the sort is focusing on the second digit from the right (tens):

subQueues[0] : { }

subQueues[1] : { 419 }

subQueues[2] : { 322 424 129 }

subQueues[3] : { 539 }

subQueues[4] : { 544 }

subQueues[5] : { }

subQueues[6] : { 264 367 }

subQueues[7] : { 372 }

subQueues[8] : { }

subQueues[9] : { }

After above step, now the mainQueue is:

mainQueue = { 419 322 424 129 539 544 264 367 372 }

The third pass of the sort is focusing on the third digit from the right (hundreds):

subQueues[0] : { }

subQueues[1] : { 129 }

subQueues[2] : { 264 }

subQueues[3] : { 322 367 372 }

subQueues[4] : { 419 424 }

subQueues[5] : { 539 544 }

subQueues[6] : { }

subQueues[7] : { }

subQueues[8] : { }

subQueues[9] : { }

After above step, now the mainQueue is sorted and mainQueue is:

mainQueue = { 129 264 322 367 372 419 424 539 544 }

Requirements:

You need to implement this method using an object of the LinkedList class in java.util package as queues (The LinkedList class implements the Queue interface). One way to utilize it is to treat it as a queue of Integer objects. The Integer class is a wrapper class for the primitive data type "int". If you use the compiler version 5 or above, you can use Auto-boxing for automatic conversion between a primitive data int and an object of the Integer class. (You can assign an int value to an Integer object or vice versa, and they are automatically converted.)

To manually convert between them, you can make use of some methods in the Integer class such as:

valueOf() method (an example below to convert an int 5 to an object)
Integer obj = Integer.valueOf(5);

intValue() method (an example below to convert an Integer object to a primitive data type int)

int num1 = obj.intValue();

Attribute name

Attribute type

Description

mainQueue

LinkedList

Main-Queue to be used to show intermediate stage of the sorting

subQueues

Array of LinkedLists

An array of queues to be used for the sorting

SIZE

Constant integer

It is used to create an array of Linked List subQueues as its size.

maxDigits

int

The maximum number of digits. It should be initialized to 0.

You need to complete the constructor Sorting(), addToMainQueue(), and sortNumber()methods

Explanation / Answer

contact me on mail for code

output 3

Choice Action

------ ------

A Add An Integer

L List Numbers

Q Quit

S Sort Numbers

? Display Help

What action would you like to perform?

a

Please enter an integer to add:

52

number added

What action would you like to perform?

a

Please enter an integer to add:

1264

number added

What action would you like to perform?

a

Please enter an integer to add:

675

number added

What action would you like to perform?

a

Please enter an integer to add:

124

number added

What action would you like to perform?

a

Please enter an integer to add:

541

number added

What action would you like to perform?

a

Please enter an integer to add:

43129

number added

What action would you like to perform?

a

Please enter an integer to add:

32

number added

What action would you like to perform?

a

Please enter an integer to add:

5441

number added

What action would you like to perform?

l

mainQueue = { 52 1264 675 124 541 43129 32 5441 }

What action would you like to perform?

s

5

Character position1

Digit is 2

Character position3

Digit is 4

Character position2

Digit is 5

Character position2

Digit is 4

Character position2

Digit is 1

Character position4

Digit is 9

Character position1

Digit is 2

Character position3

Digit is 1

subQueue[0]:{ }

subQueue[1]:{ 541 5441 }

subQueue[2]:{ 52 32 }

subQueue[3]:{ }

subQueue[4]:{ 1264 124 }

subQueue[5]:{ 675 }

subQueue[6]:{ }

subQueue[7]:{ }

subQueue[8]:{ }

subQueue[9]:{ 43129 }

mainQueue = { 541 5441 52 32 1264 124 675 43129 }

Character position1

Digit is 4

Character position2

Digit is 4

Character position0

Digit is 5

Character position0

Digit is 3

Character position2

Digit is 6

Character position1

Digit is 2

Character position1

Digit is 7

Character position3

Digit is 2

subQueue[0]:{ }

subQueue[1]:{ }

subQueue[2]:{ 124 43129 }

subQueue[3]:{ 32 }

subQueue[4]:{ 541 5441 }

subQueue[5]:{ 52 }

subQueue[6]:{ 1264 }

subQueue[7]:{ 675 }

subQueue[8]:{ }

subQueue[9]:{ }

mainQueue = { 124 43129 32 541 5441 52 1264 675 }

Character position0

Digit is 1

Character position2

Digit is 1

Character position0

Digit is 5

Character position1

Digit is 4

Character position1

Digit is 2

Character position0

Digit is 6

subQueue[0]:{ 32 52 }

subQueue[1]:{ 124 43129 }

subQueue[2]:{ 1264 }

subQueue[3]:{ }

subQueue[4]:{ 5441 }

subQueue[5]:{ 541 }

subQueue[6]:{ 675 }

subQueue[7]:{ }

subQueue[8]:{ }

subQueue[9]:{ }

mainQueue = { 32 52 124 43129 1264 5441 541 675 }

Character position1

Digit is 3

Character position0

Digit is 1

Character position0

Digit is 5

subQueue[0]:{ 32 52 124 541 675 }

subQueue[1]:{ 1264 }

subQueue[2]:{ }

subQueue[3]:{ 43129 }

subQueue[4]:{ }

subQueue[5]:{ 5441 }

subQueue[6]:{ }

subQueue[7]:{ }

subQueue[8]:{ }

subQueue[9]:{ }

mainQueue = { 32 52 124 541 675 1264 43129 5441 }

Character position0

Digit is 4

subQueue[0]:{ 32 52 124 541 675 1264 5441 }

subQueue[1]:{ }

subQueue[2]:{ }

subQueue[3]:{ }

subQueue[4]:{ 43129 }

subQueue[5]:{ }

subQueue[6]:{ }

subQueue[7]:{ }

subQueue[8]:{ }

subQueue[9]:{ }

mainQueue = { 32 52 124 541 675 1264 5441 43129 }

numbers sorted

What action would you like to perform?

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.