CSE221-Lab Assignment 02 Solved

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:

Here is code of bubble sort. It’s 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] )

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:

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
Input 2: 7 4
5 10 2 1 4
10 2 3 4 1 100 1
Output 1: 1 2 4
Output 2: 1 1 2 3
Task 3:

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.

𝑓𝑜𝑟 𝑖 ← 0 𝑡𝑜 𝑛 − 1

𝑡𝑒𝑚𝑝 ← 𝐴[𝑖 + 1]

𝑓𝑜𝑟 𝑗 ← 𝑖 𝑡𝑜 0

𝑖𝑓(𝐴[𝑗] > 𝑡𝑒𝑚𝑝)

𝐴[𝑗 + 1] ←𝐴[𝑗]

𝑒𝑙𝑠𝑒

𝑏𝑟𝑒𝑎𝑘 

𝑒𝑛𝑑 𝑓𝑜𝑟

𝐴[𝑗 + 1] ← 𝑡𝑒𝑚𝑝

𝑒𝑛𝑑Implement this pseudocode to complete your task. 𝑓𝑜𝑟

First line 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:

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