Quick Sort

Quick Sort

 


#include<iostream>
using namespace std;

int partition(int a[], int low, int high, int p){
    //swap a[p] and a[0]
    int temp;
    if(p!=low){temp=a[low];a[low]=a[p];a[p]=temp;}
    int i=low+1;
    int j=high;
    do{
        while(a[i]<=a[low] && i<high){i++;}
        while(a[j]>a[low] && j>low){j--;}
        if(i<j){temp=a[i];a[i]=a[j];a[j]=temp;i++;j--;}
    }while(i<=j);
    //swap a[low] and a[j]
    if(j!=low){temp=a[low];a[low]=a[j];a[j]=temp;}
    return j;
}
void quick_sort(int a[],int low, int high){
    if(low<high){
        int p;
        int mid=(low+high)/2;
        p=partition(a,low,high,mid);
        quick_sort(a,low,p-1);
        quick_sort(a,p+1,high);
    }
return;
}

int main(){
int a[]={5,23,9,0,-1};
int n=sizeof(a)/sizeof(int);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
quick_sort(a,0,n-1);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
}




Merge Sort

Merge Sort

 


#include<iostream>

using namespace std;

void merge(int a[], int b[], int low, int mid, int high){
    for(int j=low;j<=high;j++){
        b[j]=a[j];
    }
int low1=low;
int low2=mid+1;
    int current=low;
    while(low1<=mid && low2<=high){
        if(b[low1]<=b[low2]){
            a[current]=b[low1];
            current++;
            low1++;
        }
        else{
            a[current]=b[low2];
           current++;
              low2++;
       }
    }

while(low1<=mid){
    a[current]=b[low1];
    low1++;
    current++;
}
return;
}

void merge_sort(int a[],int b[],int low, int high){
    if(low<high){
        int mid=(low+high)/2;
        merge_sort(a,b,low,mid);
        merge_sort(a,b,mid+1,high);
        merge(a,b,low, mid, high);
}
return;
}

int main(){
int a[]={5,23,9,0,-1};
int n=sizeof(a)/sizeof(int);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
int b[n];
merge_sort(a,b,0,n-1);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
}

Binary Search

Binary Search

 

#include<iostream>

using namespace std;

int binary_search(int a[], int n, int x){
    int low=0;
    int high=n-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(a[mid]==x){return mid;}
        else if(a[mid]<x){
            low=mid+1;
}
else {high=mid-1;}
}
return -1;
//return low; if one wants to find out the insert position when x not found.
}

int main(){
int a[]={0,1,2,3,4,5,6};
cout<<binary_search(a,7,-1);
return 0;
}