PDS PROJECT REPORT

Year 2020

Submitted to
Department of Electrical Engineering
National Institute of Technology Silchar

Submitted by:
GROUP NO. STUDENTS NAME SCHOLAR ID:
ASHISH RAJ 17-13-064
13 PRITESH ABHISHEK 17-13-063
MANSUR AHMED 17-13-053
LASKAR
PRASHANT LODHI 17-13-110

MENTOR’S NAME:
Prof. BADAL SONI
ASSISTANT PROFESSOR
COMPUTER SCIENCE DEPATEMENT

PDS PROJECT REPORT 1

ANS 1:
The question is, the good or best way to physically sort a book collection.
This totally depends on the type or amount of data one have. If the range of data is fixed then one can
implement bucket sort or quick sort etc. which have linear time complexity.

Now considering the condition that, data are not limited for a fixed range, then if there are less
amount of data (i.e., space is not a issue then merge sort would be better because it will sort in O(n log
n) with extra spaces.

Now, if the condition is that number of data is very large i.e., space will also create issue in this case
again we have to check data are nearly sorted or purely random. If the given data is completely
random then quick sort would be better as it will do the work in O (n log n) without any extra space.

Now if the some part of data are nearly sorted then insertion sort would be better one. Because for
sorted items it will not check till last data .

So here, let consider that one have around ten books and have to sort them alphabetically by hand.
There are various sorting algorithm which will fulfil one’s purpose.
Like one can use either Bubble sort, Selection Sort, Insertion sort, Merge or quick sort etc.
From the above quick and merge sort are the fastest due to linear time complexity i.e. (O(n log n)).
Well a possible suitable algorithm would be quicksort. But it has problems.

What if the books are already sorted and because of this reason time complexity is very high also
doing physically this could be difficult as it is prone to human error.

One will do a lot of swaps. Especially if the bookcase is tightly packed, this could make one’s life
miserable when books don't fit where they have to be placed.

But here Insertion sort algorithm will be good for this.

If the data are nearly sorted then insertion sort have advantage over other sorting algorithm. Because
for sorted items it will not check for data till end.
As for insertion sort, it probably depends on how one seek the insertion point. If one is doing binary
search then probably you are fine. If one simply bubble the current element to the left, then it gets
more interesting to analyse - it's obvious to one that it is better than selection sort, as one compares
only a subset of all possible pairs of words, and never compare the same pair twice.
Insertion sort might not be the most efficient algorithm out there but it has an advantage that, it is easy
to implement and efficient for all small sets of data.
Since insertion sort is quite easy to implement and adequately efficient for small number of elements,
it is useful for small applications or trivial ones. The definition of small is vague and depends on a lot
of things but for fast and accurate result one can rely on insertion sort.

PDS PROJECT REPORT 2

Another situation that insertion sort is useful is when the given set of sequence or data is almost
sorted. Such sequences might not possible every time but in real world applications one often
encounter almost sorted elements. The run time of insertions sort is quadratic O(n^2) at worst case
scenario. But if implemented well the run time can be reduced to O(n). n is the number of
elements/data). The reason is that, during the first iteration, the first element from the unsorted set is
compared only with the last element of the sorted set of the array. With this modified new run time in
mind one can look if the sequence is almost sorted the run time can be almost linear which is a huge
improvement over the polynomial n^2 and also it requires less memory space.

Yes, answer will change if one have nearly one thousand books.
Now for this case one can use Quick sort algorithm because below to reasons:
• It is generally the fastest sorting algorithm in one can implement. It only swaps what needs
to be swapped and the Swaps are slow.
• It has the least O (log n) space complexity.
• Its efficient implementation can minimize the probability of requiring quadratic time.
• It also has been used in industry for many years so one can have faith in it.

One will not use Merge sort algorithm because of these two drawbacks:
• Has O(n) space complexity, which is worse than the other Quick sort.
• We have to write all your data into another array and back into your original one. Copying
is usually slower than comparing.

Certain sorts that perform well computationally just do not work in every day life. If we use
Quicksort and heapsort, as they just don't make sense if we consider the addressing difficulties.

