ADA unit-1
ADA unit-1
ADA unit-1
Characteristics of an algorithm:
Karatsuba Algorithm
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:-
2. Space Complexity
2. Quick sort
Quick sort is a sorting algorithm based on the divide and conquer approach where,
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 -
Algorithm
2. Space Complexity
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.
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.
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.
Stable YES