Description
2 Implement Sorting Algorithms
Implement the following sorting algorithms using C++ programming language and sort the
input sequence in ascending order.
1. Insertion Sort
2. Selection Sort
3. Rank Sort
4. Bubble Sort
5. Merge Sort
6. Quick Sort
7. Heap Sort
Note:
1. Program should take n inputs given from the user and display the sorted sequence.
2. Each array is implemented using the sequential linear list data structure (seqLinearList.hpp).
3. Everyone should use the seqLinearList.hpp and sorting.hpp classes provided. Do not
change the class names. It is expected to strictly use the interfaces provided in the classes
to implement the tasks.
3 Problems
1. Ross and Rachel are trying to find a new place to live together as a couple. They are in
a dilemma. Their friends live in different parts of the city and they want to live close to
all of them. All the houses in the city lie on the lattice(integral) points on a horizontal
line (x-axis). You are given the x-coordinates of all the houses along that line in an array
A of n integers A1, A2, · · · , An. Your task is to find the sum of all the distinct x that
will minimize the total of the distances between their(Ross and Rachel) and each friend’s
house. Note that they can also live at their friends’ place if required. Print the answer
modulo 109 + 7.
2. There is a small primary school in town Gachibowli. There studies a girl named Pratibha.
She is very talented and hard-working. Whenever she doesn’t find any work she starts
getting depressed. Today she has completed all her school homework and now she has
nothing to do. To avoid depression she usually takes an array of length n and starts
playing with it. She first rolls a dice and according to a number she gets on dice she
performs an operation on the array which is usually swapping some elements in the array.
If the number on the dice is even she divides it by two and gets the operation number to
be performed. If the number on the dice is odd then she divides the number by two and
adds one to it to get the operation number to be performed. Apart from this she also has
an integer ”head”.
Operation 1: She takes the (head+1)th element(say it x) from the array and inserts it
between the 1st and (head)th element of the array. She inserts it at ith place such that
(i+1)th element is greater than x and (i-1)th element is smaller than x(if there are multiple
such places then choose min ”i”). If she doesn’t find both the conditions true at the same
time she puts it at a place where at least on of the two conditions holds. After that she
increase the head by 1.
Operation 2: She takes the minimum element between (head+1)th and (n)th index of
the array and swaps it with (head+1)th element of the array. After that she increase the
head by 1.
2
Operation 3: She iterates from (head+1)th element till end of the array and swaps two
elements if a[i]>a[i+1].
She has done some k operations on the array and now it’s time for her to go for her dance
class. She wants you to validate if she has done any mistake while doing operations or
not. (You should not use any other additional array other than array you are performing
operations on.)
3. ”Hardest choices require strongest wills (and so does this problem 🙂 )”.
Thanos is the sole survivor of his planet(Moon of Saturn) Titan who has a different perception of the world. According to him, the resources of universe are limited and the
days are not too far when there would only be starving and death when the resources get
exhausted. So he is on his own mission to save the universe by killing half population of
every species in the universe. On his conquest, he had come across infinity stones and
came to know that if he could harness the power of these relics then he could achieve his
goal just by a snap of his fingers. So he compelled Eitri of Nidavellir, the weapon forger,
to make him a gauntlet so as to harness the power of infinity stones. Now after many
hardships, he finally had all infinity stones and then snaps his finger. The gauntlet was
designed in a way that doesn’t hinder the natural process of evolution by natural selection(to some extent). So it firstly divides the population into half and then exchanges at
most K healthy individuals from one half to the other in order to maximize the difference
between the health metrics of both groups and kills the half which is lesser healthy. What
is the algorithm that gauntlet applies? Implement it.
Solve it as efficiently as much you can (in terms of time and space complexity).
Input: An array A with values as health metrics of population and integer K.
Output: Two arrays P and Q with Q being the population that has been killed.
4. In the primary school of Gachibowli, every morning the students assemble in the school
playground for prayer. There are ’N’ lines formed at the time of prayer and each line
is represented using an uppercase English alphabet. Students enter in the playground in
groups of ’M’. Each student has an RollNo assigned by the school. Roll No of students
also contains information about the line in which student is going to stand. RollNo’s are
assigned in such a way that students of same class stand in same line. Roll No is of the
form XZ(ex C123) where X is an uppercase character denoting the line in which student
has to stand and Z is a unique integer id assigned to each student. Students have returned
after a long vacation. Today, the student are forming lines in a particular fashion. They
want to stand behind the first friend they encounter in their line. Two students are friends
if they have two common factors other than 1 in their id’s(Ex: if the id’s are 6,12 then
they have 2,3 as factors and they are friends. Also 4,8 are friends as they have 2,2 as
common factors but 3,6 are not friends). There are total of ’K’ number of student in the
school. Now the PTI Chaubey comes in and finds that the students are standing with their
friends making noise. So he decided to arrange them into line according to their height.
3
He will swap 2 students in a line at a time and it will cost him on an average of 0.5 sec
for each swap. He wants you to help him minimize the time taken to rearrange students
in all lines so that the prayer will start as soon as possible. Calculate the minimum time
required to rearrange each of the n lines.
Input:
N : No of lines in playground(0<= N <=26)
M : No of students in groups entering into ground.
K : Total number of students in school(It need not be multiple of M. In that case last
group entering the ground will have (K mod M) no of students.)
The next k lines will contain two integers each corresponding to student id(integer) and
his height(double)
Then there will be ceil(K/N) no of lines telling the students id’s in each group entering
the ground.
Output: Output ’N’ numbers showing minimum time required to rearrange each of the
n lines(numbers should be in order of line index ’A’ to ’Z’).
(Use Linked List for mimicking each line in ground. Your program should be modular
and clean. Try to solve it as efficiently as possible.)
4
