Description

Submission Guidelines :
1. You can code all of them either in Python or Java. But you should choose a specific language for all tasks.
2. For each task write separate python files like task1.py, task2.py and so on.
3. For each problem, take input from files called “inputX.txt”, and output at “outputX.txt”, where X is the task number. So, for problem 2, the input file is basically this, “input2.txt”. Same for output.
4. For each task include the input files (if any) in the submission folder.
5. Finally zip all the files and rename this zip file as per this format :
LabSectionNo_ID_CSE221LabAssignmentNo_Summer2022.zip. [Example :
LabSection01_21101XXX_CSE221LabAssignment02_Summer2022.zip]
6. Don’t copy from your friends
7. You MUST follow all the guidelines, naming/file/zipping convention stated above. Failure to follow instructions will result in straight 50% mark deduction.
Problem Descriptions
The following tasks need to be solved using Sorting Algorithms. Sorting algorithm is an algorithm that is used to arrange data in certain order, i,e- either ascending or descending order. We use sorting algorithms on numerical and lexicographical data to optimize the efficiency of other algorithms. You have learned several sorting algorithms such as bubble sort, insertion sort, selection sort, quick sort,merge sort etc. The problems below are related or similar to some of the sorting algorithms you learned in class. Read the task descriptions carefully and implement the algorithm using either Java or Python. The output format MUST match exactly as shown in each task.
Task : 1 [5 Marks]
Here is code of bubble sort. Its run time complexity is θ(n2). Change the code in a way so that its time complexity is θ(n) for the best case scenario. Find the best case and change the code a little bit. And explain how you did it in a comment block of your code.
def bubbleSort(arr):
for i in range(len(arr)-1):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
swap( arr[j+1], arr[j] )
Input 1:
5
3 2 1 4 5 Input 2:
6
10 20 5 15 25 30
Output 1: 1 2 3 4 5 Output 2:
5 10 15 20 25 30
Task : 2 [5 Marks]
You have a list of elements and their prices. Select your preferred lists from the item based on lowest price. So to complete the task you have a tool called selection sort.
In selection sort:
● Select the minimum element from the unsorted part of the given array.
● Move the selected element to a sorted part of the array. ● Repeat this process to make the unsorted array sorted.
Here is pseudo code:
𝑓𝑜𝑟 𝑖 ← 0 𝑡𝑜 𝑛 − 1
𝑚 = 𝑎𝑟𝑔𝑚𝑖𝑛𝑗 (𝐴[𝑖], 𝐴[𝑖 + 1], . 𝐴[𝑛 − 1])
𝑠𝑤𝑎𝑝 (𝐴[𝑖], 𝐴[𝑚])
𝑒𝑛𝑑 𝑓𝑜𝑟
Use the above pseudo code to complete the selection sort.
First line of the input will contain N items and M preferred choices (where M ≤ N). The next line will contain the price of each element. Output will contain the price of M number of preferred elements.
Input 1:
5 3
5 10 2 1 4 Input 2:
7 4
10 2 3 4 1 100 1
Output 1: 1 2 4 Output 2: 1 1 2 3
Task : 3 [5 Marks]
Suppose you are given a task to rank the students. You have gotten the marks and id of the students. Now your task is to rank the students based on their marks using only insertion sort.
Here is the pseudocode for insertion sort for ascending order. You need to change it for descending order.
𝑓𝑜𝑟 𝑖 ← 0 𝑡𝑜 𝑛 − 1
𝑡𝑒𝑚𝑝 ← 𝐴[𝑖 + 1]
𝑗 = 𝑖
𝑤ℎ𝑖𝑙𝑒 𝑗 >= 0
𝑖𝑓(𝐴[𝑗] > 𝑡𝑒𝑚𝑝)
𝐴[𝑗 + 1] ←𝐴[𝑗]
𝑒𝑙𝑠𝑒
𝑏𝑟𝑒𝑎𝑘
𝑗 = 𝑗 − 1
𝑒𝑛𝑑 𝑓𝑜𝑟
𝐴[𝑗 + 1] ← 𝑡𝑒𝑚𝑝
𝑒𝑛𝑑 𝑓𝑜𝑟
Implement this pseudocode to complete your task.
First line of the input file will contain an integer N. The next line will contain N number of id of the students.The next line will contain the N number of the marks of corresponding students. Output will be ranking the id based on their marks (descending order).
Input 1:
5
11 45 34 22 12
40 50 20 10 10 Input 2:
6
1 2 3 4 5 6
50 60 80 20 10 30
Output 1:
45 11 34 22 12 Output 2:
3 2 1 6 4 5

