[go: up one dir, main page]
Scribd
Upload
38 views6 pages

(Data Structure AND Algorathims) : (Teacher: MR Yang Weichao)

Uploaded by

ali

data structure assignment about algorithem on circut analysis or OR gate and etc algorithms submitted to china west normal university for the final semester of bacholer

Copyright:

© All Rights Reserved
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt

(Data Structure AND Algorathims) : (Teacher: MR Yang Weichao)

Uploaded by

ali
38 views6 pages
data structure assignment about algorithem on circut analysis or OR gate and etc algorithms submitted to china west normal university for the final semester of bacholer

Original Title

DSA-SAAD-EIE19 AS#02

Copyright

© © All Rights Reserved

Available Formats

DOCX, PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

data structure assignment about algorithem on circut analysis or OR gate and etc algorithms submitted to china west normal university for the final semester of bacholer

Copyright:

© All Rights Reserved
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
38 views6 pages

(Data Structure AND Algorathims) : (Teacher: MR Yang Weichao)

Uploaded by

ali
data structure assignment about algorithem on circut analysis or OR gate and etc algorithms submitted to china west normal university for the final semester of bacholer

Copyright:

© All Rights Reserved
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 6

[DATA

STRUCTURE
[Name: Syed Saad
AND Hasan]
ALGORATHIMS] [ID:201922240126]
[Session: Spring 2020]
[ Teacher: Mr Yang
[Dated:29-March-2020]
Weichao ]

[Assignment No. 02]


Q1. Pseudo code for insertion sort?
Answer: Insertion Sort Algorithm
Insertion sort is the sorting mechanism where the sorted array is built having one item at a time.
The array elements are compared with each other sequentially and then arranged simultaneously
in some particular order. The analogy can be understood from the style we arrange a deck of
cards. This sort works on the principle of inserting an element at a particular position, hence the
name Insertion Sort.
For Understanding we following steps:
1. The first step involves the comparison of the element in question with its adjacent element.
2. And if at every comparison reveals that the element in question can be inserted at a
particular position, then space is created for it by shifting the other elements one position to
the right and inserting the element at the suitable position.
3. The above procedure is repeated until all the element in the array is at their apt position.
Let us now understand working with the following example:
Consider the following array: 25, 17, 31, 13, 2
First Iteration: Compare 25 with 17. The comparison shows 17< 25. Hence swap 17 and 25.
The array now looks like:
17, 25, 31, 13, 2

Second Iteration: Begin with the second element (25), but it was already swapped on for the
correct position, so we move ahead to the next element.
Now hold on to the third element (31) and compare with the ones preceding it.
Since 31> 25, no swapping takes place.
Also, 31> 17, no swapping takes place and 31 remains at its position.
The array after the Second iteration looks like:
17, 25, 31, 13, 2

Third Iteration: Start the following Iteration with the fourth element (13), and compare it with its
preceding elements.
Since 13< 31, we swap the two.
Array now becomes: 17, 25, 13, 31, 2.
But there still exist elements that we haven’t yet compared with 13. Now the comparison takes
place between 25 and 13. Since, 13 < 25, we swap the two.
The array becomes 17, 13, 25, 31, 2.
The last comparison for the iteration is now between 17 and 13. Since 13 < 17, we swap the two.
The array now becomes 13, 17, 25, 31, 2

Fourth Iteration: The last iteration calls for the comparison of the last element (2), with all the
preceding elements and make the appropriate swapping between elements.
Since, 2< 31. Swap 2 and 31.
Array now becomes: 13, 17, 25, 2, 31.
Compare 2 with 25, 17, 13.
Since, 2< 25. Swap 25 and 2.
13, 17, 2, 25, 31.
Compare 2 with 17 and 13.
Since, 2<17. Swap 2 and 17.
Array now becomes:
13, 2, 17, 25, 31.
The last comparison for the Iteration is to compare 2 with 13.
Since 2< 13. Swap 2 and 13.
The array now becomes:
2, 13, 17, 25, 31.
This is the final array after all the corresponding iterations and swapping of elements.

Pseudo code:
INSERTION-SORT(A)
for i = 1 to n
key ← A [i]
j ← i – 1
while j > = 0 and A[j] > key
A[j+1] ← A[j]
j ← j – 1
End while
A[j+1] ← key
End for
Q2. Merging Sort?
Answer: Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls
itself for the two halves and then merges the two sorted halves. The merge () function is used for
merging two halves. The merge (arr, l, m, r) is key process that assumes that arr[l..m] And
arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C
implementation for details.

MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)

Q3. Θ Notation?
Answer: The main idea of asymptotic analysis is to have a measure of efficiency of algorithms
that doesn’t depend on machine specific constants, and doesn’t require algorithms to be
implemented and time taken by programs to be compared. Asymptotic notations are mathematical
tools to represent time complexity of algorithms for asymptotic analysis. The following 3
asymptotic notations are mostly used to represent time complexity of algorithms.

Θ Notation: The theta notation bounds a functions from above and below, so it defines exact
asymptotic behavior.A simple way to get Theta notation of an expression is to drop low order
terms and ignore leading constants. For example, consider the following expression.
3n3 + 6n2 + 6000 = Θ(n3)
Dropping lower order terms is always fine because there will always be a n0 after which Θ(n 3) has
higher values than Θn2) irrespective of the constants involved. For a given function g(n), we denote
Θ(g(n)) is following set of functions.
Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such
that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}
The above definition means, if f(n) is theta of g(n), then the value f(n) is always between c1*g(n)
and c2*g(n) for large values of n (n >= n0). The definition of theta also requires that f(n) must be
non-negative for values of n greater than n0.

You might also like