Week 1
Practice lab – Algorithms and Problem Solving (15B17CI471)
We are given an array of n distinct numbers; where n is large numbers are randomly generated.
The task is to
a) Sort the entire array using selection sort, bubble sort, insertion sort, quick sort and merge
sort. Print the total number of comparisons done in each of the sorting algorithm.
b) Take sorted array from part a) and again run all the sorting algorithm functions. Print the
total number of comparisons done in each of the sorting algorithm.
c) Change the functions to take a flag “order” as argument. This order can be „d‟ or „a‟ for
descending and ascending respectively. The function will sort the array in descending and
ascending order depending on the flag value.
d) Take sorted array from part a). Again run all the sorting algorithm functions with the
“order” flag changed. If array is already in ascending order pass flag value as „d‟ and vice
versa. Print the total number of comparisons done in each of the sorting algorithm.
e) Implement quick sort with three overloaded functions. 1st taking pivot as first index, 2nd
taking pivot as last index and 3rd taking pivot as middle index.
f) Analyse complexity of quick sort and write down your observation of best and worst case
g) Analyse complexity of merge sort and write down your observation of best and worst
case
h) Analyse complexity of bubble sort and write down your observation of best and worst
case
i) Analyse complexity of selection sort and write down your observation of best and worst
case
j) Analyse complexity of insertion sort and write down your observation of best and worst
case
k) Write a function to sort all even-placed numbers in increasing and odd-place numbers in
decreasing order. The modified array should contain all sorted even-placed numbers
followed by reverse sorted odd-placed numbers. Analyse the complexity of your
implemented approach
Note that the first element is considered as even because of its index 0.
Example for part k):
Input: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}
Output: arr[] = {0, 2, 4, 6, 7, 5, 3, 1}
Even-place elements : 0, 2, 4, 6
Odd-place elements : 1, 3, 5, 7
Even-place elements in increasing order :
0, 2, 4, 6
Odd-Place elements in decreasing order :
7, 5, 3, 1
Input: arr[] = {3, 1, 2, 4, 5, 9, 13, 14, 12}
Output: 1, 2, 4, 6, 7, 5, 3, 1
Even-place elements : 3, 2, 5, 13, 12
Odd-place elements : 1, 4, 9, 14
Even-place elements in increasing order :
2, 3, 5, 12, 13
Odd-Place elements in decreasing order :
14, 9, 4, 1
l) Given an integer array of which both first half and second half are sorted. Task is to
merge two sorted halves of array into single sorted array. Analyse the complexity of your
implemented approach
Example:
Input : A[] = { 2 ,3 , 8 ,-1 ,7 ,10 }
Output : -1 , 2 , 3 , 7 , 8 , 10
Input : A[] = {-4 , 6, 9 , -1 , 3 }
Output : -4 , -1 , 3 , 6 , 9
