Sorting as Searching

Part-A In sorting, given a set of items, the objective is to arrange them in a particular order. In the case of numbers, we generally sort them in ascending or descending order. In this assignment, you need to sort a given set of numbers in ascending order using a search algorithm. State: A comma-separated list of numbers Successor function: Swap any two neighboring numbers Goal test/state: A comma-separated list of numbers sorted in ascending order For each action, your code should print the current state. The input to the code will be a number n followed by n numbers. The final output of the code will be the path taken from the start state to the goal state in case of uninformed and informed search methods, and the final state in case of local (hill-climbing) search method. Example input: 4 4 6.3 9 -3 For the above input, the start state will be {4,6.3,9,-3} and the goal state will be {-3,4,6.3,9}. Examine the following search algorithms: (1) BFS (2) DFS (3) UCS (4) Greedy search using an appropriate heuristic function of your choice (5) A* search using the same heuristic function used in Greedy search (6) Hill-climbing search using an appropriate heuristic function of your choice Note: The (interpretation of) heuristic function used in 4 and 5 is different from that in 6.

Part-B Run each of the above algorithms at least 20 times for different values of n in {3,4,5} by randomly generating different inputs (start states) with that many numbers, and calculate the average number of nodes explored by each algorithm for each value of n.