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   

 

#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);
}