ADA unit-1

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 14

Algorithms

What is the algorithm? Write its


criteria and characteristics
Algorithm
 An algorithm is a step-by-step procedure to solve a problem in a
finite number of steps.
 Branching and repetition are included in the steps of an algorithm.
 This branching and repetition depend on the problem for which
Algorithm is developed.
 All the steps of Algorithm during the definition should be written in a
human-understandable language which does not depend on any
programming language.
 We can choose any programming language to implement the
Algorithm.
 Pseudo code and flow chart are popular ways to represent an
algorithm.

An algorithm must satisfy the following criteria:-

1. Input: An algorithm should have zero or more but should be a finite


number of inputs. We can also say that it is essential for any algorithm
before starting. Input should be given to it initially before the Algorithm
begins.
2. Output: An algorithm must give at least one required result from the
given set of input values. These output values are known as the solution
to a problem.
3. Definiteness: Each step must be clear, unambiguous, and precisely
defined.
4. Finiteness: Finiteness means Algorithm should be terminated after a
finite number of steps. Also, each step should be finished in a finite
amount of time.
5. Effectiveness: Each step of the Algorithm must be feasible i.e., it
should be practically possible to perform the action. Every Algorithm is
generally expected to be effective.

Characteristics of an algorithm:

1). Input: An algorithm must have either 0 or more inputs.


2). Output: An algorithm should have 1 or more desired output.
3). Unambiguous: Every Algorithm should be unambiguous and clear. It
means that it’s every step, and input/output should be clear and must
have only one meaning.
4). Feasibility: Algorithm should be feasible with the available resource.
5). Finiteness: Algorithm should be terminated after a finite number of
steps.
6). Independent: Algorithm should have a step-by-step direction of each
level, which is independent of programming language.

Divide and Conquer Algorithm:-


A divide and conquer algorithm is a strategy of solving a large problem by.
1. Divide: This involves dividing the problem into smaller sub-problems.
2. Conquer: Solve sub-problems by calling recursively until solved.
3. Combine: Combine the sub-problems to get the final solution of the whole problem.
Divide and Conquer Applications
 Binary Search
 Merge Sort
 Quick Sort
 Strassen's Matrix multiplication

 Karatsuba Algorithm

 Cooley-Tukey Fast Fourier Transform (FFT) algorithm


Advantages of Divide and Conquer
o Divide and Conquer tend to successfully solve one of the biggest
problems, such as the Tower of Hanoi, a mathematical puzzle. It is
challenging to solve complicated problems for which you have no
basic idea, but with the help of the divide and conquer approach, it
has lessened the effort as it works on dividing the main problem into
two halves and then solve them recursively. This algorithm is much
faster than other algorithms.
o It efficiently uses cache memory without occupying much space
because it solves simple sub- problems within the cache memory
instead of accessing the slower main memory.
o It is more proficient than that of its counterpart Brute Force
technique.
o Since these algorithms inhibit parallelism, it does not involve any
modification and is handled by systems incorporating parallel
processing.
Disadvantages of Divide and Conquer
o Since most of its algorithms are designed by incorporating recursion,
so it necessitates high memory management.
o An explicit stack may overuse the space.
o It may even crash the system if the recursion is performed rigorously
greater than the stack present in the CPU.
Sorting
In data structure, Sorting is the process of arranging the elements/data
of an array so that they can be placed either in ascending or
descending order.
OR
A Sorting Algorithm is used to rearrange a given array or list of elements
according to a comparison operator on the elements. The comparison
operator is used to decide the new order of elements in the respective
data structure.
For example, consider an array A = {A1, A2, A3, A4, ??, An }, the array is called to
be in ascending order if element of A are arranged like A1 > A2 > A3 > A4 > A5 > ?
> An .
Consider an array;
int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )
The Array sorted in ascending order will be given as;
A[]= { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }
There are two different categories in sorting:
• Internal sorting: If the input data is such that it can be adjusted
in the main memory at once, it is called internal sorting.
• External sorting: If the input data is such that it cannot be
adjusted in the memory entirely at once, it needs to be stored in a
hard disk, floppy disk, or any other storage device. This is called
external sorting.

Types of Sorting in Data Structure:-

1. Merge Sort
Merge sort is similar to the quick sort algorithm as it uses the divide and conquer
approach to sort the elements. It is one of the most popular and efficient sorting
algorithm. It divides the given list into two equal halves, calls itself for the two
halves and then merges the two sorted halves. We have to define
the merge() function to perform the merging.
The sub-lists are divided again and again into halves until the list cannot be divided
further. Then we combine the pair of one element lists into two-element lists,
sorting them in the process. The sorted two-element pairs is merged into the four-
element lists, and so on until we get the sorted list.
Algorithm:-
1. MERGE_SORT(arr, beg, end)
2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9.
10. END MERGE_SORT

Example:-

Merge sort complexity


Now, let's see the time complexity of merge sort in best case, average case, and in
worst case. We will also see the space complexity of the merge sort.
1. Time Complexity

2. Space Complexity

2. Quick sort
Quick sort is a sorting algorithm based on the divide and conquer approach where,

