//Selection sort
#include <stdio.h>
int main()
{
    int array[100], n, c, d, position, t;

    printf("Enter number of elements\n");
    scanf("%d", &n);

    printf("Enter %d integers\n", n);

    for (c = 0; c < n; c++)
        scanf("%d", &array[c]);

    for (c = 0; c < (n - 1); c++)
    {
        position = c;

        for (d = c + 1; d < n; d++)
        {
            if (array[position] > array[d])
                position = d;
        }
        if (position != c)
        {
            t = array[c];
            array[c] = array[position];
            array[position] = t;
        }
    }

    printf("Sorted list in ascending order:\n");

    for (c = 0; c < n; c++)
        printf("%d\n", array[c]);

    return 0;
}

//insertion sort
#include <stdio.h>

int main()
{
  int n, array[1000], c, d, t, flag = 0;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 1 ; c <= n - 1; c++) {
    t = array[c];

    for (d = c - 1 ; d >= 0; d--) {
      if (array[d] > t) {
        array[d+1] = array[d];
        flag = 1;
      }
      else
        break;
    }
    if (flag)
      array[d+1] = t;
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }

  return 0;
}

//insertionSort And Binary search Using Function
#include<stdio.h>

void insertionSort(int arr[], int n)
{
    int i, value, empty;

    for(i=1;i<n;i++){
    value=arr[i];
    empty=i;

    while(empty>0 && arr[empty-1]>value){
        arr[empty]=arr[empty-1];
        empty--;
    }
    arr[empty]=value;
}

}
 void binary_search( int arr[], int n,int item)
{
    int left =0, right= n-1, middle;
        while(left<=right)
        {
          middle=(left+right)/2;


            if(arr[middle]==item)
            {
                printf("item found index %d" ,middle);
                return 0;
            }
        else if (arr[middle]<item)
        {
            left= middle+1;
        }

        else {
            right=middle-1;
        }
    }
    printf("Item not found");

}
int main()
{
    int n;
    printf("Enter array size : ");
    scanf("%d",&n);

    printf("Enter Array Elements : ");
    int arr[n];
    for(int i=0; i<n; i++)
        {
            scanf("%d",&arr[i]);
        }
        insertionSort(arr,n);
        int key;
        scanf("%d",&key);
        binary_search(arr,n, key);
        return 0;


}