Task : 4 [5 Marks]
Here is the problem, just simply sorting an array. Now, to sort the array you should use efficient sorting techniques. It will have worst-case time complexity better than the above sorting algorithms. The sorting algorithm pseudocode is given below:
𝑀𝐸𝑅𝐺𝐸 (𝐴, 𝑝, 𝑞, 𝑟 )
𝑛1 ← 𝑞 − 𝑝 + 1
𝑛2 ← 𝑟 − 𝑞
𝐶𝑟𝑒𝑎𝑡𝑒 𝑎𝑟𝑟𝑎𝑦𝑠 𝐿[1 . . 𝑛1 + 1] 𝑎𝑛𝑑 𝑅[1 . . 𝑛2 + 1]
𝐹𝑂𝑅 𝑖 ← 1 𝑡𝑜 𝑛1
𝐷𝑂 𝐿[𝑖] ← 𝐴[𝑝 + 𝑖 − 1]
𝐹𝑂𝑅 𝑗 ← 1 𝑡𝑜 𝑛2
𝐷𝑂 𝑅[𝑗] ← 𝐴[𝑞 + 𝑗 ]
𝐿[𝑛1 + 1] ← ∞
𝑅[𝑛2 + 1] ← ∞
𝑖 ← 1
𝑗 ← 1
𝐹𝑂𝑅 𝑘 ← 𝑝 𝑇𝑂 𝑟
𝐷𝑂 𝐼𝐹 𝐿[𝑖 ] ≤ 𝑅[ 𝑗]
𝑇𝐻𝐸𝑁 𝐴[𝑘] ← 𝐿[𝑖] 𝑖 ← 𝑖 + 1
𝐸𝐿𝑆𝐸 𝐴[𝑘] ← 𝑅[𝑗]
𝑗 ← 𝑗 + 1
𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑝, 𝑟)
𝑖𝑓 𝑝 < 𝑟 // 𝐶ℎ𝑒𝑐𝑘 𝑓𝑜𝑟 𝑏𝑎𝑠𝑒 𝑐𝑎𝑠𝑒
𝑞 = (𝑝 + 𝑟)/2
𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑝, 𝑞)
𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑞 + 1, 𝑟)
𝑀𝐸𝑅𝐺𝐸 (𝐴, 𝑝, 𝑞, 𝑟)
Take help from pseudocode or use your way to complete the task.
First line will contain N . The next line will contain N number of elements. The output will contain a sorted N number of elements (ascending order).
Input 1:
5
5 -1 10 2 8 Input 2:
6
10 20 3 40 5 6
Output 1:
-1 2 5 8 10 Output 2:
3 5 6 10 20 40
Task : 5 [5 Marks]
a. Study the algorithm below and implement the quickSort method . Additionally you will also need to implement the “partition” method. After sorting, print both the unsorted array and sorted array and also the time it takes to complete sorting.

b. Implement an algorithm “findK” that uses the “partition” algorithm to find the kth
(smallest) element from an array without sorting. E.g. for the array in our example, the 5th element will be “9”
Input:
The array: 1 3 4 5 9 10 10
K=5
K=7 K= 2
Output: 9
10
3