// Binary Search

#include<iostream>
using namespace std;

int binary(int arr[], int size, int item){

    int beg = 0, last = size - 1, mid;
 
while (beg <= last){
   
    mid = (beg + last) / 2;
   
    if (arr[mid] == item)
    return mid;
else if (item > arr[mid])
beg = mid + 1;
else
last = mid - 1;
}
return -1;
}


int main(){

int size, item, output;

cout<<"\nEnter Size of Array : ";
cin>>size;
int arr[size];

cout<<"\nEnter "<<size<<" Elements : ";
for(int i=0;i<size;i++){
cin>>arr[i];
}

cout<<"\nEnter Element to Search : ";
cin>>item;
output = binary(arr,size,item);

if(output != -1)
cout<<"\nElement "<<item<<" Found at index "<<output;
else
cout<<"\nElement Not Found !";

return 0;
}

// Linear Search

#include<iostream>
using namespace std;

void linear(int arr[], int size, int item){

    for(int i = 0; i < size; i++)
{
    if(arr[i] == item)
{
    cout<<"\nElement "<<item<<" Found at index "<<i;
    return;
}
}
cout<<"\n\lement Not Found !";
}


int main(){

int size, item;

cout<<"\nEnter Size of Array : ";
cin>>size;
int arr[size];

cout<<"\nEnter "<<size<<" Elements : ";
for(int i = 0; i < size; i++){
cin>>arr[i];
}
cout<<"\nEnter Element to Search : ";
cin>>item;
linear(arr,size,item);

return 0;
}

// Insertion Sort
#include<iostream>
using namespace std;

void insertion(int arr[], int size)
{
int temp, j;

for(int i = 1; i <= size - 1; i++)
{
        temp=arr[i];
        j=i-1;
       
while((temp < arr[j]) && (j >= 0))
{
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = temp;
    }
}
int main(){

int size;

cout<<"\nEnter Size of Array : ";
cin>>size;
int arr[size];

cout<<"\nEnter "<<size<<" Elements : ";
for(int i = 0; i < size; i++){
cin>>arr[i];
}
insertion(arr,size);
cout<<"\nArray After Insertion() : ";
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}

return 0;
}

#include<iostream>
using namespace std;

void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}

int partition(int arr[], int start, int end)
{
int pivot = arr[end];
int i,j;

j = start;
for (i = start; i < end; i++)
{
if (arr[i] <= pivot)
{
swap(&arr[i], &arr[j]);
j++;
}

}
swap(&arr[j], &arr[end]);
return j;
}

void quicksort(int arr[], int start, int end)
{
int part;

if (start < end)
{
part = partition(arr, start, end);

quicksort(arr, start, part - 1);
quicksort(arr, part + 1, end);
}
}

int main()
{
int size;
cout<<"\n Enter the size of the array : ";
cin>>size;

int arr[size];

cout<<"\n Enter "<<size<<" elements in the array : ";
for (int i = 0; i < size; i++)
{
cin>>arr[i];
}

quicksort(arr, 0, size - 1);

cout<<"\n Sorted Array : ";
for (int i = 0; i < size; i++)
{
cout<<arr[i]<<" ";
}

return 0;
}

//Selection Sort Program
#include<iostream>
using namespace std;

#include<conio.h>

void SelectionSort(int arr[], int size)
{
int min,pos;
for (int i = 0; i < size - 1; i++)
{
min = arr[i];
pos = i;
//Finding the smallest element
for (int j = i + 1; j < size; j++)
{
if (arr[j] < min)
{
min = arr[j];
pos = j;
}
}
//Swaping the smallest element to its accurate position
arr[pos] = arr[i];
arr[i] = min;
}
}

int main()
{
int size;

cout<<"\n Enter the size of the array : ";
cin>>size;

int arr[size];

cout<<"\n Enter the Elements in the array : ";
for (int i = 0; i < size; i++)
{
cin>>arr[i];
}

SelectionSort(arr, size);

cout<<"\n Sorted Array : ";
for (int i = 0; i < size; i++)
{
cout<<arr[i]<<" ";
}

getch();
return 0;
}