Problem of the Day
A new programming or logic puzzle every Mon-Fri

Today's objective is to create a function that takes in a sorted array and a new value to insert in to that array. The function should then insert the value in sorted order and return back the array with the new value. Your function should figure out where to insert the new value in better than O(n) time (on average).

Comments:

• Anonymous - 10 years, 6 months ago

  from bisect import bisect_left
  
  def inserted_sort(el, lst):
      p = bisect_left(lst, el)
      return lst[:p] + [el] + lst[p:]
  
  print(inserted_sort(3, [1,2,4,5,6]))
  print(inserted_sort(5, [1,2,3,4,5,6]))
  print(inserted_sort(0, [1,2,3,4]))
  print(inserted_sort(6, [1,3,4,5]))
  

  reply permalink

• Nick Krichevsky - 10 years, 6 months ago

  Done. I figured mine should come with a joke today. Two men walk into a bar. Ouch. (Did I ever mention I was terrible at jokes?)

  nums = [1,2,3,5,11] #We're assuming a good input and the list is already sorted
  checkNums = list(nums) #Creating a duplicate of the list. If we don't do this our for loop will run forever :(
  num = 12
  for item in checkNums:
      if item > num:
          nums.insert(nums.index(item),num)
          break
      elif item == nums[-1]:
          if num > item:
              nums.append(num)
              break
  print nums
  

  reply permalink

• bumbleguppy - 10 years, 6 months ago

  This was my first thought as well, just iterate through each list item and compare. But I was concerned about the operation time had to be better than O(n).

  Since I don't have a CS degree, I had to look up what O(n) meant, and found this:

  http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

  I am intrigued by the "binary search" concept.

  Could I write something that finds the middle value and then compares the input to it? i.e. "is it in the first half or second half of the list?"

  That way I halve HALVED the number of operations right off the bat! :)

  Sill working on it, though.

  reply permalink

• Max Burstein - 10 years, 6 months ago

  Nicely done. Binary search is indeed the correct way to approach this problem.

  reply permalink

• bumbleguppy - 10 years, 6 months ago

  I think I've got it now in javascript:

    function big_O_experiment(val, arr)
    {
       var low = 0;
       var high = arr.length - 1;
       var mid = Math.round(high / 2);
       var retArr = [];
       while(true){
          if(val > arr[mid]){
             low = mid;
          }else{
             if(val < arr[mid]){
                high = mid;           
             }else{
                break; //value === arr[mid]
             }
          }
  
          mid = Math.round((high + low) / 2);
  
          if((high - low) <= 1){
             break;
          }
       }
  
       return retArr.concat(arr.slice(0, mid), val, arr.slice(mid));
  
    }
  
  
    console.log(big_O_experiment(74, [1,2,3,5,6,7,8,12,15,23,45,67,82,123,253]));
  

  reply permalink

• bumbleguppy - 10 years, 6 months ago

  Oops, fails when value is lower than first element :(

  reply permalink

• Mre64 - 10 years, 6 months ago

  /* Mre64 6/17/14

  ''I'm a tree, I feed branches of people''
      -Kanye West
  

  */ import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List;

  public class InsertSort {

  public static void main(String[] args) {
      // Initialize ArrayList with default integer values
      List<Integer> list =  new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,8,9));
      // call addSort method, add 7
      sortAdd(list, 7);
      System.out.println(list.toString());
  }
  // addSort method just takes in an arrayList and a value to place in it, then sort
  public static void sortAdd(List<Integer> list, int add){
      //sort
      Collections.sort(list);
      //add integer
      list.add(add);
      //sort
      Collections.sort(list);
  }
  

  }not a lot of time so i cheated hard today

  reply permalink