Python: selectionsort algorithm with queues

Question

I have come across an exercise in Python:

1. Read in some strings and put them into a queue
2. Sort the strings lexicographically into a new queue, but the original queue shouldn't be changed. I should write a function from scratch (e.g. the sorted function cannot be used)
3. The use of arrays is not allowed

I think I have managed to come up with a function for step 1, but I have been struggling with step 2 for hours. I would really appreciate any kind of help!

Here is my code snippet for step 1:

q1 = []

def DisplayQueue(queue):
    for Item in queue:
        print(Item)

def PushQueue(queue):
    x = True
    while x:
        user_input = input("Please enter a string (for exit type: exit): ")
        if user_input == "exit":
            x = False
        else:
           queue.append(user_input)
    return queue

queue = PushQueue(q1)

Answer 1

Sorting can be done in many ways (bubble sort, insert sort, quick sort radix sort), but I recommend you start with something simple, although not the fastest.

1. Create a queue (or list) to store the answer in.
2. Find the smallest element in the old data list. *
3. Remove that element from the old list. **
4. Add than element to the answer list.
5. Repeat from step 2 (if the data list is not empty).

The data list will get shorter and shorter for each turn, and the elements will be added in increasing order to the answer list.

*) To find the smallest element in the data list (you could put that in a separate function), keep the value of the currently smallest value in a variable called x or something, and go through the data items one by one. If the data item is smaller than what you have in the variable x, then put the value of that data item into x.

Now, once you have gone through the whole data list, your variable x will contain the value of the smallest element in the list.

**) You can remove a value v from a list x with x.remove(v). It just removes the first occurence of that value.