Week 1 of DAA in CPP

Iterative Linear Search

#include<iostream>
using namespace std;

int iterativeLinearSearch(int arr[], int size, int key){
  for(int i = 0;i<size;i++)
    if(arr[i]==key) return i;
  return -1;
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  int key;
  cout<<"Enter key : ";
  cin>>key;
  int index = iterativeLinearSearch(arr,n,key);
  if(index == -1){
    cout<<"Element not found";
  }
  else{
    cout<<"Element found on index "<<index;
  }
}

Recursive Linear Search

#include<iostream>
using namespace std;

int recursiveLinearSearch(int arr[], int size, int key){
  if(size <= 0) return -1;
  if(arr[size-1] == key) return size-1;
  return recursiveLinearSearch(arr, size-1, key);
} 

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  int key;
  cout<<"Enter key : ";
  cin>>key;
  int index = recursiveLinearSearch(arr,n,key);
  if(index == -1){
    cout<<"Element not found";
  }
  else{
    cout<<"Element found on index "<<index;
  }
}

Iterative Binary Search

#include<iostream>
using namespace std;

#define swap(a,b) (a=a+b-(b=a))

void sortArray(int arr[], int size){
  for(int i=0;i<size;i++)
    for(int j=0;j<size-i-1;j++)
      if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
}

int iterativeBinarySearch(int arr[],int size, int key){
  int low=0,high=size-1;
  while(low<=high){
    int mid = (low+high)/2;
    if(arr[mid] == key) return mid;
    if(arr[mid] > key) high = mid-1;
    if(arr[mid] < key) low = mid+1;
  }
  return -1;
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  int key;
  cout<<"Enter key : ";
  cin>>key;
  sortArray(arr,n);
  int index = iterativeBinarySearch(arr,n,key);
  if(index == -1){
    cout<<"Element not found";
  }
  else{
    cout<<"Element found on index "<<index;
  }
}

Recursive Binary Search

#include<iostream>
  using namespace std;

  #define swap(a,b) (a=a+b-(b=a))

  void sortArray(int arr[], int size){
    for(int i=0;i<size;i++)
      for(int j=0;j<size-i-1;j++)
        if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
  }

  int recursiveBinarySearch(int arr[], int key,int low, int high){
  if(low > high) return -1;
  int mid = (low+high)/2;
  if(arr[mid] == key) return mid;
  if(arr[mid] > key) return  recursiveBinarySearch(arr,key,low,mid-1);
  return recursiveBinarySearch(arr,key,mid+1,high);
  }

  int main(){
    int n;
    cin>>n;
    int low=0,high=n-1;
    int arr[n];
    for(int i=0;i<n;i++){
      cin>>arr[i];
    }
    int key;
    cout<<"Enter key : ";
    cin>>key;
    sortArray(arr,n);
    int index = recursiveBinarySearch(arr,key,low,high);
    if(index == -1){
      cout<<"Element not found";
    }
    else{
      cout<<"Element found on index "<<index;
    }
  }

Bubble Sort

#include<iostream>
using namespace std;

#define swap(a,b) (a=a+b-(b=a))

void bubbleSort(int arr[], int size){
  for(int i=0;i<size;i++)
   for(int j=0;j<size-i-1;j++)
    if(arr[j] > arr[j+1]) swap(arr[j],arr[j+1]);
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++) cin>>arr[i];
  for(int i=0;i<n;i++) cout<<arr[i]<<" ";
  bubbleSort(arr,n);
  cout<<endl;
  for(int i=0;i<n;i++) cout<<arr[i]<<" ";
  return 0;
}

Insertion Sort

#include<iostream>
using namespace std;

void insertionSort(int arr[], int size){
  int key,j;
  for(int i=1;i<size;i++){
    key = arr[i];
    j = i-1;
    while(j>=0 && (arr[j] > key)) arr[j+1] = arr[j--];
    arr[j+1] = key;
  }
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++) cin>>arr[i];
  for(int i=0;i<n;i++) cout<<arr[i]<<" ";
  insertionSort(arr,n);
  cout<<endl;
  for(int i=0;i<n;i++) cout<<arr[i]<<" ";
  return 0;
}

Selection Sort

#include<iostream>
using namespace std;

