## Search This Blog

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.