CSE221 Lab 2 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.

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.

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).

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

𝑀𝐸𝑅𝐺𝐸 − 𝑆𝑂𝑅𝑇 (𝐴, 𝑝, 𝑟) 𝑖𝑓𝑝 < 𝑟

//𝐶h𝑒𝑐𝑘𝑓𝑜𝑟𝑏𝑎𝑠𝑒𝑐𝑎𝑠𝑒

𝑞 = (𝑝 + 𝑟)/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).