Question

Write me some pseudocode for one pass of the SelectionSort algorithm through random values stored in an Unordered-List, or Linked-List, of values (rather than a standard "Python" List).

How would you implement a swap using a Linked-List?

What is the minimum number of variables required?

Step me through an illustrated example (including all needed variables/arrows) of a Linked-List of size 5, where the positions of nodes 3 and 4 are swapped.

Show the pseudocode to accomplish this in your report

Answer 1

The Algorithm for selection sort is given below:

1) If Linked list is empty then make the node as

head and return it.

2) If the value of the node to be inserted is smaller

than the value of the head node, then insert the node

at the start and make it head.

3) In a loop, find the appropriate node after

which the input node is to be inserted.

To find the appropriate node start from the head,

keep moving until you reach a node who's value is greater than

the input node. The node just before given node is the

appropriate .

4) Insert the node after the appropriate node

found in step 3

Swap can be implemented using LInked-List by multiple assignment as shown.

The minimum number of variables required is 2.

An example is given below

your_list = ["a", "b", "c", "d", "e"]

your_list[3], your_list[4] = your_list[4], your_list[3]

print(your_list)

OUTPUT

['a', 'b', 'd', 'c', 'e']