An algorithm is simply a set of steps used to complete a specific task. It is a finite set of instructions carried out in a specific order to perform a particular task. It is not the entire program or code; it is simple logic of a problem represented as an informal description in the form of a flowchart or pseudocode.
An algorithm is a set
of well-defined instructions to solve a particular problem. It takes a set of
input and produces a desired output.
An
algorithm is a set of instructions for solving a problem or accomplishing
a task.
Characteristics of an Algorithm:
An algorithm should
have the following characteristics:
1. Input: An
algorithm requires some input values. There should be zero or more inputs supplied externally
to the algorithm.
2. Output: There should be at least one output produced.
3. Definiteness
or Unambiguity: Algorithm should be should
be clear and unambiguous. Each
of its steps should be clear and simple in all aspects and must lead to only
one meaning.
4. Finiteness: The
algorithm must be finite. Here, finiteness means that
the algorithm should contain a limited number of instructions. Algorithms
must terminate after a finite number of steps.
5. Effectiveness: An algorithm
should be effective as each instruction in an algorithm affects the
overall process.. Every instruction must be basic and must be
feasible.
Advantages of Algorithms:
(i) It is simple to understand step by
step solution of the problem.
(ii) It is easy to debug i.e., errors can
be easily pointed out.
(iii) It is not dependent on any programming language, so it is
easy to understand for anyone even without programming knowledge.
(iv) By using algorithm, the problem is broken down into
smaller pieces or steps hence, it is easier for programmer to convert it into
an actual program.
Analysis of Algorithm:
An algorithm is said to be efficient
and fast, if it takes less time to execute and consumes less memory space.
The performance of the algorithm can be measured in two factors:
- Time Complexity
- Space Complexity
Time Complexity:
The time complexity of an
algorithm is the amount of time required to complete its execution. It's generally a good practice
to try to keep the time required minimum, so that our algorithm completes it's
execution in the minimum time possible.
Space Complexity:
It’s the amount of memory space required by the
algorithm, during the course of its execution. Space complexity must be taken
seriously for multi-user systems and in situations where limited memory is
available.
Types of Analysis:
1)
Worst Case
2) Average Case
3) Best Case
1. Worst Case Analysis:
- The maximum amount of the time taken by an algorithm on input size n is called worst case analysis.
- In the worst case analysis, we calculate the upper limit of the execution time of an algorithm.
- It executes in maximum no. of steps.
- Generally, it is denoted by Big Oh(O) notation.
2. Average Case Analysis:
- The average amount of the time taken by an algorithm on input size n is called average case analysis.
- In the average case analysis, we take all possible inputs and calculate the computation time for all inputs. Add up all the calculated values and divide the sum by the total number of entries.
- It executes in maximum no. of steps.
- Generally, it is denoted by Big Theta (Θ) notation.
3. Best Case Analysis:
- The minimum amount of the time taken by an algorithm on input size n is called best case analysis.
- In the best case analysis, we calculate the lower bound of the execution time of an algorithm.
- It executes in minimum no. of steps.
- Generally, it is denoted by Big Omega (Ω) notation.
Sorting Algorithms:
Sorting
algorithms are used to arrange the elements in an array or a given data
structure in some specific order either ascending or descending order. These
algorithms take an input list, processes it (i.e, performs some operations on
it) and produce the sorted list.
The most common example we
experience every day is sorting items on an e-commerce website either by
lowest-price to highest, or list by popularity, or some other order.
Consider an
array;
int A[10] = { 6, 3, 10, 2, 25, 35, 30, 12,
16, 8 )
The Array sorted in ascending order will be given as;
A[] = { 2, 3, 6, 8,
10, 12, 16, 25, 30, 35 }
There are many sorting algorithm by using
which, sorting can be performed.
Some
sorting algorithms available are:
(i) Selection sort
(ii) Insertion sort
(iii) Bubble sort
(iv) Quick sort
(v) Merge sort
(vi) Heap sort
Selection Sort:
Selection Sort is one of the simplest
sorting algorithm. When sorting a small list, selection sort can be used. It
is an in-place comparison based algorithm. In this algorithm the array
is divides into two parts, the sorted part at the left and the
unsorted part at the right end. Initially, the sorted part of the array is
empty, and the unsorted part is the given array.
In selection sort, the first smallest
element is selected from the unsorted array and placed at the first position.
After that second smallest element is selected and placed in the second
position. The process continues until the array is entirely sorted.
Insertion Sort:
Insertion sort is a simple sorting algorithm for a small
number of elements. As the name suggests, insertion sort inserts each element
of the array to its proper place.
Insertion sort is the sorting algorithm 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.
Insertion sort works similar to the sorting of playing cards
in hands. It is assumed that the first card is already sorted in the card game,
and then we select an unsorted card. If the selected unsorted card is greater
than the first card, it will be placed at the right side; otherwise, it will be
placed at the left side. Similarly, all unsorted cards are taken and put in
their exact place. The same approach is applied in insertion sort.
We insert each element into its proper place in the sorted array using this
algorithm.
Bubble Sort:
Bubble Sort is the simplest sorting algorithm that
works by repeatedly swapping the adjacent elements until
they are not in the intended order. The algorithm traverses a list and
compares adjacent values, swapping them if they are not in the correct order.
If the given array has to be sorted
in ascending order, then bubble sort will start by comparing the first element
of the array with the second element, if the first element is greater than the
second element, it will swap both the elements, and then move on to
compare the second and the third element, and so on.
If we
have total n elements,
then we need to repeat this process for n-1 times.
It is known as bubble
sort, because with every complete iteration the largest element in the
given array, bubbles up towards the last place or the highest index, just like
a water bubble rises up to the water surface.
Searching Algorithm:
Searching is the process of finding
some particular element in the list. If the element is present in the list, the
process is considered successful, and it returns the location of that element.
Otherwise, the search is called unsuccessful.
Linear Search and Binary Search are
the two popular searching techniques.
Linear Search:
Linear search is also known as sequential search. It is the simplest searching algorithm. It examines each element until it finds a match, starting at the beginning of the list, until the end.This
search process starts comparing search element with the first element in the
list. If both are matched then result is element found otherwise search element
is compared with the next element in the list. Repeat the same until search
element is compared with the last element in the list, if that last element
also doesn't match, then the result is "Element not found in the
list". That means, the search element is compared with element by element
in the list.
The linear search algorithm is easy to implement and efficient in two scenarios:
- When the list contains lesser elements
- When searching for a single element in an unordered array.
The worst-case time complexity of
linear search is O(n).
Binary Search:
Binary search is the most popular Search algorithm. It is
efficient and also one of the most commonly used searching techniques. It is a searching algorithm for
finding an element's position in a sorted array. Binary search can be implemented
only on a sorted list of items. If the elements are not sorted already, we need
to sort them first.
This search algorithm works
on the principle of divide and conquer approach
in which the list is divided into two halves, and the item is compared with the
middle element of the list. If the match is
found then, the location of the middle element is returned. Otherwise, we
search into either of the halves depending upon the result produced through the
match.
0 Comments
if you have any doubts plz let me know...