1. An array is divided into sub-arrays by selecting a pivot element (element selected


from the array).

While dividing the array, the pivot element should be positioned in such a way that
elements less than pivot are kept on the left side and elements greater than pivot are
on the right side of the pivot.
2. The left and right sub-arrays are also divided using the same approach. This process
continues until each sub-array contains a single element.

3. At this point, elements are already sorted. Finally, elements are combined to form a
sorted array.
 Choosing the pivot
Picking a good pivot is necessary for the fast implementation of quick sort.
However, it is typical to determine a good pivot. Some of the ways of choosing a
pivot are as follows -

o Pivot can be random, i.e. select the random pivot


from the given array.
o Pivot can either be the rightmost element of the

leftmost element of the given array.

o Select median as the pivot element.

 Algorithm

1. QUICKSORT (array A, start, end)


2. {
3. 1 if (start < end)
4. 2{
5. 3 p = partition(A, start, end)
6. 4 QUICKSORT (A, start, p - 1)
7. 5 QUICKSORT (A, p + 1, end)
8. 6 }
9. }
Quick sort complexity
Now, let's see the time complexity of quick sort in best case, average case, and in
worst case. We will also see the space complexity of quick sort.
1. Time Complexity

2. Space Complexity

 Advantages of Quick Sort:


 It is a divide-and-conquer algorithm that makes it easier to solve problems.
 It is efficient on large data sets.
 It has a low overhead, as it only requires a small amount of memory to function.

 Disadvantages of Quick Sort:


 It has a worst-case time complexity of O(N 2), which occurs when the pivot is chosen
poorly.
 It is not a good choice for small data sets.
 It is not a stable sort, meaning that if two elements have the same key, their relative
order will not be preserved in the sorted output in case of quick sort, because here
we are swapping elements according to the pivot’s position (without considering
their original positions).

3. Heap sort
What is a heap?
A heap is a special tree based data structure in which the tree is a complete binary
tree, and the binary tree is a tree in which the node can have the utmost two
children. A complete binary tree is a binary tree in which all the levels except the
last level, i.e., leaf node, should be completely filled, and all the nodes should be
left justified.

Types of heap:
 Max- heap:- In a max heap the key present at the root node must be greatest
among the keys present at all of its children . The same property must be
recursively true for all sub trees in that binary tree.

 Min-heap :- In a min heap the key present at the root node must be minimum
among the keys present at all of its children . The same property must be
recursively true for all sub trees in that binary tree.

What is heap sort?


Heap sort is a popular and efficient sorting algorithm. The concept of heap sort is to
eliminate the elements one by one from the heap part of the list, and then insert
them into the sorted part of the list.
Heap sort is the in-place sorting algorithm.
Algorithm:-

Working of Heap sort Algorithm:-


Now, let's see the working of the Heap sort Algorithm.
In heap sort, basically, there are two phases involved in the sorting of elements. By
using the heap sort algorithm, they are as follows -
o The first step includes the creation of a heap by adjusting the elements of the array.
o After the creation of heap, now remove the root element of the heap repeatedly by
shifting it to the end of the array, and then store the heap structure with the
remaining elements.
Heap sort complexity:-
Now, let's see the time complexity of Heap sort in the best case, average case, and
worst case. We will also see the space complexity of Heap sort.
1. Time Complexity

2. Space Complexity
4. Bubble sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-
based algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order.
It is called bubble sort because the movement of array elements is just like the
movement of air bubbles in the water. Bubbles in water rise up to the surface;
similarly, the array elements in bubble sort move to the end in each iteration.
Working of Bubble Sort
Consider that we want to sort a list in ascending order ,here are the steps that the
algorithm would follow:
1. Start with the first element.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, then swap both the
elements. If not, move to the next element.
4. Repeat steps 1 – 3 until we get the sorted list.

Bubble short is majorly used where -


o complexity does not matter
o simple and short code is preferred

Bubble Sort Algorithm

Bubble sort complexity


Now, let's see the time complexity of bubble sort in the best case, average case,
and worst case. We will also see the space complexity of bubble sort.
1. Time Complexity

2. Space Complexity

5. Selection sort
Selection sort is a simple and efficient sorting algorithm that works by
repeatedly selecting the smallest (or largest) element from the unsorted
portion of the list and moving it to the sorted portion of the list.
The algorithm repeatedly selects the smallest (or largest) element from the
unsorted portion of the list and swaps it with the first element of the
unsorted portion. This process is repeated for the remaining unsorted portion
of the list until the entire list is sorted.
One variation of selection sort is called “Bidirectional selection sort” which
goes through the list of elements by alternating between the smallest and
largest element, this way the algorithm can be faster in some cases.

Selection sort complexity


Now, let's see the time complexity of selection sort in best case, average case, and
in worst case. We will also see the space complexity of the selection sort.
1. Time Complexity
Case Time complexity
Best case O(n2)
Average case O(n2)
Worst case O(n2)
2. Space Complexity
Space complexity O(1)

Stable YES

o The space complexity of selection sort is O(1). It is because, in selection sort, an


extra variable is required for swapping.

You might also like