Insertion in unsorted array

Problem Statement : Given unsorted array & element to insert. WAP to insert that element to its correct position.

 

Approach

 

1) Sort the array

2) If element smaller than first element. Insert in beginning 

3) If element greater that last element. Insert in end

4) Else compare with adjacent elements & insert at the appropriate position

 

Source Code   

 

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include<bits/stdc++.h>
using namespace std;

void *insert(int a[], int n, int len)
{
  int i; 

  // Insert at first position
  if(n < a[0])
  {
    len++;
    for(i = len-1; i>=1; i--) a[i] = a[i-1];
    a[0] = n;
  }

  // Insert at last position
  else if(a[len-1]<n)
  {
    a[len] = n;
    len++;
  }

  // Insert in middle of two element
  else
  {
    int pos;
    for(i = 0; i<len-1; i++)
    {
      if(a[i]<n && a[i+1]>n) pos = i+1;
    }
    len++;
    for(i = len-1; i>=pos; i--) a[i] = a[i-1];
    a[pos] = n;
  }

  return a;  
}

// Bubble Sort
void *sort(int a[], int len)
{
  int i, j, tmp;
  for(i = 0; i<len; i++)
  {
    for(j = 0; j<len-i; j++)
    {
      if(a[j]>a[j+1])
      {
        tmp = a[j+1];
        a[j+1] = a[j];
        a[j] = tmp;
      }
    }
  }
  return a;
}

void display(int a[], int len)
{
  for(int i = 0; i<len; i++) cout<<a[i]<<" ";
}

int main()
{
  int a[] = {67, 5, 135, 45, 116};
  int sz = 5;
  sort(a, sz);

  insert(a, 2, 5);
  sz++;
  
  insert(a, 60, sz);
  sz++;

  insert(a, 180, sz);
  sz++;

  display(a, sz);
}