The O(N^2) sorts that are often dismissed actually do work rather well, since the N is relatively small
most of the time when sorting book, and the act of linearly searching through the stack of books,
which most of this class of algorithm depends on, takes about the same time as specifically addressing
a sub stack.

Bucket sorts actually works extremely well, since we can still relatively quickly address the 26
English alphabets.

There definitely are some recursive sorts that can still work well when sorting manually. Merge sort
only depends on comparison between two objects at a time, and merging into a single pile, so it works
exceptionally well. However, it requires a large amount of space if one follow the algorithm
rigorously since it copies the data into different subarray.

Finally, a combination of sorting algorithm often works better than just sticking to a single algorithm.
The implementation of sort is a combination of intro sort (which in itself is quicksort + heapsort) and
insertion sort. So in practice, one can found that what works well with large stacks (between 500-1000
books) is to first split the stack into K sub-stacks, where K is a power of two, and each sub-stack has
less than 100 set of books.
Then, bucket each sub-stack alphabetically. Most of the bucket sets should be small, so that selection
or insertion sort can speedily get each bucket in order. Once each sub-stack is sorted, start combining
pairs by implementing merge sort.

PDS PROJECT REPORT 3

Yes, it depends on the order of the books currently in.
Quick sort has the worst case performance when the given input data is already sorted and the pivot is
chosen as the left most element with time complexity O(n^2).

We know that quicksort divides the array in half each iteration on a pivot value or the partition. Then,
it compares the partition to each sub-array. It moves the values all the books left that comes before the
pivot/partition and the remaining books to the right side, building an ideally balanced binary tree with
the pivot/partition as the root node and don’t have to compare books on the left with books on the
right.

If the input data is already sorted, then Quicksort formed an unbalanced binary tree with the partition
having only one child or skew tree of height n. When all the nodes (partition) in a binary tree have
only one child, then it is really represents a linked list of array length n.

The effect is n partition through n array elements, or O(n2) O(n2) worst case performance.

ANS 2:
Selection sort is a simple and one of the basic sorting algorithms of array. We start sorting the data
from left side and move towards the right side of the data. We move the selected minimum data to left
side of the data(it’s assigned position) and make a loop for moving the remaining data one by one.
The smallest value is selected from the unsorted array and swapped with the its actual positioned
element, and that part is considered as sorted array part. This process continues until we reach a sorted
array.
This algorithm can’t be considered for large set of data as its average and worst-case complexities is
Ο(n2), where n is number of elements in an array.

EXAMPLE:-

Let’s take an example.

13 32 26 9 34 18 41 43

For the first position in the sorted list, we find the minimum value of the array. We form a loop
and found 10 as the lowest value.

13 32 26 9 34 18 41 43

Hence, we swapped 14 with 10. And after one round 10 is considered as the part of the sorted
array.

PDS PROJECT REPORT 4

 9 32 26 13 34 18 41 43

For the second position, we again scan for next smallest number and replace it with the
second element of the array.

9 32 26 13 34 18 41 43

After one round, we found 14 as the second lowest element, so we have replace it with
second element that is 33.

9 32 26 13 34 18 41 43

Now, after two round two values are placed at there position and that part of array is called
sorted array.

9 13 26 32 34 18 41 43

Same process is repeated until we obtain a sorted list of array in ascending order.
Following are the process happening, as shown in figure.

9 13 26 32 34 18 41 43

9 13 26 32 34 18 41 43

9 13 18 32 34 26 41 43

9 13 18 32 34 26 41 43

9 13 18 26 34 32 41 43

9 13 18 26 34 32 41 43

PDS PROJECT REPORT 5

 9 13 18 26 34 32 41 43

9 13 18 26 32 34 41 43

9 13 18 26 32 34 41 43

Algorithm:

Step 1 – MIN is set to initial element of array.

Step 2 − Search the minimum value in the array
Step 3 – position is swapped between min value and the position where it supposed to be in sorted
part of array ( or, after the sorted part of array).
Step 4 – MIN is incremented to point next element.
Step 5 – repeat until array is sorted

CODE:
#include <stdio.h>
#include <stdlib.h>

