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

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