#include <bits/stdc++.h>

using namespace std;

  

// Queue elements after sortedIndex are 

// already sorted. This function returns

// index of minimum element from front to

// sortedIndex

int minIndex(queue<int> &q, int sortedIndex)

{

    int min_index = -1;

    int min_val = INT_MAX;

    int n = q.size();

    for (int i=0; i<n; i++)

    {

        int curr = q.front();

        q.pop();  // This is dequeue() in C++ STL

  

        // we add the condition i <= sortedIndex

        // because we don't want to traverse

        // on the sorted part of the queue,

        // which is the right part.

        if (curr <= min_val && i <= sortedIndex)

        {

            min_index = i;

            min_val = curr;

        }

        q.push(curr);  // This is enqueue() in 

                       // C++ STL

    }

    return min_index;

}

  

// Moves given minimum element to rear of 

// queue

void insertMinToRear(queue<int> &q, int min_index)

{

    int min_val;

    int n = q.size();

    for (int i = 0; i < n; i++)

    {

        int curr = q.front();

        q.pop();

        if (i != min_index)

            q.push(curr);

        else

            min_val = curr;

    }

    q.push(min_val);

}

  

void sortQueue(queue<int> &q)

{

    for (int i = 1; i <= q.size(); i++)

    {

        int min_index = minIndex(q, q.size() - i);

        insertMinToRear(q, min_index);

    }

}

  

// driver code

int main()

{

  queue<int> q;

  q.push(30);

  q.push(11);

  q.push(15);

  q.push(4);

    

  // Sort queue

  sortQueue(q);

    

  // Print sorted queue

  while (q.empty() == false)

  {

     cout << q.front() << " ";

     q.pop();

  }

  cout << endl;

  return 0;

}