Question

Implement the selection sort algorithm on a Queue of long-type items. Specifically, you are given the Queue class implementation and you need to write a method that takes a Queue and sorts it using the selection sort idea. The implementation of the Queue class for long data type is given in the lecture slides (the code skeleton including the implementation of the Queue class is provided below for your convenience). You should go over the Queue and use enqueue(), dequeue(), peek(),... methods to sort the items in the Queue.

You must work with the queue, that means you are not allowed to convert the Queue into an array (or some other data structure) and then sort the array. Also, you should write the sorting part that means you cannot call a library sort method on the Queue.

your file to be submitted to Gradescope should be named HW04P2.java.

    

import java.util.NoSuchElementException;

class Queue

{

    private int maxSize;

    private long[] queArray;

    private int front;

    private int rear;

    private int nItems;

    //--------------------------------------------------------------

    public Queue(int s) // constructor

    {

        maxSize = s;

        queArray = new long[maxSize];

        front = 0;

        rear = -1;

        nItems = 0;

    }

    //----------------------------------------------------------------

    public long dequeue() // take item from front of queue

    {

        if (isEmpty())

            throw new NoSuchElementException("Queue is empty");

        long temp = queArray[front++]; // get value and increment front

        if(front == maxSize) // deal with wraparound

            front = 0;

        nItems--; // one less item

        return temp;

    }

    //----------------------------------------------------------------

    public void enqueue(long j) // put item at rear of queue

    {

        if (isFull())

            throw new IllegalStateException("Queue is full");

        if(rear == maxSize-1) // deal with wraparound

            rear = -1;

        queArray[++rear] = j; // increment rear and insert

        nItems++; // one more item

    }

    //--------------------------------------------------------------

    public long peek() // peek at front of queue

    {

        if (isEmpty())

            throw new NoSuchElementException("Queue is empty");

        return queArray[front];

    }

    //--------------------------------------------------------------

    public boolean isEmpty() // true if queue is empty

    {

        return (nItems==0);

    }

    //--------------------------------------------------------------

    public boolean isFull() // true if queue is full

    {

        return (nItems==maxSize);

    }

    //--------------------------------------------------------------

    public int size() // number of items in queue

    {

        return nItems;

    }

    //--------------------------------------------------------------

    public void display()

    {

        System.out.println("************ printing queue ************");

        for(int i=0; i<nItems; i++) {

            long temp = dequeue();

            System.out.println(temp);

            enqueue(temp);

        }

        System.out.println("************ Done ************");

    }

}

public class HW04P2

{

    public static void selectionSortQ(Queue myQ)

    {

        //your implementation

    }

}

Answer 1

    public static void selectionSortQ(Queue  myQ) 
    { 
        for(int i = 1; i <= myQ.size(); i++) 
        { 
            
            int min_index = findMinIndex(myQ,myQ.size() - i); //t o get index of minimum number 
            insertMinToRear(myQ, min_index); // to insert minimum element to end to end of queue
        } 
    } 
    
    public static int findMinIndex(Queue q, 
                                     int sortIndex) 
    { 
        //this function will return index of smallest element of queue
        int min_index = -1; 
        long min_value = Integer.MAX_VALUE; 
        int size = q.size();
        for (int i = 0; i < size; i++) 
        { 
            long current = q.dequeue(); 
              
      
            // we need to traverse till sortIndex not beyond it 
            if (current <= min_value && i <= sortIndex) 
            { 
                min_index = i; 
                min_value = current; 
            } 
            q.enqueue(current);  
        } 
        //return index of minimum element
        return min_index; 
    }
    public static void insertMinToRear(Queue q ,
                                             int min_index) 
     { 
         //function to insert minimum element to end of Queue
         // dequeue element from queue and if it is not minimum then enqueue it else 
         // after going through all element then enqueue it so that we make sure  order is followed
        long min_value = 0;  
        int size = q.size(); 
        for (int i = 0; i < size; i++) 
        { 
            long current = q.dequeue(); 
            if (i != min_index) 
                q.enqueue(current); //enqueue dequeued element for all non minimum elements
            else
                min_value = current; //store min index element
        } 
            // enqueue minimum element  after checking all elements of queue
            q.enqueue(min_value); 
    } 

necessary comment are provided in code

idea is find smallest element of queue and insert at end.

repeat this for remaining part of queue.

ex: let queue be  1 5 4 2

1) min index =0

after inserting 1 : 5 4 2 1

2) min index =2

after inserting 2 : 5 4 1 2

3) min index = 1

after inserting 4 : 5 1 2 4

4) min index =0

after inserting 2 : 1 2 4 5