Basic Algorithms(Searhcing and Sorting) DSA
SEARCHING
Linear Search:
Let x = element to be found
Let arr[] = search space(array in which x is to be found)
Basic Approach:- Compare all the elements of arr[] one by one with x and if found , return it’s index and if the element is not found and the search space is exhausted, we return -1;
We can improve this if we take two pointers:- one at beginning and other at end and in one traversal we compare the left and right element simultaneously.
Binary Search:
In this, the basic approach is to reduce the search space to half and compare the elements.
- Find middle element from the given search space.
- Compare x with the middle element, if same return middle index.
- If x is less than arr[mid], element would be found in left half i.e from (0 to mid-1).
- If x is greater than arr[mid], element would be found in right half i.e from (mid+1 to high).
- If the search space is finished, return -1
SORTING
Bubble Sort:
The basic approach of this sort is to compare the adjacent elements and if element at left is greater than element at right, then swap them.
As you can observe that after one pass, the maximum element will be at last.
Consider: [10, 2, 5, 3]
Compare 10 and 2, 10 > 2, swap
=> [2, 10, 5, 3]
Compare 10 and 5, 10 > 5, swap
=> [2, 5, 10, 3]
Compare 10 and 3, 10> 3, swap
=> [2, 5, 3, 10]
Now we know 10 is at it’s sorted position so we will compare the rest elements and the array will become sorted.
=> [2, 3, 5, 10]
A boolean variable “swapping” is taken to check if everything is sorted, then no need to make more comparisons.
Insertion Sort:
The basic idea behind this is to, insert the element at it’s correct position one by one.
- Choose the second element and store it in a temp variable.
- Compare it with the left elements until you found a smaller element.
- Shift the element to right
- Place the element stored in temp variable after the smaller element found.
Consider [8, 4, 5, 10]
temp = 4, compare 4 with left element i.e 8, 8>4, shift 8 to right
=> [ ,8, 5, 10]
As there are no element left in the list, place temp at the first position
=> [4, 8, 5, 10]
Now temp = 5, 8 > 5, shift 8
=> [4, , 8, 10]
4>5, place 5 at this position
=>[4, 5, 8, 10]
Now temp = 10, 8<10
No need to do anything. The array is sorted.
Note: Don’t swap elements, we need to shift bigger elements to right so that the element chosen is at the correct position.
Selection Sort:
The basic idea behind it is to find the minimum element of the list and swap it with the first unsorted element.
- Select minimum element from the initial array and place it at the beginning of the array.
- The first element is sorted, so now select minimum from unsorted part and place it at the beginning or unsorted part.
Consider [4, 1, 9, 6]
min = 1
swap it with the first element of array
=> [1, 4, 9, 6]
min = 4
swap it with second element of array
=> [1, 4, 9, 6]
min = 6
swap it with third element of array
=> [1, 4, 6, 9]
The array will be sorted.
Quick Sort(Divide and Conquer algorithm):
The basic approach behind quick sort is to select an element say “pivot” and place it at the correct position and partition the array in left part of pivot and right part and apply the same process.
- Select first element as “pivot”.
- Take two pointers and keep one at beginning(left) and other at end(right).
- Move left pointer to right until a greater element(greater than pivot) is found.
- Move right pointer to left until a smaller element(smaller than pivot) is found.
- Swap left and right pointer element.
- Repeat until left pointer< right pointer.
- Swap the right pointer element and pivot element.
- The pivot will be at it’s sorted position.
- Partition the array and make it two sub arrays one that have element from start to pivot-1 and other that have elements from pivot+1 to end.
- Apply same process. The array will be sorted.
Consider [9, 5, 1, 10, 15, 2]
pivot = 9
left = 1, right = 5
see from left
5<9 move forward left =2
1<9 move forward left = 3
10 > 9 stop left = 3
see from right
2 < 9 stop right = 5
swap 3rd and 5th index element
=> [9, 5, 1, 2, 15, 10]
see again from left
15 > 9 stop left = 4
see from right
15 > 9 move backward right = 3
2<9 stop right = 3
as left > right
swap right i.e. 3rd and pivot element
=>[2, 5, 1, 9, 15, 10]
You will observe that 9 is at it’s sorted position
make 2 sub arrays
=> [2, 5, 1] and [15, 10]
Merge Sort:
The basic idea behind this sort is to divide the array into smaller sub arrays(arrays which can’t be divided further), then merge those sub arrays while sorting them with each other.
It is also a divide and conquer algorithm.
The scanned copy of all the notes related to these algorithms are available here:
If you like the blog, don’t forget to hit the clap icon and follow me for more such blogs.
I will be explaining the complexities of each and every algorithms in my next blog.