int min(int A[], int k, int N)

{
int l, MIN;
MIN=A[k];
l=k;
for(int j=k+1; j<N-1; j++)
if(MIN>A[j])
{
MIN=A[j];
l=j;

PDS PROJECT REPORT 6

 }
return(l);

}
int main()
{
int A[]={13,32,26,9,34,18,41,43};
int l,k,t;
for(k=0;k<6;k++)
{
l=min (A,k,8);
t=A[k];
A[k]=A[l];
A[l]=t;
}
for(k=0;k<=7;k++)
printf("%d\t",A[k]);
getch();
}

Comparison Chart:

QUANTITY INSERTION SORTING SELECTION SORTING

definition The data is sorted by inserting the The data is sorted by selecting a

smallest data from remaining data into minimum value in data and placing the

an existing sorted part. data in sorted location.

PDS PROJECT REPORT 7

 QUANTITY INSERTION SORTING SELECTION SORTING

procedure Elements are known before the Position is previously known while

program while location to place them is elements are looked.

looked.

During loop Insertion sort is live sorting technique It cannot deal with data recently

which can deal with recently supplied supplied; it needs to be present from
Immediate data
data. the starting.

Complexity O(n) O(n2)

of sorting

Ans 3:
MERGE SORT
Merge sort algorithm was first introduced by John Von Neumann. The algorithm works on
divide and conquer policy. Merge sort algorithm is very much efficient for large arrays. It has an
efficient time complexity of O(nlog(n)) and a space complexity of O(n). Merge sort can be compared
to a large assignment to be done by a group of people. First, the work is divided among the employees
and then the individual work is merged to get the whole work.
The sorting method contains two steps. First, the array is divided into halves till individual
elements are separated from each other. In second step, all the individual elements are rejoined or
merged. The divide and merge process are done in recursive manner.
For disintegrating the array, three parameters are required- The array, LOWER index and
UPPER index of the array. Then the MIDDLE index of the array is found using the formula
(LOWER+UPPER)/2. If there are odd number of elements in array, rounding is done so that the left
portion contains more numbers of element than right part of the array. In next step, two arrays are
divided and their own UPPER and LOWER index are assigned. The process is repeated recursively to
fully disintegrate the array into single element arrays.
Elements are merged and sorted consecutively. Two arrays (which are separated from same
array previously) are merged. The UPPER index of new array is same as that of the right array. The

PDS PROJECT REPORT 8

LOWER index of new array is same as that of left array. While merging, the merged array is
developed by sorting both the arrays. The process of merging is also recursive

ALGORITHM FOR MERGE SORT

MERGE

Step 1: [INITIALIZE] SET I = LOWER, J = MID + 1, INDEX = 0

Step 2: Repeat while (I <= MID) AND (J<=UPPER)

IF ARR[I] < ARR[J]
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[END OF IF]
SET INDEX = INDEX + 1
[END OF LOOP]

Step 3: [Copy the remaining elements of right sub-array, if any]

IF I > MID
Repeat while J <= UPPER
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[END OF LOOP]
[Copy the remaining elements of left sub-array, if any]
ELSE
Repeat while I <= MID
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[END OF LOOP]
[END OF IF]

Step 4: [Copy the contents of TEMP back to ARR] SET K = 0

Step 5: Repeat while K < INDEX

SET ARR[K] = TEMP[K]
SET K = K + 1
[END OF LOOP]

PDS PROJECT REPORT 9

 Step 6: Exit

MERGE_SORT (ARR, LOWER, UPPER)

Step 1: IF LOWER < UPPER

SET MID = (LOWER + UPPER)/2
CALL MERGE_SORT (ARR, LOWER, UPPER)
CALL MERGE_SORT (ARR, MID + 1, UPPER)
MERGE (ARR, LOWER, MID, UPPER)
[END OF IF]

Step 2: END

Now let us take an array [32 54 9 35 21 91 41] to explain the procedure briefly. Here we
are going to sort the elements in ascending order.
Here total number of elements = 7,
Therefore, LOWER index = 0;
And UPPER index = 6;
So, index of MIDDLE element = (0+6)/2 = 3
As, there are 7 elements, the array is divided into two parts – left array has 4 elements and right array
has 3 elements.
After diving the arrays are shown below:

[32 54 9 35] [21 91 41]

Now, we have two arrays, if we apply same method to both arrays as in earlier array, we get the below
arrays:

[32 54] [9 35] [21 91] [41]

Again, dividing by above mentioned method, we get

PDS PROJECT REPORT 10

 [32] [54] [9] [35] [21] [91] [41]
So, here we are at the final position of step 1 mentioned in 2nd para. Now we need to merge the arrays
with sorting.
Here we are going to discuss about the merge of 32 and 54. At the time of merging, a new
array is created, whose UPPER index is same as that of 54 and LOWER index is same as that of 32.
Now, 32 is placed at first position and 54 is placed at second position of array as 32 is smaller than 54.
The same procedure is followed for 9,35 pair and 21,91 pair. 41 remains as it is because it has no
adjacent member.
So, after first step of merging we get the arrays as shown below,

[32 54] [9 35] [21 91] [41]

Again, merging is done on the arrays as done in above step, [32 54] & [9 35] array pair are merged
and [21 91] & [41] array pair are also merged. Finally, we get the result as shown below.

[9 32 35 54] [21 41 91]

Again, merging the arrays as done in above step, both the arrays are merged and sorted in ascending
manner.

[9 21 32 35 41 54 91]

So, we have finally got the sorted array after dividing and merging the given array.

CODE:
Using C
#include <stdio.h>
#define max 10
int b[6]; //auxillary space

int merge(int lower, int middle, int higher, int A[], int B[])

PDS PROJECT REPORT 11

{
int index1, index2, i; //temporary variable

for(index1 = lower, index2 = middle + 1, i = lower; index1 <= middle && index2 <= higher; i++) {
if(A[index1] <= B[index2])
b[i] = A[index1++];
else
b[i] = A[index2++];
}

while(index1 <= middle)

b[i++] = A[index1++];

while(q <= higher)

b[i++] = A[index2++];

for(i = lower; i <= higher; i++)

{
A[i] = b[i];
}
return 0;
}

void Merge_sort(int lower, int higher) {

int middle;
if(lower < higher) {
middle = (lower + higher) / 2;
Merge_sort(lower, middle);
Merge_sort(middle+1, higher);
merge(lower, middle, higher);
} else {
return;

PDS PROJECT REPORT 12

 }
}

int main() {
int I, a[] = { 9,21,32,35,41,54,91};
printf("given no.s before sorting\n");

for(i = 0; i <= max; i++)

printf("%d ", a[i]);

Merge_sort(0, max);

printf("\no.s after sorting\n");

for(i = 0; i <= max; i++)

printf("%d ", a[i]);
return 0;
}

COMPARISON BETWEEN MERGE SORT AND INSERTION SORT:

MERGE SORT INSERTION SORT

1. In all cases merge sort has time 1. In Insertion Sort, the Worst Case and
complexity 𝑂(𝑛𝑙𝑜𝑔𝑛). average Case is 𝑂(𝑛2 ) and Best Case
is O(n)

2. It has space complexity O(𝑛). 2. It has space complexity 𝑂(1).

3. Merge Sort is preferred for large data 3. Insertion Sort is preferred for small
sets. number of elements

4. Merge Sort is efficient in terms of time. 4. Insertion Sort is efficient in terms of

space.

5. It is done using divide and conquer 5. It is done using incremental approach.

approach.

6. Recursion is used. 6. Recursion is not used.

PDS PROJECT REPORT 13

Conclusion:
All the questions are answered with explanation. Algorithm and code is written as per the required
question. In the first question the best algorithm for sorting books alphabetically with proper
explanation is written. After that in the second question we have explained selection sort algorithm
with example and compared it with insertion sort. We conclude from that, insertion sort is a better
option than selection sort though it is the very simple and easy to implement. At last we have
explained merge sort with example and compared it with insertion sort and conclude that though
merge sort has linear time complexity but it required a lot of space to implement. So it depend on the
user which sorting algorithm they want to use.

PDS PROJECT REPORT 14