All Algorithms of Searching & Sorting in the Best & Easiest way.
SEARCHING & SORTING ALGORITHM
Linear Search
for(start to end of array)
{
if (current_element equals to 5)
{
print (current_index);
}} Space Complexity:O(1)
Binary Search
int binarySearch(int low,int high,int key)
{
while(low<=high)
{
int mid=(low+high)/2;
if(a[mid]<key)
{
low=mid+1;
}
else if(a[mid]>key)
{
high=mid-1;
}
else
{
return mid;
}
}
return -1; //key not found
} Time Complexity: O(log2 N)
Space Complexity:O(1)
Bubble Sort
void bubble_sort( int A[ ], int n ) {
int temp;
for(int k = 0; k< n-1; k++) {
// (n-k-1) is for ignoring comparisons of elements which have already been compared in earlier iterations
for(int i = 0; i < n-k-1; i++) {
if(A[ i ] > A[ i+1] ) {
// here swapping of positions is being done.
temp = A[ i ];
A[ i ] = A[ i+1 ];
A[ i + 1] = temp;
}
}
}
}Time Complexity: O(N^2)
Space Complexity:O(1)
Selection Sort :
void selection_sort (int A[ ], int n) { // temporary variable to store the position of minimum element int minimum; // reduces the effective size of the array by one in each iteration. for(int i = 0; i < n-1 ; i++) { // assuming the first element to be the minimum of the unsorted array . minimum = i ; // gives the effective size of the unsorted array . for(int j = i+1; j < n ; j++ ) { if(A[ j ] < A[ minimum ]) { //finds the minimum element minimum = j ; } } // putting minimum element on its proper position. swap ( A[ minimum ], A[ i ]) ; } }Time Complexity: comparisons and swaps result in the overall complexity of o(N^2).
Space Complexity:O(1) Insertion Sort :
void insertion_sort ( int A[ ] , int n)
{
for( int i = 0 ;i < n ; i++ ) {
/*storing current element whose left side is checked for its
correct position .*/
int temp = A[ i ];
int j = i;
/* check whether the adjacent element in left side is greater or
less than the current element. */
while( j > 0 && temp < A[ j -1]) {
// moving the left side element to one position forward.
A[ j ] = A[ j-1];
j= j - 1;
}
// moving current element to its correct position.
A[ j ] = temp;
}
}
Time complexity : O(N^2)Space Complexity:O(1) Merge Sort :
void merge(int A[ ] , int start, int mid, int end) {
//stores the starting position of both parts in temporary variables.
int p = start ,q = mid+1;
int Arr[end-start+1] , k=0;
for(int i = start ;i <= end ;i++) {
if(p > mid) //checks if first part comes to an end or not .
Arr[ k++ ] = A[ q++] ;
else if ( q > end) //checks if second part comes to an end or not
Arr[ k++ ] = A[ p++ ];
else if( A[ p ] < A[ q ]) //checks which part has smaller element.
Arr[ k++ ] = A[ p++ ];
else
Arr[ k++ ] = A[ q++];
}
for (int p=0 ; p< k ;p ++) {
/* Now the real array has elements in sorted manner including both
parts.*/
A[ start++ ] = Arr[ p ] ;
}
}
void merge_sort (int A[ ] , int start , int end )
{
if( start < end ) {
int mid = (start + end ) / 2 ; // defines the current array in 2 parts .
merge_sort (A, start , mid ) ; // sort the 1st part of array .
merge_sort (A,mid+1 , end ) ; // sort the 2nd part of array.
// merge the both parts by comparing elements of both the parts.
merge(A,start , mid , end );
}
}
Time Complexity:
The list of size N is divided into a max of logN parts, and the merging of all sublists into a single list takes O(N) time, the worst case run time of this algorithm is O(NLogN)Space Complexity:O(N) Quick Sort :
int partition ( int A[],int start ,int end) {
int i = start + 1;
int piv = A[start] ; //make the first element as pivot element.
for(int j =start + 1; j <= end ; j++ ) {
/*rearrange the array by putting elements which are less than pivot
on one side and which are greater that on other. */
if ( A[ j ] < piv) {
swap (A[ i ],A [ j ]);
i += 1;
}
}
swap ( A[ start ] ,A[ i-1 ] ) ; //put the pivot element in its proper place.
return i-1; //return the position of the pivot
}void quick_sort ( int A[ ] ,int start , int end ) {
if( start < end ) {
//stores the position of pivot element
int piv_pos = partition (A,start , end ) ;
quick_sort (A,start , piv_pos -1); //sorts the left side of pivot.
quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot.
}
}Let’s see the randomized version of the partition function :
int rand_partition ( int A[ ] , int start , int end ) {
//chooses position of pivot randomly by using rand() function .
int random = start + rand( )%(end-start +1 ) ;
swap ( A[random] , A[start]) ; //swap pivot with 1st element.
return partition(A,start ,end) ; //call the above partition function
}
Time complexity of this algorithm is O(N^2) , but as this is randomized algorithm, its time complexity fluctuates between O(N^2) and O(NlogN) and mostly it comes out to be O(NlogN) Space Complexity:O(logN) Radix Sort :
void countsort(int arr[],int n,int place)
{
int i,freq[range]={0}; //range for integers is 10 as digits range from 0-9
int output[n];
for(i=0;i<n;i++)
freq[(arr[i]/place)%range]++;
for(i=1;i<range;i++)
freq[i]+=freq[i-1];
for(i=n-1;i>=0;i--)
{
output[freq[(arr[i]/place)%range]-1]=arr[i];
freq[(arr[i]/place)%range]--;
}
for(i=0;i<n;i++)
arr[i]=output[i];
}
void radixsort(ll arr[],int n,int maxx) //maxx is the maximum element in the array
{
int mul=1;
while(maxx)
{
countsort(arr,n,mul);
mul*=10;
maxx/=10;
}
}
Time complexity is O(kn) and space complexity is O(k + n).Here n is the number of elements and k is the number of bits required to represent largest element in the array.Space Complexity:O(1) Heap Sort :
void heap_sort(int Arr[ ])
{
int heap_size = N;
build_maxheap(Arr);
for(int i = N; i >= 2 ; i-- )
{
swap|(Arr[ 1 ], Arr[ i ]);
heap_size = heap_size - 1;
max_heapify(Arr, 1, heap_size);
}
}
max_heapify has Time complexity O(logN), build_maxheap has complexity O(N) and we run max_heapify N-1 times in heap_sort function, therefore complexity of heap_sort function is O(NlogN) Space Complexity:O(N)
Bucket Sort :
void bucketSort(float[] a,int n)
{
for(each floating integer 'x' in n)
{
insert x into bucket[n*x];
}
for(each bucket)
{
sort(bucket);
}
}if one assumes that insertion in a bucket takes O(1) time,Then Algo will take O(N) time.Space complexity : O(n+k) Counting Sort :
void counting_sort(int A[], int Aux[], int sortedA[], int N) {
// First, find the maximum value in A[]
int K = 0;
for(int i=0; i<N; i++) {
K = max(K, A[i]);
}
// Initialize the elements of Aux[] with 0
for(int i=0 ; i<=K; i++) {
Aux[i] = 0;
}
// Store the frequencies of each distinct element of A[],
// by mapping its value as the index of Aux[] array
for(int i=0; i<N; i++) {
Aux[A[i]]++;
}
int j = 0;
for(int i=0; i<=K; i++) {
int tmp = Aux[i];
// Aux stores which element occurs how many times,
// Add i in sortedA[] according to the number of times i occured in A[]
while(tmp--) {
//cout << Aux[i] << endl;
sortedA[j] = i;
j++;
}
}
}
Time complexity of counting sort algorithm is O(N+K).Space complexity : O(n+k) 
Comments
Post a Comment