CSE221 LabAssignment02 solved

$30.00

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment

Description

5/5 - (5 votes)

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 θ(n
2
). 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] )
The first line of the input will contain N, which is the size of the array. Next line will
contain the N number of elements. Output will contain the sorted elements.
P.S: sample input and output may not be the preferred answer choice.
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 5 th element will be “9” Input: The array: 1 3 4 5 9 10 10 K=5 K=7 K= 2 Output: 9 10 3