[go: up one dir, main page]
Scribd
Upload
46 views17 pages

Assignment 2

Manav Verma's data structures assignment compares quicksort and mergesort, discussing their time complexities, differences between full binary and complete binary trees, heapsort and heapify, binary search trees, threaded binary trees, and polynomial representation. Quicksort is generally faster than mergesort for average cases but mergesort has better worst-case performance. Heapsort uses a heap data structure to sort in O(n log n) time. Binary search trees allow efficient insertion and deletion while maintaining sorted order. Threaded binary trees reduce wasted space by replacing null pointers with threads to other nodes. Polynomials can be represented as linked lists of term coefficients and exponents.

Uploaded by

Manav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
46 views17 pages

Assignment 2

Manav Verma's data structures assignment compares quicksort and mergesort, discussing their time complexities, differences between full binary and complete binary trees, heapsort and heapify, binary search trees, threaded binary trees, and polynomial representation. Quicksort is generally faster than mergesort for average cases but mergesort has better worst-case performance. Heapsort uses a heap data structure to sort in O(n log n) time. Binary search trees allow efficient insertion and deletion while maintaining sorted order. Threaded binary trees reduce wasted space by replacing null pointers with threads to other nodes. Polynomials can be represented as linked lists of term coefficients and exponents.

Uploaded by

Manav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 17

Name: Manav Verma

Roll Number: R2142211002


SAP ID: 500091766

DATA STRUCTURE ASSIGNMENT - 2

Q1) DIFFERENCE BETWEEN MERGE SORT AND QUICK SORT WITH


THEIR TIME COMPLEXITY.
Quicksort is an internal and comparison-based algorithm that pursues the divide and
conquer strategy to sort the arrays. It is also known as partition exchange sort. In quick
sort, we mostly prefer a pivot (key) for resembling and partitioning the components in
the array. The elements which have less value as compared to the pivot will shift to the
left side. On the other hand, the elements which have greater value as compared to the
pivot will shift to the right side of the pivot. The left and right sections are known as the
left and right partitions, respectively.
Merge sort is an external algorithm that also prefers the ‘divide and conquer technique’.
It divides the array into two parts. It sorts the array separately and merges them
concurrently to construct the sorted array.

S.No. Quick Sort Merge Sort

1. It follows the divide and conquer It also follows the divide and conquer
method. method.

2. Here, we sort the components by It splits the array into two segments or
comparing each component with the subarrays on repetition until one
pivot. component is left.

3. It is inefficient for large arrays as It is more efficient as compared to the quick


compared to the merge sort. sort.

4. It is an internal sorting technique. It is an external sorting technique.

5. The time complexity for the worst The time complexity for the worst case is O
case is O (n2). (n log n).

6. The quick sort is mostly preferred for The merge sort is mostly applicable for the
large unsorted arrays. linked lists.

Difference between Quick Sort and Merge Sort

Time Complexity of Quick Sort:


Quicksort works under the hood of the famous divide and conquer algorithm. In this
technique, large input arrays are divided into smaller sub-arrays, and these sub-arrays
are recursively sorted and merged into an enormous array after sorting.

Best and Average time complexity: O (n log n)

Worst-case time complexity: (n2)

Time Complexity of Merge Sort

Merge Sort also works under the influence of the divide and conquer algorithm. In this
sorting technique, the input array is divided into half, and then these halves are sorted.
After sorting, these two halved sub-arrays are merged into one to form a complete
sorted array.

Best and Average time complexity: O (n log n)

Worst-case time complexity: O (n log n)

Q2) DIFFERENCE BETWEEN FULL BINARY AND COMPLETE


BINARY.
FULL BINARY TREE

A full binary tree can be defined as a binary tree in which all the nodes have 0 or two
children. In other words, the full binary tree can be defined as a binary tree in which all
the nodes have two children except the leaf nodes.

The below tree is a full binary tree:

The above tree is a full binary tree as all the nodes except the leaf nodes have two
children.

COMPLETE BINARY TREE