#define swap(a,b) (a=a+b-(b=a))

void selectionSort(int arr[],int size){
 for(int i=0;i<size-1;i++){
  int min_index = i;
  for(int j=i+1;j<size;j++) 
    min_index = (arr[min_index] > arr[j])?j:min_index;
  swap(arr[i],arr[min_index]);
 }  
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int &x:arr) cin>>x;
  for(int x:arr) cout<<x<<" ";
  selectionSort(arr,n);
  cout<<endl;
  for(int x:arr) cout<<x<<" ";
  return 0;
}

Quick Sort

#include<iostream>
using namespace std;

#define swap(a,b) (a=a+b-(b=a))

int partition(int arr[], int start, int end){
  int pivot = arr[start];
  int i = start+1;
  int j = end;
  while(i<j){
    while(i<=end && arr[i] <= pivot) i++;
    while( j>=start && arr[j] > pivot) j--;
    if(i<j) swap(arr[i],arr[j]);
  }
  swap(arr[start],arr[j]);
  return j;
}

void quickSort(int arr[], int start, int end){
  if(start>=end) return;
    int partition_index = partition(arr,start,end);
    quickSort(arr,partition_index+1,end);
    quickSort(arr,start,partition_index-1);
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int &x:arr) cin>>x;
  for(int x:arr) cout<<x<<" ";
  quickSort(arr,0,n-1);
  cout<<endl;
  for(int x:arr) cout<<x<<" ";
  return 0;
}

Merge Sort

#include<iostream>
using namespace std;

#define BUFFER 100
void merge(int arr[],int mid, int low, int high){
  int temp[BUFFER];
  int i=low,j=mid+1,k=0;
  while(i<=mid && j<=high)
    temp[k++] = (arr[i] <= arr[j])?arr[i++]:arr[j++];
  while(i<=mid) temp[k++] = arr[i++];
  while(j<=high) temp[k++] = arr[j++];
  for(int i=low,x=0;i<=high;i++,x++) arr[i] = temp[x];
}

void mergeSort(int arr[],int low, int high){
  if(low>=high) return;
  int mid = (low+high)/2;
  mergeSort(arr,low,mid);
  mergeSort(arr,mid+1,high);
  merge(arr,mid,low,high);
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int &x:arr) cin>>x;
  for(int x:arr) cout<<x<<" ";
  mergeSort(arr,0,n-1);
  cout<<endl;
  for(int x:arr) cout<<x<<" ";
  return 0;
}

Count Sort

#include<iostream>
using namespace std;

#define MAX(x,y) ((x>y)?x:y)

void countSort(int arr[],int size){
  int max = arr[0];
  for(int i=0;i<size;i++) max = MAX(max,arr[i]);
  int temp[max+1]={0};
  for(int i=0;i<size;i++) temp[arr[i]]++;
  int i=0,j=0;
  while(i<=max){
    if(temp[i]-- > 0) arr[j++] = i;
    else i++;
  }
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int &x:arr) cin>>x;
  for(int x:arr) cout<<x<<" ";
  countSort(arr,n);
  cout<<endl;
  for(int x:arr) cout<<x<<" ";
  return 0;
}

Radix Sort

#include<iostream>
using namespace std;

#define max(x,y) ((x>y)?x:y)

void countingSort(int arr[], int size, int pos){
  int output[size],temp[10]={0};
  for(int i=0;i<size;i++) temp[(arr[i]/pos)%10]++;
  for(int i=1;i<10;i++) temp[i] += temp[i-1];
  for(int i=size-1;i>=0;i--) output[temp[(arr[i]/pos)%10]---1] = arr[i];
  for(int i=0;i<size;i++) arr[i] = output[i];
}

void radixSort(int arr[], int size){
  int m = arr[0];
  for(int i=0;i<size;i++) m=max(m,arr[i]);
  for(int pos=1;m/pos>0;pos*=10){
    countingSort(arr,size,pos);
  }
}

int main(){
  int n;
  cin>>n;
  int arr[n];
  for(int &x:arr) cin>>x;
  for(int x:arr) cout<<x<<" ";
  radixSort(arr,n);
  cout<<endl;
  for(int x:arr) cout<<x<<" ";
  return 0;
}