Search This Blog

Search & Sort

Linear Search: O(n)
int linear_search(int ar[], int n, int key){
    for(int i=0; i<n; i++){
        if(ar[i]==key) {
            return i+1;
        }
    }
    return -1;
}

Binary Search: O(log n)
int b_search(int ar[], int n, int k)
{
    int start=0,last=n-1,mid;
    while(start<=last && ar[mid] != k){
        mid=(start+last)/2;
        if(k>ar[mid]) start=mid+1;
        else last=mid;
    }
    if(start>last) -1;
    return mid;
}

Quick Sort: O(n2)


void quicksort(int A[],int lo,int hi)
{
    if(lo<hi){
        int pivot = PARTITION(A,lo,hi);
        quicksort(A,lo,pivot-1);
        quicksort(A,pivot+1,hi);
    }
}
int PARTITION(int A[], int lo, int hi){
    int x= A[hi];
    int i= lo-1;
    for(int j=lo; j<hi; j++){
        if(A[j]<=x) swap(A[++i],A[j]);
        //cout<<"hi\n";
    }
    swap(A[i+1],A[hi]);
    return i+1;
}


Insertion Sort: O(n2)

void insertionSort(int ar[],int n)
{
    int i,j,x;
    for(i=1; i<n; i++){
        x=ar[i];
        j=i-1;
        while(j>=0 && ar[j]>x){
            ar[j+1]=ar[j];
            j--;
        }
        ar[j+1]=x;
    }

}


Merge Sort: O(n log n)

void mergesort(int ar[], int lo, int hi)
{
    if(lo<hi){
    int mid= (lo+hi)/2;
    mergesort(ar,lo,mid);
    mergesort(ar,mid+1,hi);
    Merge(ar,lo,mid,hi);
    }
}
void Merge(int ar[],int lo, int mid, int hi){
    int i,j,k;
    int n1= mid-lo+1;
    int n2=hi-mid;
    int L[n1+1], R[n2+1];
    for(i=1; i<=n1; i++)  L[i-1]= ar[lo+i-1];
    for(i=1; i<=n2; i++)  R[i-1]= ar[mid+i];
    L[n1]= MAX;
    R[n2]= MAX;
    i=0;
    j=0;
    for(k=lo; k<=hi; k++){
        if(L[i]<=R[j])  ar[k]= L[i++];
        else ar[k]=R[j++];
    }
}



No comments

Powered by Blogger.