A binary tree is said to be a complete binary tree when all the levels are completely
filled except the last level, which is filled from the left.

The below tree is a complete binary tree:

The complete binary tree is similar to the full binary tree except for the two differences
which are given below:

o The filling of the leaf node must start from the leftmost side.
o It is not mandatory that the last leaf node must have the right sibling

Q3) WHAT IS HEAPIFY? EXPLAIN THE CONCEPT OF HEAP SORT


WITH EXAMPLE.
The process of creating a heap data structure using the binary tree is called Heapify.
The heapify process is used to create the Max-Heap or the Min-Heap.
Heap Sort is one of the best sorting methods being in-place and with no quadratic
worst-case running time. It is a comparison-based sorting technique based on a Binary
Heap data structure.
Algorithm. The Heapsort algorithm involves preparing the list by first turning it into a
max heap. The algorithm then repeatedly swaps the first value of the list with the last
value, decreasing the range of values considered in the heap operation by one, and
sifting the new first value into its position in the heap.
Get Maximum or Minimum Element: O (1) Insert Element into Max-Heap or Min-Heap:
O (log N)…

Min Heap Max Heap


In a Min-Heap the minimum key In a Max-Heap the maximum key
1.
element present at the root. element present at the root.

A Min-Heap uses the ascending A Max-Heap uses the descending


2.
priority. priority.
Q4) WHAT IS BINARY SEARCH TREE? PROGRAM TO IMPLEMENT
INSERTION AND DELETION IN BINARY SEARCH TREE.
Binary Search Tree (or BST) is a special kind of binary tree in which the values of all
the nodes of the left subtree of any node of the tree are smaller than the value of the
node. Also, the values of all the nodes of the right subtree of any node are greater than
the value of the node.
Q5) WHAT ARE THREADED BINARY TREE? PROGRAM TO
IMPLEMENT THE TRAVERSAL IN THREADED BINARY TREE.

In the linked representation of binary trees, more than one half of the link fields
contain NULL values which results in wastage of storage space. If a binary tree
consists of n nodes then n+1 link fields contain NULL values. So in order to
effectively manage the space, a method was devised by Perlis and Thornton in
which the NULL links are replaced with special links known as threads. Such
binary trees with threads are known as threaded binary trees. Each node in a
threaded binary tree either contains a link to its child node or thread to other
nodes in the tree.

One-way threaded Binary trees:

In one-way threaded binary trees, a thread will appear either in the right or left
link field of a node. If it appears in the right link field of a node then it will point
to the next node that will appear on performing in order traversal. Such trees are
called Right threaded binary trees
Two-way threaded Binary Trees:

In two-way threaded Binary trees, the right link field of a node containing NULL
values is replaced by a thread that points to nodes inorder successor and left
field of a node containing NULL values is replaced by a thread that points to
nodes inorder predecessor.

CODE:
OUTPUT:
Q6) DESCRIBE POLYNOMIAL REPRESENTATION.
A polynomial is of the form: i n i ∑ ci
Where, ci is the coefficient of the ith term and n is the degree of the polynomial.
Some examples are: 5x2 + 3x + 1 , 12x3 – 4x ,
5x4 – 8x3 + 2x2 + 4x1 + 9x0
A linked list structure that represents polynomials 5x4 – 8x3 + 2x2 + 4x1 + 9x0

It is not necessary to write terms of the polynomials in decreasing order of degree. In


other words, the two polynomials 1 + x and x + 1 are equivalent.
The computer implementation requires implementing polynomials as a list of pairs of
coefficient and exponent. Each of these pairs will constitute a structure, so a polynomial
will be represented as a list of structures
Addition of Polynomials: To add two polynomials we need to scan them once. If we find
terms with the same exponent in the two polynomials, then we add the coefficients;
otherwise, we copy the term of larger exponent into the sum and go on. When we reach
at the end of one of the polynomials, then remaining part of the other is copied into the
sum.
To add two polynomials, follow the following steps:
• Read two polynomials
• Add them.
• Display the resultant polynomial.

You might also like